Don't forget that Adonis is a gentleman, he reads, meditates and works out daily, doesn't waste precious time in gaming or social media, doesn't fap, stays on his diet, works hard for his goals, respects women and his parents, and doesn't settle for weakness. Be like Adonis my friends, be the best version of yourself you can be.

Actually, it's the second or third already.

Don't forget Codeforces Round 659 (Div. 1)

Another division should be created for this single person

And what about that?

Um_nik wins.

not happening now. You did jinxed it.

jinxed...

they have to participate to help tourist cross 4000 rating

It means that the authors are from Cuba.

it means the authors are from Kuban

.

1. Don't copy paste code directly into comments. No one has the patience to try and understand unformatted code. It's also a nuisance to all those reading other comments on the blog since it takes up so much space. Use a code block and if it takes up more than a few lines, use a spoiler tag (there are options for them when you comment). If it is an entire submission, just provide the link (143943751).
2. This is the announcement blog for an upcoming round, so this is not the place to be posting this.
3. At least make an effort to solve your problem yourself. If you look at your sumbmission, the verdict says RTE on test 24. The first line even says "Probably, the solution is executed with error 'out of bounds' on the line 74".
4. If you're asking for a favour, maybe it would be better to give readers some context (ask your question) prior to dumping a huge block of code in their face.
5. And here you go: 143948025.

Who is Adonis?

No...

When you participate in Codeforces rounds you must prepare yourself for anything because there are a lot of creative minds of who will set the problems in the contest on this round and another rounds, good luck .

No. The score assigned to each problem is the score that you will gain if you solved this problem during contest, not the delta that you will gain after the contest.

Yes, Participate in as many contests as possible.

Since you are New I have 2 suggestions:

1) Initially participate for learning not for rating cause ultimately you have nothing to lose.

2) Enjoy the contest.

Yes

How would you explain a scenario where everyone performs well.

I bet <0.001% can even understand um-nik's solution

i thought the same for a while and then realized my foolishness. in my case, i was considering, k == n — 1 as a -1 condition which is completely inaccurate.

Yea Me too but still i have the hope:)

He got concerned if there's a Y2K-like issue with CF rating database.

The one with almost same memory and time are suspicious

Honestly, I thought it was a really cool problem till I got WA on test 2. The edge case for n>4 & k= n-1 is freaking disgusting (maybe an example testcase would solve this..). I was sure about the correctness of my solution (at least for the rest of it...) and for the whole contest, I was trying to figure out what was wrong. I am really disappointed that the overall contest performance gets blown by such crap.

