Thanks for quick editorial.

This is hard :(

B solution: should it be $$$a_i \gt a_{i-1}$$$?

Why I am getting WA on test case 4 in problem C. 119395523 . I used dfs and printed 2^(connected comp).

in question B editorial it is mentioned that

"observe that decreasing a column will never affect whether it is optimal to decrease any other column, so we can treat the operations as independent."

Why they are independent, Why it will never affect other columns?

I tried a different approach for D, which I am not able to prove. So it would be great if someone can have a look and either prove or disprove it.

Nice problemset. "Lost Problemset"

जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।

Nice questionset.

So interactive :D

119391919 Can someone please tell me why I'm getting TLE in problem C?

liked the beauty of problem D, great job!

For E, I think we can also do greedy:

First, if $$$n$$$ is odd and $$$k$$$ is even, we can never win.

Notice that two moves always results in even number of bits flipped. So if $$$n$$$ is odd and $$$k$$$ is odd, then we will have odd number of moves, so start by turning on some $$$k$$$.

Now we are left with turning on even number of $$$0$$$ bits.

Let's denote $$$action1$$$ as turning on some $$$k$$$ bits using one move, and $$$action2$$$ as using two moves to turn on $$$x$$$ bits, where $$$x$$$ is even, and $$$2\le x\le min(2k, 2(n-k))$$$.

If $$$action2$$$ is unavailable(there are no possible values for $$$x$$$), and our current number of zeros is not divided by $$$k$$$, we lose.

Otherwise, if $$$k$$$ is odd we can just do action2 greedily, and if $$$k$$$ is even, before the greedy, we might need to do a single $$$action1$$$ (this is easy to check).

Code: 119401441

Kinda different solution to E. I'm sad, tired, and hopelessly hardstuck, so this is the short ver

The answer is NO iff $$$n$$$ is odd and $$$k$$$ is even. The if part is true because we can't distinguish between any two arrays $$$a$$$ and $$$b$$$ such that for all $$$i$$$, $$$a_i \oplus b_i = 111111...$$$.

Let's show that it's possible otherwise. The case where $$$k$$$ divides $$$n$$$ is trivial.

Consider all other cases except for ($$$k$$$ is odd, $$$n$$$ is even, $$$2k$$$ > $$$n$$$). We can greedily form segments of length $$$k$$$ until there is an even number (let this number be $$$r$$$) of elements remaining such that $$$r \lt 2k$$$. It takes $$$2$$$ more queries to solve the problem. We can show that this is optimal via a parity condition.

In the case ($$$k$$$ is odd, $$$n$$$ is even, $$$2k$$$ > $$$n$$$), we can set $$$k = n - k$$$ and solve the problem as in the former case, except that we query the complement of things. Pretty sure this is provable (the problem becomes strictly harder if you're given the complement xor, and you can solve it in the optimal number of moves in the equivalent easier version), but my head is foggy :/

I think solving it this way is very impractical tho, the bfs solution should be the "correct" one to think of during contest

Can someone explain why my O(N^2) solution give TLE in problem D? My Submission

I am not sure if the my approach itself is accurate, but still O(N^2) solution must not be giving TLE.?

Thanks.

Please, someone, explain 2nd problem, Thanks :|

Benq orz.

I really enjoyed the round, I think it was well balanced.

I wonder why so many contestants including me got WA on F1. And my solution is similar to toturial's (using strongly connected components) . That confuses me. (Ahh...I spend more than an hour during the contest on debugging my F1 code!!!)

Here is my submission

Can somebody provide some details to be careful on F1? Or some special test cases?

is it possible to get different verdict in pretest and submission?

Can anyone please tell why i am getting wrong answer on pretest 2? 119361708

Please can anyone tell me what does "set" mean in "bipartite set" in problem D?

what are the Algorithms i need to learn so that i can consistently solve A and B problems Ps: newbie:)

In problem E does d, the maximum no. of queries also varies with n and k? I thought we just have to make it within 500 queries irrespective of n or k. T_T

One of the best Editorial for Problem E. Lost Array, I could find on the net is this one by gotexans, Solution for Lost Array (E).

In problem D, sample test case 2. How can we tell for sure after just one query? It's given the tree is

? 5 gives 2 2 1 1 0. So can the tree be not like this?

Update: Got the wrong case:

What's wrong in my code 119358197 ? got Wrong Answer test case 4. my logic was exactly same as editorial .

Did anyone solve problem C using maths, like a single formula or something?

Can anyone explain intuition behind hint 4 for problem D

The min(number of black, number of white) nodes is ≤⌈n/2⌉.

why can't it be <=floor(n/2) symbol? any counter example? UPD: problem solved, the editorial is updated.

In problem B why it is not optimal to reduce the height of a[i] a[i]>a[i+1] when i==0

consider case n=2 5 1 initally ans = 5+4+1

1 1 now ans = 4+1+1

or I missing something.

https://mirror.codeforces.com/contest/1534/submission/119444809

Any ideas why?

The hints before the solutions are very helpful . I think every editorial should have hints .

I think my solution for D seems more creative/easy because you dont need any experience with standard/similar problems, so I am putting it here

So we will root the tree at 1 and evaluate parent for each node.

first we will ask for depths (i.e. distances from 1), and for all nodes with depth 1 we will set 1 as their parent

Now, let's iterate over all nodes in increasing order of depth.

Whenever we encounters a node (let's call it r) without a parent assigned we will make a query with r, and set it as a parent of all nodes with distance 1, except one which already had a parent, let's call it p. Now take r and other nodes which have a dis of 2 with r and same depth as r, set p as their parent.

Proof:

Let's ignore 1st query and node for simplicity

Note, for each node that we made a query with, we skipped at least 1 node (obviously its parent) 
above it...

also notice that each node is covered by at most 1 of its children (analyze the last operation).

So, chosen <= skipped   // ignoring 1st node/query

in the worst case chosen = skipped,
 total_nodes = chosen + skipped + 1 = odd number // added 1 for node 1
 chosen + 1 == ceil(total_nodes/2) // added 1 for 1st query to LHS

code

I only had a blurred picture of it in the contest :(

Please correct me if something was wrong, and also feel to ask.

I wasn't able to take this contest, but I just did a virtual and I have to say — These problems were brilliant! They were unique, easy to understand, and not too complicated to implement (even F1, if you just look at the solution, it seems complicated, but it's really not).

My solution to E was much more direct than using BFS. The first observation is that each query just gives you a linear equation (mod 2) containing $$$k$$$ of the variables. Then, in order to find the XOR-sum of everything, it's necessary and sufficient to make some queries such that a linear combination of them is the desired XOR-sum. In particular, because we're working mod 2, the coefficient of each equation is either $$$0$$$ or $$$1$$$, and we can just not query the 0's, so we need exactly a set of queries such that the total XOR is the XOR-sum. In other words, we need to query each variable an odd number of times.

Now, the problem is much simpler: first, consider a number of queries $$$d$$$, so that we will make exactly $$$d$$$ queries each with exactly $$$k$$$ distinct variables. Then, if we fix the frequencies of variables, the greedy strategy "always query the $$$k$$$ variables with the greatest remaining frequency" is guaranteed to work unless the max frequency is $$$ \gt d$$$, in which case there is no solution. Thus, we want to minimize the max frequency while keeping all frequencies odd and having sum of $$$dk$$$; this is achieved by making the frequencies as similar as possible, either $$$1+2\lfloor (dk-n)/2/n \rfloor$$$ or $$$1+2\lceil (dk-n)/2/n \rceil$$$. In particular, $$$d$$$ is valid iff $$$dk \ge n$$$, $$$dk \equiv n \pmod{2}$$$, and $$$1 + 2 \lceil (dk-n)/2/n \rceil \le d$$$, so we can find the minimum $$$d$$$ with a simple linear search.

F1 is similar to https://dmoj.ca/problem/wc99sp5.

In question D I'm getting an error "wrong output format Unexpected end of file — int32 expected". I don't understand if I used wrong approach because my code works fine on small test cases and counter test cases. If someone could help me resolve it that would be a great help. Thank you. My code: 119541888

Problem B would have been even more interesting and difficult if height of bars could be increased as well. Which sadly how I misinterpreted it.

In problem G, $$$dp[x][y] = (\min{dp[a][b]} \forall y-(x-a) \leq b \leq y+(x-a)) + (\sum{\frac{|y-z|}{2}} \forall potatoes (x,z))$$$ all such b's aren't reachable, won't that create any problem? Also what should be our intial function, I think it should be like $$$f(0) = 0,$$$ else $$$\infty$$$. Somebody please help me out.

Its mysterious to me. Please point out what is wrong in this easy problem A-solution.

In F2 we need to mark the minimum number of nodes in a DAG such that a set of "special nodes" can be reached by at least one marked node.

Because any special node can be reached by a contiguous range of other nodes we can solve this problem efficiently in this case.

Is this problem NP-hard in a general graph?