Pretty balanced contenst

reverse madness was a cool one

Thanks for the fast Editorial.

Very interesting problem set, especially problem F

One of the best Div3. D problem, first I just printed valued of a,b (cause nothing else was coming in my mind :)), and then i was not difficult to see that for each possible a there is unique b

The idea behind E is nice but you can just code a sparse table to handle the query part from the binary search.

Can you please help me see why the code below times out? This code is for E. Thank you very much!

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int sl,k;
int check(int x)
{
	int res = a[sl];
	for(int i=sl+1;i<=x;i++)
	{
		res &= a[i];
		if(res<k) return 0;
	}
	return 1;
 
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int q;
		scanf("%d",&q);
		while(q--)//Խ��ԽС
		{
			scanf("%d%d",&sl,&k);
			if(a[sl]<k) printf("-1 ");
			else{
			int l=sl,r=n;
			while(l<r)
			{
				int mid=(l+r+1)/2;
				if(check(mid)) l=mid;
				else r=mid-1;
			}
			printf("%d ",l);
			}
		}
		printf("\n");
	}
}

I have a slightly different implementation for Problem G . My approach is the same as the editorial (finding the selective nodes where the bitwise or changes).

However to find these nodes, instead of using binary search, we can maintain a map for every node. The map will have the $$$ closest $$$ $$$ ancestor $$$ to the current node for each distinct bitwise or possible. To find such ancestors we can use a map and iterate on it.

Implementation

1878B — Aleksa and Stack, how smoothly they made me realise that only only odd numbers can divide odd numbers. while even can be divided by both.

I'd like to rephrase the proof of Problem C.

The key observation is that we can always change the sum of k numbers from s to s + 1, given that s is not the maximal. The proof comes as follows. Assume that we have a set of k numbers which sum to s. Let denote the maximal among the k numbers as m. If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done. If the maximal is n, we can prove it by contradiction as shown in the tutorial, i.e., n, n — 1, ..., n — k + 1 will belong to the set. This set will yield the maximal and contradicts the assumption that s is not the maximal.

In problem G, I don't understand why for each bit, we choose the vertex z such that it contains that bit, and z is closest to x (or y). What happen if we choose z such that it is not the closest?

even i can't solve the B one, but watching the editorial was really satisfy and pleasant

For problem E, we can calculate every position, the first 0 to the right of every bit.

Then for each query, iterate each bit from low to high, and check first 0 to the right. If the current bit of k is 1, it needs to satisfy all the smallest right end points that are not 0. If the current bit of k is 0, since we iterate from low to high, the rightmost non-0 can be greater than or equal to k.

I am not sure if my solution is correct, after all, it has not passed the system test. But I want to share my ideas with you, and the code is as follows:

https://codeforces.com/contest/1878/submission/225352692

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

PS: Don't judge me by my current rating :(

Nice hints and comments in the solutions!

For problem C, I wrote down lots of test cases on the paper to check and came up with the solution but couldn't prove it. It's good to see the proof in the editorial now!

Thanks guys for the contest!

Hello. I have a question about Problem G. Why is the complexity not q*logA*logn*logn? Because finding the intersection points takes logA time, finding LCA takes logn time, and finally calculating by bits also takes logn time. I'm a little confused here，and my code get TLE.

E had a very long implementation, a little bit much for div3 question imo.

don't say sorry contest was very nice. All the problems were very interesting.

there's a very simple O(N+Q) solution for E 225432409

First, notice that the only positions of R that change a[L]&...&a[R] are those where the bit which was set in a[L] gets reset. Calculate the next positions where each bit gets reset and store them. Then for each query iterate over those "important" R positions and update the current value of a[L]&...&a[R]. If at a certain R the answer stops being greater than K, then the answer is R-1, otherwise the answer is N-1.

Can I solve the problem E using segment tree? For each query I can use binary search to find the value of "r" and find the value of f(l,r) using query method of segment tree. Time complexity O(q*logn*logn). But I am getting wrong answer after performing binary search.