Yes problem C ruined my day :(.

I figured out that edge case quickly, yet i was too late because i spent half an hour trying to fix a tiny bug in B.It would be sad if that was the only reason of my WA in C..
edit: my code got WA because of that case and I also had a typo in the code anyway :D

Thanks to problem C, at least I know what type of problem I hate the most :

The one that has tricky cases

If every subarray needs to have strictly more in range than out of range, then the entire array needs to have at least k more in range than out of range. Finding the range requires constructing a copy of the array and then sorting, and then minimizing arr[i+dist]-arr[i]. Constructing is then a linear scan waiting for the moment in range > out of range, except for the last one being the rest of the array.

My thoughts were: for a fixed interval $$$[x, y]$$$ denote all the numbers that are in this interval by $$$1$$$ and all the others by $$$-1$$$. Then you should be able to find partition where all the segments have their sum > 0. If you compute array of prefix sums then you should check if its longest increasing subsequence starting with $$$0-$$$th number and ending in $$$n$$$-th number is at least $$$k + 1$$$. You can binsearch on $$$y - x$$$ and iterate over $$$x$$$ somehow manipulating on longest increasing subsequence but I didn't figured out how.

Edit: saw solution above, my is overkill

And why do you think so?

For you

Fixed, we are very sorry for all the issues with that

I think you overkilled it, you can pair i and (n — 1) xor i, to create anything less than n — 1, you can create pairs (k, n — 1), (0, k xor (n — 1)), for n — 1 it's same but create 1 and n — 2.

x & ~x = 0 so you can pair $$$n-1$$$ with $$$k$$$, $$$0$$$ with $$$\sim k$$$, and $$$x$$$ with $$$\sim x$$$ for other $$$x$$$s. The only tricky part is that despite what the example suggests the answer always exists when $$$n>4$$$ and the above construction only works when $$$k<n-1$$$ so another one is needed (it's also simple. The case analysis seems unavoidable).

At first I tried to find the way how to get sum == 0. And it is clear to see that we can match every number to it's inverted partner (a goes with b, where a == ), so in every pair (a^b) = (n-1) is true.

Then I tried to find a way to get value k with only 1 swap. If we match some value with 0, we always get 0. If we match x with n-1, we always get x. So let's take a pair (k, ) and match k with n-1, and with 0. Every other pair is still valid, and the answer is k.

We cannot do that when k == n-1, so for n == 4 the answer is -1.

But when n is 8 or more, there is always a way to make sum equal to k. I thought that we should divide "adding k" into 2 parts. I decided to add k-1, and 1 seperately. So I had to add pairs. {1, 3} — adds 1 {n-1, n-2} — adds n-2 {0, n-3} — adds 0 {2, n-4} — adds 0 so we used first 4 and last 4 values, and every pair can be matched in a usual way.

Hint: you don't need to check if a certain interval $$$[x, y]$$$ is valid for subarrays individually, but you can check for the entire array directly.

Hint : If you have ceil((n+k)/2) elements in the range, you can create such k partitions satisfying the condition. After this idea, it's just binary search for finding the range and then partitioning into subarrays.

I was looking forward to it! So sad now :(

I think D is easier than A. The trick in D is too obvious (at least for me).

I don't know much C++, but the most common mistake that I know of is forgetting that after you perform the operation, elements right after the ones you just changed might already be equal to the target. Checking this condition requires a while loop.

It was "n 0".

EDIT: I guess it was "n 0" "n n-1".

your code fails for

1

8 7

as there is a possible answer

7 6

1 5

0 2

3 4

If we can invert a range $$$a$$$ and a range $$$b$$$, then we can invert any range $$$a-b$$$ (works thanks to $$$a,b \le n/2$$$). That gives Euclid's modulo algorithm. We can invert any range $$$g = gcd(B)$$$.

It's easy to see that we can then invert any two elements whose distance is multiple of $$$g$$$. We get $$$g$$$ groups, in each group we can change the number of negative elements by $$$2$$$ so it can be forced to be $$$0$$$ or $$$1$$$.

The above uses an even number of operations so two cases arise depending on the parity of number of operations applied. The rest is simple implementation.

The example for n=65536, k=65535 would be (65535, 65534), (0, 1), (2, 65532), (3, 65533). The rest are just paired so that their sum is 65535.

if (k==n-1 and n!=4), the two pairs which will sum up to k will be (n,k-1) and (k-2,1) and for the rest of the pairs you have to make their & 0.

when n>4 and k==n-1 you can find it by simply (n-1)&(n-2) , 1&3 , 0&(n-1-3) and rest as i&(n-1-i). But if n==4 and k==n-1 it is impossible. Hope you get it;)

Yes, statement says we can assume that such a case doesn't happen. There's nothing we can do if it does, after all — the expected number wouldn't be well-defined. It's always possible to switch to sum over all distinct permutations (or to floats), though.

I figured out the edge case for k=n-1 , but still get WA on pretest 2. I even checked myself for various cases like 16,0 16,15 and so on and was getting the right answer. If anyone can help figure out the problem I'd be grateful. My solution if(4,3) then -1, if(n,n-1) then pair (n-1,n-2)(all but 1 is missing now) 1,3(to add the 1) then 0,n-1^3 and rest i,i^n-1. But I'm still getting wa on pretest 2. Please help

int q;
cin>>q;
while(q--){

    inte n;
    cin>>n;
    inte k;
    cin>>k;
    n--;
    if(n+1==2){
       if(k==0) {
         cout<<0<<" "<<1<<endl;
       }
       else cout<<-1<<endl;
    }
    else if(n+1==4){
       if(k==3) cout<<-1;
       else if(k==0){
           fr(i,(n+1)/2){
             inte temp=i^n;
          //if(i==0||i==k||i==k^n) continue;
          cout<<i<<" "<<temp<<endl;
         }
       }
       else{
         fr(i,(n+1)/2){
             inte temp=(i^n);
          if(i==0||i==k||i==(k^n)) continue;
          cout<<i<<" "<<temp<<endl;
         }
         inte z=k^n;
         cout<<0<<" "<<z<<endl;
         cout<<k<<" "<<n<<endl;
       }
    }
    else{
       if(k==n){
         fr(i,(n+1)/2){
             inte temp=(i^n);
          if(i==0||i==1||i==3) continue;
          cout<<i<<" "<<temp<<endl;
         }
         inte g=(n^3);
         cout<<0<<" "<<g<<endl;
         cout<<1<<" "<<3<<endl;
         cout<<n<<" "<<n-1<<endl;
       }
       else if(k==0){
           fr(i,(n+1)/2){
             inte temp=(i^n);
          //if(i==0||i==k||i==k^n) continue;
          cout<<i<<" "<<temp<<endl;
         }
       }
       else{
           inte h=(k^n);
         fr(i,(n+1)/2){
             inte temp=(i^n);
          if(i==0||i==k||i==h) continue;
          cout<<i<<" "<<temp<<endl;
         }
         cout<<0<<" "<<h<<endl;
         cout<<k<<" "<<n<<endl;
       }
    }

}

will you please share the approach of problem D?

Same after two WA :)

The procedure was to find x,y and then partition the array in k parts. 1. If x,y satisfies the constraints of the problem, then x,y+1 too, and if x,y don't satisfy the constraints, then x,y-1 also won't. This gives an idea to binary search on y. 2. So we iterate over x, binary search on y, and then we get our optimal x and y.

Notice that once we get our optimal x and y (call them ansx and ansy), the following relation will hold — no of elements outside [ansx, ansy] + k <= no of elements inside [ansx, ansy]

So to partition the array, following greedy strategy works — First partition array in k-1 parts so that count of excluded == count of included-1, then assign the remaining array as last partition. The last parition will also satisify the constraints of [ansx, ansy] because of the relation mentioned above.

F is cool, but I mean, it is just a slight variation to the very well known problem of determining the biggest antichain in a poset. It is fine for a Codeforces round, but I personally would definitely not consider it among the best problems

I agree with the fact about F, it's one of the best problems I've seen so far.

I'm not sure how your solution exactly works, so it'd be great if you could explain the reduction to bipartite matching. (I noticed that you used bipartite matching since yours was one of the fastest solutions in contest).

My (out of contest) solution consists of noting that if the edges were directed, then you need to avoid paths of length 2 (it is necessary and sufficient to avoid an odd cycle). To do this, we can construct a network with 6 layers (first and last layers being the source and the sink), with $$$n$$$ vertices each in the remaining layers, and the edges between layers {1, 2}, {3, 4} and {5, 6} corresponding to vertices in the original graph, and edges between layers {2, 3} and {4, 5} corresponding to directed edges. Then using the vertex version of Menger's theorem we can see that the max flow in this network is the number of vertices we need to remove (since each path from source to sink passes through all the layers).