Awesome editorial and even awesome questions. After this round, I feel like practicing more now.

I really liked this contest. All problems between A and E are well-balanced. They are not almost ad-hoc, and they are not stupid realization. Ideal balance! Thanks for this round!

thanks for blazing fast editorial. Loved the problems <3

For problem C This is a classical dynamic-programming task with a twist. Which task does this refer to?

it fits easily in the time-limit. it doesn't...

Anyone wasted an hour in B?

In parallel universe.

If $$$a=b+1$$$ and $$$b$$$ is even, then $$$a^b=1$$$.

In Hint $$$4$$$ of the first solution of problem $$$E$$$, maybe it should be $$$a\oplus b=1$$$($$$\oplus$$$ denotes xor)...

Also in Hint $$$3$$$ of the second solution, it should be $$$2^{19}$$$ but not $$$2^19$$$.

Many of them could have got ac on D if it were 2*n steps,lol. By the way,thanks for a great contest.Liked it. Thanks for strong pretests

Me :Could only solve one, feeling low...

Also Me : After reading the overview of problemset...I am glad I solved A.

This is peak editorial writing. From giving some extra time to the ones who were really close to getting AC on H to writing multiple hints for us to be able to figure out the rest of the solution by ourselves. Great work dude!

Thanks for the awesome Tutorial keep it with hints its such a good way of learning and explanation :D !

The way of presentation of the Editorial is very Nice. Going through the Hints before The Actual Solution really helps in learning. I request all editorial should be posted like this (Hints and Then solution).

I have lost more than 200 rating points in the last 3 contests, Don't really know what's happening :/

Great format for the editorial! Loved the bunch of hints before the elaborated solution. Thank you!

it would have been better , if the editorials were given with the problems in the contest.

Here are video solutions for A-E, as well as complaining about gaining rating (apparently)

sorry for such a silly question but why am i getting TLE here? 95114705 I tried to form all possible permutations coz the constraints were very small. But still i got TLE. If anyone got time a slight help would be great. Thank you. Have a good day

Can anyone tell why my solution is incorrect for Problem — B ( Chess Cheater )? My approach :

Step 0: Find the initial score and store it in variable sum
Step 1: Find all contiguous Loss substrings and store 
        (length,0) if the substring is not a prefix/suffix 
        (length,1) if it is a suffix/prefix
Step 2: Sort the vector in increasing order, putting prefix and suffix substrings at the end
Step 3: iterate for elements in the sorted vector ( for i=0;i < it.size(); i++ )
        if( k >= it[i]) // meaning we can change the whole interval 
            sum += 2*it[i] +1 if the i'th substring of L's is not a suffix or prefix
            sum += 2* it[i] if i'th substring of L's is a prefix/suffix
            k -= it[i]
        else if( k < it[i] ) // this is the last substring we can change, and we can't change it fully
            sum += 2*k 
            k=0;
Step 5: cout<< sum <<" \n" 

Link to submission : Can anyone point out the mistake kindly? Thanks in advance :)

C was much harder than D for me.

Nice editorial! It would be great if we can have hint on all the future editorials! (but that would be time consuming for the writer)

Great Set of questions. Even the editorial in this format is very informative and help in logic building.

This is the toughest round for me so far.

There is an elementary solution to E which does not use Bezout's Theorem.

For B, I used the idea of finding the contiguous substring with maximum consecutive Ws by performing at most k flips(where a flip is from W to L, L to W). Then I would calculate the winning score. I am getting the wrong answer on pretest2. Can somebody help me find out what's wrong with my solution?