Problem E and D could have been swapped.. But I'd still say I liked the contest, specially solving D gave me so much pleasure :)

In problem E cant we do bitwise AND between low and high using simple linear for loop like: for(i=low; i<high; i++) andd & = arr[i];

I think the most easier way (I mean no need handle bit by bit) to do 1878E - Iva & Pav is to use seg tree. Here is my solution: 225454109

In D, I used binary search to get the indices, then calculated all the reversals I have to do, then just copy paste a solution of CSES substring reversals. Even if the CSES solution uses treaps, you still can just copy a solution without thinking about the treaps part

I've observed this thing regarding all ICPC-style contests on CF(i.e., div3/div4/edu rounds): fast solving doesn't matter as much as it matters in normal rounds.

For eg. contestants who solved the same no. of problems as me in this div3 but half an hour before me are ranked just 400 places ahead of me.

In problem C it should be the sum of 1 to n-k elements (4th line)

Awesome round in general. The problem are balanced and cover a lot of topic. I really like problem F.

However C is a little bit adhoc but I think it is fine.

And in my opinion, the gap between C and D is close enough.

sparse tables are a little bit too advanced of a topic for div3 E

Meanwhile problem G: range minimum query, binary lifting, LCA.

This is a snippet of neal's solution of D

for (int q = 0; q < Q; q++) {
        int x;
        cin >> x;
        int index = int(lower_bound(R.begin(), R.end(), x) - R.begin());
        int a = min(x, L[index] + R[index] - x);
        a--;
        flips[a]++;
}
 
for (int i = 0; i < K; i++) {
     int sum = 0;
 
     for (int a = L[i] - 1, b = R[i] - 1; a < b; a++, b--) {
         sum += flips[a];
 
         if (sum % 2 != 0)
            swap(S[a], S[b]);
      }
}

Not getting why max(x, l[i] + r[i] - x) is not being considered while doing the swap or even during the preprocessing of queries.

Edit: Ok, got it. So the answer lies in this statement — It is easy to see that the modifications x and n - x + 1 are equivalent.

Can this CSES task be also solved by similar trick, or advanced DS like treap is mandatory?

Can Someone explain why my code gave TLE ? 225358802

F is a very nice problem. Thanks for this round. Hope we see you again.

During testing, I found a nice offline solution for E.

The idea is to iterate from right to left and keep the value for each current prefix. When the values $$$f(i,i)$$$, $$$f(i,i+1)$$$, $$$f(i,i+2)$$$, ... are stored in some array, we can find the answer to some query by performing a binary search. In fact, we keep the right endpoints (denoted by $$$j$$$) in an array. We update the left endpoints ($$$i$$$) dynamically.

This is $$$O(n)$$$ memory. Updating the values when traversing from $$$i$$$ to $$$i-1$$$ can require up to $$$O(n)$$$ time. It seems like the total complexity is $$$O(n^2)$$$, which is untrue. In fact, it is amortized. Notice how we only need to update the values for which $$$f(i,j)$$$ changes. Modifying them decreases the total number of bits (among all values of $$$f$$$). The number of bits is $$$O(n \ log \ A)$$$, making the complexity $$$O(q \ log \ n + n \ log \ A )$$$.

Thank you for the round. Hope we see you again.

Man, there's an even simpler solution for B:

for(int i = 0; i < n; i++)
{
    std::cout << i + 5 << ' ';
}

I hope all contests all balanced like this one , great contest

I solved problem E by using a segment tree to query each segment in logarithmic time but it TLE'd in python3 during the contest. I found out just now that using Pypy is much faster and the solution is easily accepted. Is pypy a reasonable choice for competitive programming or will I still commonly run into this runtime trouble in the future?

Hall of fame level task names and descriptions

