Man, who thought that blue color for a t-shirt would be a good idea??? Even black color would have been better!

E was a good problem. F was good too. Overall a balanced and good problemset!

Are there any updates on the t-shirt distribution? Haven't got any email regarding this.

I hate C. How hard was it to find the d values :(

Where do I get the update for the t shirt?

I absolutely hate these kinds of editorials, where the solution to a problem is written in 4 lines like — oh we can do this for the solution, then do that, then do this greedy approach which we won't explain how it is correct, and then finally find answer with some random data structure which we won't bother to implement. You might as well don't write the editorial please, it will make no difference.

You guys need to understand that a person who comes to the editorial, is expecting a detailed solution with good explanation, so that he/she can learn the idea behind it and use in future problems, and not a 4 line paragraph where half of the things are just written without any proofs or anything. Random people posting explanation in discussion thread are far better than these stupid editorials.

I think E was too easy to be a Div 3 E. Loved solving F1. Thought F2 was on similar lines of F1 but it was actually way more difficult. Overall a nice problem set!

Problem A — Simple sort and binary search.

Problem B — Note that 1st element can only be modified by operations on element 2. Accordingly iterate over the array, simulate the operations on each, and check the last 2 elements for 0. In any case, element value goes < 0, answer is not possible.

Problem C — Simple substring search. First, count for mapie (requires only 1 operation). Then check for rest of the possiblities (pie, map).

Problem D — Let dp(i,j) represents whether all the m turns result in player j having the ball, if we are at move i and currently player j has the ball. Do a simple recurive dp, and final answer is the count of dp[i][m] == 1 over all i players.

Problem E — For each row, let dp(i) represent the min. cost to place supports, such that we place a support at a[row][j]. dp(i) can be calculated as min j from i-d-1 to i-1. Use segment tree to speed up this calculation. For every row, cost for that is dp(m). Final answer is a subarray of size k with minimum sum, that can be done using simple prefix sums.

In E, how can you say that the sum is a convex function?

Can someone explain the editorial of D in more detail?

I could only think of a bruteforce solution to D.

Took so much time for C, couldn't even think about D much. How to solve D?

I solved problem B easily but couldn't solve C. Don't know whether to feel sad or happy about this.

I found F easier than E. The time limit of 6 seconds on E allowed my O(q*1000*logn) solution to pass.

In editorial of problem D, what is the "another case to work"?

D was absolute best!. Couldn't solve it but enjoyed thinking about it. Same for C.

Another Div 3 which I'm going to downvote. Authors think that they are preparing problems for Div 2.

D — good idea but shit ton of implementation.

E — couldn't solve but I think it's some casework which I absolutely hate, hence didn't bother.

Also, C = https://codeforces.me/contest/1462/problem/C. wtf?

How to do E? My idea was to consider every chip as the last remaining chip, then to calculate answer by considering that the chips in the same row will just move towards the selected chip, and chips in the other row would first go towards the cell directly above the selected chip and then in 1 move, move downwards to finally become 1 chip. Am I missing something?

But the algorithm I mentioned will give the correct answer, no?

My idea for F — Find the path from x to y. Let the path array be composed of nodes u1, u2, u3 ... ul, where u1 = x and ul = y. Then for every u, do a BFS considering u as the root, and store the distances in a array dis. Then the answer is length of path + 2*(sum of all distances of mentioned k nodes). But it got WA on test 2. Am I missing something?

Submission

I think there is a typo in editorial for D. For the line

Otherwise, we delete an occurance of ai in S and decrement j. If we cannot find ai in S, it is impossible to transform b to a.

Instead of decrement j, it should be decrement i.

I went rainboy mode in this contest.

• I couldn't solve A. Felt that it was misplaced, or maybe I'm just not good in solving constructive problems.
• B idea was nice. Implmentation was also okay.
• I got the idea for C 5 minutes after contest ending. A good problem in my opinion.

C is the one of the worst questions I have seen in a while. The last paragraph of the problem is so confusing, even looking at samples didn't help. I had the idea in 5 minutes, but took 4 WA's on test 1 just because the output formatting is wrong. Also, what does this line have anything to do with anything?

The order in which you output the endpoints of a segment is not important — you can output the index of the left endpoint first and then the number of the right endpoint, or the other way around.

This just makes the problem even more confusing. And lastly, would it kill you guys to give the initial points as sorted? So much extra implementation just to print the indices of the points in original order after god knows how many times I used sort().

On the other hand, the problem itself and the idea behind it is nice. I just don't like the fact that I have to spend 10 minutes on thinking about the solution + implementations and then 30 minutes to properly format the output just so that it passes samples.

Can someone provide a proof of how Div 2 D has time complexity of C log C according to editorial?

Was the idea of E something like this —

1. Make a undirected graph according to input.
2. If graph is not bipartite, print NO.
3. Else, make another directed graph such that for each edge [u,v] in input, make an edge u -> v if [u,v] is of type 1, else make an edge v -> u.
4. If there is a cycle in this new directed graph, print NO.
5. Else, do a topo sort and give coordinates to each node in order they appear.

D was a nice question. 0-1 Knapsack DP hidden behind a good observation — max operations on any index i can be atmax 12. So if k>=12*n, ans would be sum of array c otherwise apply standard DP for 0-1 knapsack.

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.

Am I the only one who initially thought for Div2 C, the answer is -1 for k=n-1, then after 2 WA's realized it is only for n=4?

PS. Div2 D was a nice question!

I declare myself the dumbest person on this planet when I realized after 40 mins that string of length 1 is always a palindrome, so you only need to handle strings of length 2 and 3.

After giving this contest, I have a feeling that my 2022 won't be going well either.

In editorial of C,

To find the set of such nodes, we can run DFS from the player with maximum ai.

Why only ai? Don't we have to take maximum bi also?

My recursive binary search solution passed (https://codeforces.me/contest/1613/submission/137671370).

For me, A > B and D > E. In other words, I felt E was easier than D and B was easier than A. Although A was easy too, just some bit of implementation.

I think that the authors of this contest need to be reminded that this is a Div 3 round, not a Div 2 round. Div 3 should be ideal for beginners/newbies, this round certainly wasn't.

Why in C we do we need to go to the deepest subtree? Why can't we take any subtree whose xor is x?

When I solved A and B under 15 minutes, the round gets unrated. Of course, why not :(

Can someone give some strong test cases for D? I thought of every test case I could and stil couldn't figure out the bug in my code.

Can someone explain me how to do this part in the solution of 1558B?

We can achieve that by preparing a sieve of Eratosthenes, factorizing x and generating all its divisors.

Div2 B was a nightmare for me.

E was MUCH easier than F1. Damn caseworks in F1. Everytime I got WA, I discover a new casework.

operator precedence

Contrary to popular belief, I liked problem C. A good question based on bit contribution and combinatorics.

I hate div 2 C.

I swear I'll never give any writer's first contest.

I regret giving this contest :)

How in problem C1, the dp does not depend upon the actual potions taken? I mean, how can I calculate ans for dp[i][k] without knowing what is my current health?

Can anyone tell why this code is giving TLE on test 125?

My Submission for C got TLE on pretest 3. Afterwards, including fast I/O and changing for(auto x:s) to for(auto &x:s) ,it got passed. How?

A great and well balanced problem-set. Also, C was a nice question, although it took me an hour to implement it and fix bugs :(.

Getting a +150 increase and seeing contest becoming unrated hurts :(

How to change handle?

What an absolute stupid contest! No thinking, no DS, nothing. Just some stupid observations and you're good to go. Why do you even frame these type type of problems? Just say like — Print numbers from 1 to n. It will be a lot better to solve. Seriously, even Leetcode contests are better than these contests, atleast they require some thinking and implementation, and DS. But here, just put some if-else conditions in problem D which is supposed to be a good problem, and you're done! Absolute waste of time and effort.

What a stupid contest !