Here is my code — void solve() { cin >> n >> k;

string s;
cin >> s;

vi A(n);
fo(i,n){
    if(s[i]=='W')
        A[i] = 1;
    else if(s[i]=='L')
        A[i] = 0;
}

// Now I find the contiguous substring with maximum consecutive 1s by doing at most k flips.
int l=0, r=0, maxLen=INT_MIN, maxL, maxR, c=k;
for(r=0,l=0; r<n; r++){
    if(c<0){
        while(l<=r){
            if(c>=0)
                break;
            if(A[l]==0)
                c++;
            l++;
        }
    }
    else{
        if(A[r]==0){
            c--;
            if(c<0){
                r--;
                continue;
            }
        }
        if((r-l+1)>maxLen){
            maxLen=r-l+1;
            maxL=l;
            maxR=r;
        }
    }
}

int ans = 0, j = maxL;
if(maxLen!=INT_MIN){
    while(j<=maxR){
        A[j] = 1;
        j++;
    }
    fo(i,n){
        if(i==0){
            if(A[i]==1)
                ans++;
        }
        else if(i>0 && A[i]==1){
            if(A[i-1]==1)
                ans+=2;
            else
                ans++;
        }
    }
}  

cout << ans << endl;

}

hence I will leave them a couple more hours to try getting AC

https://mirror.codeforces.com/contest/1427/submission/95152627