In problem D, instead of editorial's approach where it is taking into consideration the parity of number of operations as a condition to swap. I'm maintaining an array (1 based) which stores the number of operations on x [x = min(x, ri + li — x)]. For every query, I perform prefix[x]++ and take prefix sum of this array after all the queries. Now, if parity of number of operations (in the prefix sum array) before starting a new pair of (l, r) and number of operations at any index (in the prefix sum array) during the iteration in this pair is different, that would suggest a swap is required at that index. Otherwise, continue iterating. But I'm getting wrong answer as verdict. Please help me find where I'm going wrong.

Here is the submission link : https://codeforces.com/contest/1878/submission/225566736

why solving C in o(k) gives TLE ? Thanks in advance

Tutorial of D is terribly explained. Worst.

A simple way of understanding...

AlphaMale06 may you explain how sparse table can help here ? as in what we need to implement in the sparse table related to this problem ? sparse tables as far as i know is used to find minimum in a subarray how here it works ?

I personally feel D was easier than E. Maybe it were the long statements.

anyone can explain any of the below solutions if possible ? they took very much less time or sometimes quite low memory space. https://codeforces.com/contest/1878/submission/225305916 by satyam343 https://codeforces.com/contest/1878/submission/225321019 by vgtcross https://codeforces.com/contest/1878/submission/225297136 by jiangly

In problem E, how can we use sparse table to get $$$f(l,r)$$$ in $$$O(1)$$$? I thought it's still needed to reconstruct the segment in $$$O(log_2(r-l))$$$ time? (I don't know much about sparse tables)

I'm getting TLEd on G. What I am doing is, while binary searching the answer, I am fetching the ancestor. So basically the binary search is from 1 to the number of nodes in the path, and accordingly I'm fetching the count of bits. The implementation isn't the best, but it works. This is heavy on time because during my binary search I'm constantly binary lifting to find the node, so the binary search costs O( log(n) * log(max(a)) ). Combine that with query and it TLEs out. I cannot clearly understand how the editorial does it in O( log(n) + log(max(a) ). Any help will be appreciated, thanks in advance!

https://codeforces.com/contest/1878/submission/225749618

For E, solution has mentioned that we can use sparse table also.I am learning segment tree currently..

I think segment tree can also be used here, am i correct?

Good contest and wonderful tutorial! Thanks.

Extended proof for F which may be useful in the future: If $$$x$$$ and $$$y$$$ are coprime, then $$$d(x\cdot y) = d(x)\cdot d(y)$$$

Problem C: Note that the sum of n over all test cases may exceed 2⋅105.

TC 05: 10000 194598 194598 10085825445 196910 196910 19386872505 193137 193137 6236620375 194427 194427 8160790120 ...

shouldn't O(n) also be accepted according to constraints? have i missed something?

Can any of you tell me how the E question was optimized with a hash table, the official question solution doesn't give any specific instructions.

For problem F solution 2, I was actually originally going to do this solution for the problem, but I was deterred because to find prime divisors and their exponents for $$$d(N)$$$, I have to find prime factorization of $$$d(N)$$$. Thus, we need to keep track of the smallest prime factor of numbers up to 1e9 (because $$$d(N)$$$ is bounded by 1e9) if we want logarithmic complexity. This uses too much memory. Has anyone figured out an implementation to find this prime factorization without use of smallest prime factor?

Hye guys!

You can see the detailed solutions for the problems A,B and C with proofs from my youtube video below:

https://youtu.be/odTQC7AOL3s?feature=shared

somebody help me with my implementation for F, it is getting wrong on test 4

//  i started at 1:03 A.M. 1/2/2022 Author:: Gorssorser  , nice to see you here , thnx for visiting
// somebody give me self control text me at my codeforces handle : gorssorser
// i am gorssorser <-n->
//Mei toh bass bajata hun mujhe kya pata ¯\_(ツ)_/¯
//Duniya mei sb log jo tumhare aspas hai sb bhut acche hai.. aur yhi tum glt hogaye, sb madarchod hai..
//////////////////////////////////////////////////////////////////////////////////////////

#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <limits.h>
#include <float.h>
#include <list>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <chrono>
//////////////////   Defining here  ///////////////////////////////////////

#define debmatrix(matrix){  cout<<"debuged matrix: "<<endl; for(auto i : matrix){for(auto j : i){cout<<j<<"  "; } \
 cout<<endl;   }}