It turns out my problem was that I was simply losing too much precision when considering escaping through a very close point :(

Knowing that my answer is actually bigger than the correct one was enough to find the issue immediately.

Thanks for the contest!

In the question C... I tried a code with dp approach but with some restriction (difference of index). It passed all the test cases.

But for this test case my code outputs 0 but the answer should be 1.

500 2

100 50 60

2100 500 500

Are the test cases of C weak or Am I wrong somewhere?

Submission link:- https://mirror.codeforces.com/contest/1427/submission/95152766

In problem C, I thought that R in the input is useless then tried solving the inequality tj — ti >= |xj — xi| + |yj — yi|, (tj > ti) to solve the problem in n*log(n) time but didn't come up with the solution, is there any such faster solution possible?

My solution for problem G seems to be a weird modification of the standard solution.

I do binary search on the candidate values, run min-cut, then divide the vertices into two halves. Thus there will be $$$O(\log n)$$$ layers, each consisting a total of $$$O(n^2)$$$ vertices and edges. The complexity will be $$$O(n^3\log n)$$$. (Since Dinic's algorithm works in $$$O(E\min\{E^{1/2},V^{2/3}\})$$$ on networks with unit capacities)

Difficulty of 'B' should not be less than 1500

Another deterministic solution of E:

Step 1: Let $$$p \in N$$$ be the unique number such that $$$2^{p-1} < x < 2^{p}$$$. Write $$$2^p x$$$ and $$$(2^p - 1) x$$$ on board with $$$O(p)$$$ operations.

Step 2: Write $$$(2^p x) \oplus ((2^p - 1) x) = 2^{p+1} - x$$$ on the board. Then, write $$$x+ (2^{p+1} - x) = 2^{p+1}$$$ on the board.

Step 3: We can write $$$2^i$$$ for all $$$i \ge p+1$$$ on the board. Write $$$2^p$$$ by using xor operations for all the bits of $$$2^p x$$$ except $$$2^p$$$.

Step 4: Write $$$(2^{p+1} - x) \oplus (2^p) = (2^p - x)$$$ and repeat the steps with new $$$x = (2^p - x)$$$ while $$$x \ge 1$$$. New $$$p$$$ of new $$$x$$$ is strictly smaller than current $$$p$$$, so it repeats at most 20 times.

Can dynamic programming in Problem C be done with recursion and memoization? If yes, how? Please help.

Problem D is actually very easy if you realize the operation is same as reversing each deck individually and reversing the entire array. Since you can fix the reversing of the entire array with one operation, the problem is reduced to "sort an array with at most N subarray reverses", which is easy

In the editorial for problem A, it's conjectured that a random shuffle works with probability at least $$$\tfrac1n$$$ (assuming the sum of all the numbers is nonzero). This is true, and here is a proof. The key claim is that, given any shuffle, some cyclic permutation of it works. This easily implies the desired result.

Suppose that the claim is false for some shuffle $$$a_1,\ \dots,\ a_n$$$ (so $$$a_1 + \dots + a_n \ne 0$$$). Interpret all indices modulo $$$n$$$. Since no cyclic permutation of this is valid, for any $$$k$$$, there exists some $$$f(k)$$$ such that $$$a_k + a_{k+1} + \dots + a_{f(k)-1} = 0$$$.

Thus, we have a function $$$f$$$ on the integers modulo $$$n$$$. (Formally, we have $$$f\colon \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$$$.) Thus, this function has a cycle, say $$$t_1 \to t_2 \to \dots \to t_k \to t_1$$$.

This gives us the $$$k$$$ relations $$$a_{t_1} + \dots + a_{t_2-1} = 0$$$, $$$a_{t_2} + \dots + a_{t_3-1} = 0$$$, $$$\dots$$$, $$$a_{t_k} + \dots + a_{t_1-1} = 0$$$. Summing these all up, we get $$$c(a_1 + \dots + a_n) = 0$$$, where $$$c$$$ is the number of "revolutions." Thus $$$a_1 + \dots + a_n = 0$$$, as wanted.

I have a straight forward solution for E with no randomization or coprime numbers required.

Let k be the MSB of x. Notice that we can get 2^n * x for all n by adding x to itself and then repeating. Now, for any number on the board y, we can set all bits >= k equal to 1. We can do this by xor-ing 2^n*x to set each bit above k if it is not set for some appropriate n. So we just need to find two numbers for which, after setting all bits >= k to 1, all of the bits below k are the same, except the 1 bit. We can just check the first 3e6 multiples of x (no randomization required).

Submission: https://mirror.codeforces.com/contest/1427/submission/95156859

I solved problem C the way you suggested and thought that 2rn = 10^8 will not fit so I didn't implement it...
Did this happen to anyone else?

95127605 I used random_shuffle for problem A because the constraints were small whereas everybody else used sorting. Is it my luck that my submission got accepted? Also, what are the chances that my solution won't work?

For E, I had similar solution to the gcd one, but the step of finding a co-prime pair is randomized. It randomly generates new numbers until it finds a co-prime pair. It too completes in $$$\le 100$$$ operations. 95149535

one of the best editorial. Loved it!!

if it is possible, try to keep hints option in every editorial .. it is so beneficially for a newbie like me :)

I like the solution to E with bezout theorem very much! Thanks for fast editorial.

Could you check pls what is wrong with my solution for C (WA15)

cin >> k >> n;
vector<pair<ll,ll>> v(1e6+1, {-1,-1});
v[0] = {1,1};
for(ll i = 0; i < n; ++i)
{
    cin >> t >> p >> q;
    v[t] = {p,q};
    m = t;
}
vector<ll> dp(m+1, 0);
sum = 0;
for(ll i = 0; i < m+1; ++i)
{
    if(v[i].first == -1) continue;
    if(i-k*2 > 0)
    {
        sum = max(sum,dp[i-k*2-1]);
        dp[i] = max(dp[i], sum+1);
    }
    for(ll j = i+1; j < min(i+k*2+1, m+1); ++j)
    {
        if(v[j].first == -1) continue;
        if(j-i >= abs(v[j].first-v[i].first)+abs(v[j].second-v[i].second))
        {
            if(dp[i] || !i) dp[j] = max(dp[j], dp[i]+1);
        }
    }   
}
mx = 0;
for(ll i = 0; i < m+1; ++i)
{
    mx = max(dp[i], mx);
}
cout << mx;

I stupidly misread the constraints for D, and even more stupidly called my results vector in the solution "omgconstraints", as a way to punish myself for not reading constraints, by typing that name like 50 times. Given that my successful submission for D was 10 seconds before the contest ended, I cursed myself every time i typed "omgconstraints" rather than the usual "res" that I use. Had I known that these extra letters might have pushed cost me the problem, I would have definitely thought twice.

Hey, I have some problems with B.

Just Have a look at this test case and tell me how's the answer for this test case is 16.

1

12 2

WWLWLLWLWWWL

Ans:- 16 I think the answer should be 15

In problem C.Who can explain completely Hint 3 ?

Based on this contest, I believe that dario2994 is one of the best problemsetters on CF. Would love to see another contest from you!

Can someone explain step1 of the deterministic solution of Problem E . Particularly this line :- y=(2ex)^x=(2e+1)x−2e+1 and therefore gcd(x,y)=gcd(x,2e+1)=1

Who is an "experienced participant" in your view dario2994?

Hi, Can anyone help to understand why my solution of problem D works. Here is the link to solution : SOLUTION

Approach: I am counting the number of operations from 0.

When the parity of number of operation is even : In this case I select subarrays staring from first element till the elements are in decreasing order. When I find an element that is bigger than previous element, I stop and considers the chosen elements as a split. Now I start fresh from this element and repeat this process until I have some k splits. Now I perform the operation on them.

When the parity of operation is odd, I am doing the same process except I chose subarrays that are strictly increasing.

For example : Input:

5

4 2 1 5 3

Output:

2

3 3 1 1

4 1 2 1 1

Given 4 2 1 5 3:

Operation 0 : Parity = 0

We split as (4 2 1) (5 3)

New array : 5 3 4 2 1

Operation 1: Parity = 1

We split as (5) (3 4) (2) (1)

New array : 1 2 3 4 5

We get the sorted array.

I am not able to prove why this works. I saw this pattern during contest but forgot about the case that k should not be equal to 1. Is this same as the approach given in the editorial intuitively ?

This is what I did in problem D.

Idea: for 1<=i<n we get i and (i+1) adjacent keeping everything else(less than i) adjacent. (Similar to the editorials idea). Hence in at most n-1 moves we can get the array sorted and 1 extra move if the array turns out to be descending.

So let us say we have first i numbers sorted(descending or ascending). We have 4 possibilities.

The indicated boxes are how we can achieve our idea.

After this the code is fairly simple.

As asked by the dario2994, I have some feedback to offer. Some of the below points are for the a part of community who miss no chance to rant the organisers. So here we go.(expecting a lot of hate from those who can't agree diverse thought process)

What I loved about the contest:

1. The contest in general was awesome. It was one those contests that kept me thinking about the problems for the entire time rather than reaching a point where one realises that later problems ain't their cup of tea. (Kudos for this because such contests are rare to find).

2. The contest had a vast range of problem. Many people are of the view that contest was filled with ad-hoc ones, but I beg to differ. I think we can call these problems as non-trivial/non-standard rather than ad-hoc. (I know lot of people would disagree to this)

3. The contest is an excellent example where the problem statement are not exactly short yet very interesting to read. I can't stress enough that length of problem statement doesn't matter as long as the description is to the point and doesn't make things messy to understand. As for me, I didn't loose interest in reading any statement and I read all of them (yes all until H) even though I knew I wouldn't be able to solve them realistically.(I expect most hate for favouring the length of problem statements).

4. The contest had excellent sample cases. I can bet that without such samples a lot people would have had series of WA on pretest for question B.

5. The contest had really high quality problem (even though I couldn't solve many problems doesn't take away the fact). I would genuinely like to appreciate the quality of the problems and beautiful ideas behind the solutions.

What I think could have made contest more interesting:

1. I believe that scoring distribution could have been better than what it was. Of course this point applies iff one is able to solve problems else it is irrelevant. But I strongly believe that scoring can be made better by comparing the problems within a contest (and not with other CF rounds) relative to each other. I liked the math the errichto proposed to the author in one of his comment but I also understand that it is very hard to gauge the exact difficulty of problems just from handful of testers and that the actual round can have variations to this. I think that this round could have had been relatively high scoring (by increasing the point of C and onwards problems) or could have been low scoring (by decreasing the points of A and B). All I am trying to convey is that scoring could have been better distributed.

But overall, I'd place this contest in top 10-15 of all I have appeared in (appx 200 or more across various platforms). I'd sincerely appreciate the hard work of author and coordinators for making such a nice contest.

So we are basically optimising $$$ O(n^2) $$$ dp solution for Problem C. My question is how do we optimize it if there is no $$$ \triangle{t} \ge 2\cdot{r} $$$. Won't it run on $$$ O(n^2) $$$ and give a TLE. Or am I missing something out? Thanks and Great Round.

Edit :

Got it. $$$t(i)<t(i+1)$$$ that limits maximum iterations to $$$2r$$$ and complexity to $$$O(2nr)$$$.

I did come up with the $$$O(nr)$$$ solution for 1427C - Тяжелая работа папарацци, but I thought it would not fit into the time limit :(

I use another optimization in problem C and also get accepted: 95139974 My brief idea is using ans[i] to store the maximum photos can be taken when we already at i'th celebrity. We iterate from ans[n] to ans[1]. For each ans[i], instead of iterating all celebrities in [i+1, n], we use a map to record the ans[j] (j in [i+1, n]) in descending order, so we can just take the first celebrity that satisfies $$$|x_i-x_j| + |y_i-y_j| \le t_j-t_i$$$.

For problem C, is it possible that two consecutive celebrities appear at the same intersection?

My solution for E:

• try various inputs, bruteforce and print some shit to get an intuitive understanding
• notice that the worst case is when $$$X$$$ is a simple binary palindrome 1000...1 and we need to create numbers approx. up to $$$X^2$$$ then
• we want to generate a smaller (than $$$X$$$) number $$$Y$$$; if it's even, we can remove the largest 1-bit from $$$X$$$ using it, and if it's odd, we can solve recursively for $$$Y$$$ (there's the operation limit, but this recursion turns out pretty fast)
• this seems to work for the palindromic case: try XORs of $$$X$$$, $$$2X$$$, $$$4X$$$ etc. up to $$$2^k X$$$, for each $$$2^k$$$, pick one of these (denoted by $$$A$$$), then $$$B = A \oplus X$$$, then create $$$(A+B) \oplus (2A)$$$ or $$$(A+B) \oplus (2B)$$$, and it turns out to be smaller than $$$X$$$ for a good choice of $$$k \le 20$$$
• bruteforce check if it gives $$$Y \ll X$$$ for each $$$X$$$
• it works and any odd $$$Y$$$ is around 2 times smaller than $$$X$$$! implement

I don't want randomised solutions because they carry a risk, but my thinking here is way more random. I have no idea why this works.

I like problem D. And I believe I'm producing nicest solutions out of all solutions I've looked at. :) 95384262

Anyone able to provide proof as to why we only need to consider 4r consecutive celebrities ? I'm not able to figure it out as I think, as said in the editorial, any element past the 2r point will be a compatible point. What different happens at 4r ?

Thanks in advanced!

the author was playing jailbreak on Roblox when he was thinking about the last problem.

I have an alternate solution to problem E: doesn't use any number theory theorem.

First of all, let's assume the number we have ends with $$$01$$$ and not $$$11$$$. If it ends with $$$11$$$, we can XOR it with its double and make it end with $$$01$$$. So we start from a number ending with $$$01$$$ : lets say we start from $$$x$$$.

form a number $$$c$$$ which is $$$x$$$ shifted left $$$k$$$ number of times, where $$$k$$$ is the bit length of $$$x$$$.

Then we XOR : $$$x+c$$$ and $$$x \oplus c$$$.

Hence we get a number $$$d$$$ which is a pure power of $$$2$$$, and is the smallest power of $$$2$$$ which is greater than $$$x$$$.

Now we will use this number $$$d$$$ to remove the highest bit of $$$x$$$: Keep multiplying $$$x$$$ by $$$2$$$, and whenever we have highest bit of $$$x$$$ and $$$d$$$ colliding, XOR them. Do it until only one bit in $$$x$$$ remains. Because $$$x$$$ ends with $$$01$$$, we get a power of 2 which is less than $$$d$$$. Use this to chop off the highest bit of $$$x$$$.

Keep chopping off the highest bit of $$$x$$$ until we get $$$1$$$.

Code