#define debpair(matrix){  cout<<"debuged pair: "<<endl; for(auto i : matrix){ cout<<i.first<<"  "<<i.second<<endl; } \
 cout<<endl; }
# define ff first
#define ss second
#define mod1 998244353
#define seg_size 262144
#define sz(x) ((ll)(x).size())
#define all(a)   a.begin() , a.end()
# define debarr(arr){ cout<<"deb arr :"<<endl;  for(auto i : arr){ cout<<i<<" "; } cout<<endl;   }
# define debval(a){cout<<"var : "<<a<<endl;}
#define  ll  long long int
#define pll ll
//////////////////////////////////////////////////  Defining ends here   ////////////////////////
using namespace std;
using namespace __gnu_pbds;
typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

using namespace std;
ll n, x, m, y ;
ll mod  =  1e9+7;
ll mul(ll a,ll b, ll mod = mod)
{
    return ((a%mod)*(b%mod)+mod)%mod;
}
ll add(ll a,ll b, ll mod = mod)
{
    return ((a%mod)+(b%mod)+mod)%mod;
}
ll power1(ll a,  ll b, ll mod = mod)
{
    ll ans = 1 ;
    while(b)
    {
        if(b&1)
        {
            ans = mul(ans, a, mod) ;
        }
        a = mul(a, a, mod ) ;
        b>>=1 ;
    }

    return ans ;

}

ll solve(ll bit )
{
cin>>n >> x ;
    m =  n ;
   while(x--){
    ll div  = 1 ;
    cin>> y;  
    if(y  == 1){
     cin>>y ;
    n *= y;
     ll n_ = n ;
    for(ll i = 2 ; i <=  sqrtl(n) ; i++){
       ll cou =0;
       while(n%i == 0){
             n/=i ;
             cou++ ;
       }
       div = div*(cou+1ll) ;
    }
    if(n != 1 ){
         div = 2ll*div ;
    }
    n =  n_ ;
//    cout<<div<<endl;

    cout<<((n%div == 0) ?  "YES": "NO")<<endl;
     }
     else n = m ;
    }
//    cout<<div<<endl;
    return 0;

}
// u know sometime instead of trying to check for something just prebuild it in thecin>>n ;  correct order ,
// like sort or arrange the things accordinglyif
int  main()
{
    #ifndef ONLINE_JUDGE

    // For getting input from input.txt file
    freopen("input.txt", "r", stdin);

    // Printing the Output to output.txt file
    freopen("output.txt", "w", stdout);

   #endif
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(NULL);
    int t = 1 ;
    cin>>t ;

//    mod =  mod ;
    int counter =  0;
    while(t--)
    {
        counter++ ;
        int   bit  = 0 ;
        if(counter == 5  )bit = 1;
//        cout<<"Case #"<<counter<<": ";
        solve( bit );
//        cout<<endl;
//        counter++;
    }
    return 0;
}
/*DSA
   Quick Sort it is for all and for everything
   Finding can also be done using two pointer + sorting /;v;\,  sometimes use bounds , l and r to look for greatest consecutive sequence,
   slow and fast pointer you should think like everytime it comes one step closure to hare , so in worst time it will catch hare at the root node
   how to store previous data of diagonal in matrix efficiently   it row+col vector ,   think about elinimation as done in celeb problem if(a know b then a cant, and if he doesnt then b cant)
   you know if you can go into the depth the you can also come out of that depth and may be it is much easier(longest palindrome in  a string) ,
   BST: inorderTraversal , BSTiterator, Kahn Algorithms
   BST: inorderTraversal , BSTiterator, Kahn Algorithms
   Detecting Cycles: BFS kahns method of inorder Edges, DFS vis[1] , vis[2] , undirected BFS vis[1] means cycles
   Kahn for topo and stack also for dfs topo sort


   /;v;\
*/
/*Digit Dp states are defined as dp[index][tight] with additional states if any*/
/* greedy brute force dp binary search constructive pegion hole  */
/*some times negation is much preferred */
/*some times u will fall but a babmoo tree1 take 4 yrs to start, now its time to start to grow */
/*go for second intuition once stuck for an hr*/
/*Euler Flattening and Mo-algorithm, Sqrt Decomposition*/
/*palindrome manacher , KMP , string hashing*/
/*why not mo sometimes of queries of continuous fashion , updating ans each time depending on frequencies*/
/*always think for applying mos in which you need some freq kinda of a thing in a range */
/*

/*Number Theory Help :
    mod of p1*p2*p3*p4*p5*.......pn, where pi, pj are all pair wise co prime numbers  if they mod a certain number then,
    let say  number is n , then the mod of n if n%p1  == 0 that implies (n%(p1*p2*p3*p4 .... pn))  %  p1  == 0


*/
// a| b = a^b + a&b      a^(a&b) = (a|b)^b       b^(a&b) = (a|b)^a       (a&b)^(a|b) = a^b
// a+b = a|b + a&b      a+b = a^b + 2(a&b)
// a-b = (a^(a&b))-((a|b)^a)    a-b = ((a|b)^b)-((a|b)^a)   a-b = (a^(a&b))-(b^(a&b))   a-b = ((a|b)^b)-(b^(a&b))

/*Type more ^v^*/

In ProblemG, can anyone say why am i getting TLE in testcase 24 227234745?

my segment tree solution for E 227542958

Problem D was a good one. However the tutorial was not so clear. I think the tutorial should emphasize the relation between the example (l = 1 and r = n) and common l and rs. It really took me an effort to really comprehend(Yes I'm newbee, and I'm sure there are lots of like me out there.....)

Hi, for problem G, I don't quite understand why the array r can be used to calculate the OR operations. Can anyone explain to me what is the logic behind that?

Gave virtual contest, solved A B D E, failed on C.

for C I assumed it would be on the easier side and I guessed the solution kinda. I am not able to correctly prove the solution.

I tried doing a brute-force simulation of the process by taking the smallest set 1..k and then replacing it as needed but not able to proceed as the logic itself was not clear.

Is it possible to get the valid set ?

Asking in case instead of YES / NO, if it was a constructive question.

Is problem G possible in O(n log n)? The part where you calculate the ORs for each node can be optimized by noticing that the total value of the sums of the g function will increase by 1 in the first occurence of the bit and decrease by 1 in the last occurence of the bit (going from x to y). With that in mind we can just go from the closest important node to X to the last important node and keep track of the current sum.

However the bottleneck is still there in finding the important nodes. Is there a way to optimise it O(nlogn)?

For => 1878C — Vasilije in Cacak

n, k, and x are input integers read from the standard input. max_sum and min_sum are calculated as follows:

max_sum is the maximum sum achievable based on the value of k. It's calculated using the sum of the first k natural numbers.min_sum represents the minimum sum based on the range (2 * n — k + 1) * k / 2. It considers the summation of numbers within a specific range. The conditional check determines if either the min_sum is less than x or the max_sum is greater than x.

If either condition is true, the output will be "NO," indicating that the given condition doesn’t hold. Otherwise, the output will be "YES," signifying that the condition is met.

int t; cin >> t; while (t--) { long long n, k, x; cin >> n >> k >> x; long long max_sum = k * (k + 1) / 2; long long min_sum = (2 * n — k + 1)*k / 2; if (min_sum < x || max_sum > x) { cout << "NO" << endl; } else { cout << "YES" << endl; }

}

why does this code fail 255033091 and when i change the line m=m1 to add_divs(n,m) it gets acc why if i change m=m1 it fails