Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

Автокомментарий: текст был обновлен пользователем neckbotov (предыдущая версия, новая версия, сравнить).

I think pretests are weak for B.

Wishing everyone HAPPINESS,LOVE,JOY and PROSPERITY.

Why in problem Div1C for the test 3 3 abc

the answer is Yes? we have only 2 options here: 1) -a — b + c = -1 — 2 + 4 = 1 2) -a + b + c = -1 + 2 + 4 = 5

Time limit for B is awfully tight for python. 101868901 and 101909293 have a mere constant factor difference but one TLEs and the other ACs

my -20 is now a -140 :(

Upd : Got hacked xD

Can someone explain B?

Problem C is Intresting!!! we can solve it with DSU too.

Can someone explain the editorial of Division 2C? I am not getting it

How to prove that ternary search will work in Div1B/2D?

What is point of having strict time limit for DIV2 B?
I am storing the digits of a number in set:
Advantage: I don't need to check for same digit again.
Disadvantage: Extra log factor
It is giving TLE.
101869576

First, note that the last digit will always be taken with a plus sign, and the one before the last — with a minus sign

Isn't it the first digit, not the one before the last?

Edit: Nvm, I understand why now.

D1E Walsh-Hadamard transform solution: https://codeforces.me/blog/entry/85746?#comment-735491

For Div2 C, how come we only need to consider the edge x->y and not y->x? I understand what is happening with the graph, and why cycles need an extra move to break, but do not understand why/how the graph construction relates to the problem.

In Div1 B, I used binary/ternary search over prefix length, assuming the costs would be decreasing then increasing, but it failed system tests. I later got AC by just also checking the endpoints (0-length prefix and full prefix). I wonder if there is an easy way to characterize the cost function vs prefix length causing this to work.

.

I solved A and B under 10 min. Can't solve C after 110 min. didn't read D. result is +31.

What is your advice ?

why his code got AC, but the same code I got TLE?

can someone explain to me why div 2 c solution of xmt who came 2nd in div 2 is giving time limit exceed on test case 12 when I am trying to submit the same solution but his solution got accepted?[user:xmt][standings:https://codeforces.me/contest/1465/standings]

I have an offline solution to F that involves pretty much no data structures. First, divide-and-conquer on time so that we only have to process $$$O(q \log(q))$$$ insertions (no deletions).

First, note that checking whether all paths are within $$$d$$$ of a given point is a lot like checking if the "diameter" is at most $$$2d$$$. In fact, this is exactly true; the minimum $$$d$$$ for which there is a vertex in the $$$d$$$-neighborhood is exactly 1/2 the maximum value of the shortest-path between some two paths in our set.

We can actually go a step further; let the "center" of the set of active paths be the set of vertices which minimize the maximum distance to any active path, and let the "radius" be this distance. The center is either the intersection of all active paths if it's nonempty (and the radius is 0), or a single point (the midpoint of the diameter). (Here, we allow points to lie halfway along an edge).

Now, we can show that for any other point, the maximum distance to any path is exactly the distance to the nearest center plus the radius; this follows for essentially the same arguments as for the center of a normal tree. Thus, in order to support new insertions, we only need to maintain the center(s) and radius of our current active set. Updating the center/radius when adding a new path is also easy; we can check if the path intersects our center(s), and potentially move the center towards that path. All of these operations can be implemented using only LCA/level ancestor. With standard LCA, we can solve this problem in $$$O(q \log(q) \log(n))$$$, and with precomputation, this should only take $$$O(n \log(n) + q \log(q))$$$ or even $$$O(n + q \log(q))$$$.

Implementation note: when the radius is positive, instead of maintaining the center, we can just maintain a diameter, i.e. a path with length $$$2 \cdot radius$$$ and midpoint at the center. This allows us to remove the level-ancestor queries.

AC in $$$O(q \log(q) \log(n))$$$: 101920713

AC in $$$O(n + q \log (q))$$$: 101921489

What's the proof for the greedy addition/subtraction in D1C?

Can someone please explain to me D. Grime Zoo? Thanks.

Can there be any approach of c without using graphs?

Спасибо большое! Хороший, понятный разбор и отличный подбор задач. Но мне показалось, что на этот раз задачи были более сложные, чем на предыдущих отборах. Хотелось бы по больше таких соревнований.

Hi, could somebody please explain the following (D2E/D1C): Now the problem is reduced to whether we can get the number X using the first n−2 letters. Since the weights of the items are powers of two, we can choose them greedily.?

Can you share your solution to Div2 D? It is hard to find and interpret which submission uses the same approach mentioned in the editorial.

Can anyone tell why thus code is failing for 1234567890 https://codeforces.me/contest/1465/submission/101931003

How to solve the Div2 C with dsu?

How to solve div2-D with DP?

In question C, I got WA on test case 5. Here is link to my WA solution: here
Here is link to Accepted solution: here

Can anyone help me, what's the difference in both of dfs? Everything else is exact same.

Hi anta.baka! What does variable "Roma" mean in your code? Was this code written by you? I can't find the variable "kukold" which you usually use..

Someone plss help me with problem B https://codeforces.me/contest/1465/submission/101926615

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

Автокомментарий: текст был обновлен пользователем neckbotov (предыдущая версия, новая версия, сравнить).

In Div 2 D, how do we find which prefix of ? is optimal to be replaced by 1 (x >= y)? I tried brute force which gave TLE (reasonably so), then thought there might be only one global minimum (WA), and tried minimizing r-l (WA). I think the proof needs to be a bit more elaborate.

Can anyone explain D a bit clearly? I dont understand the editorial.

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

Автокомментарий: текст был обновлен пользователем neckbotov (предыдущая версия, новая версия, сравнить).

In problem Div1C/Div2E, can someone explain to me how the $$$+$$$ $$$-$$$ are chosen greedily, is it only possible if the weights were powers of two?

I got TLE in Div.2\B(Fair Number) although I think that I did almost same as written in editorial. Here is my submission 101881464. What did I do wrong?

Another solution for div1E with GP summation of matrices (very similar to editorial, but another way to look)

Let $$$C_i$$$ be the number of grundy numbers with value $$$i$$$.

Since we need to find the number of

Let $$$P(T, X)$$$ be the probability the xor of the grundy numbers will be X after T turns.

$$$P(T, X) = \sum(ans(T-1, Y) * C_{X\oplus Y})/(n+1)$$$

$$$P(T)$$$ can be written as a matrix product of $$$M$$$ and $$$P(T - 1)$$$, where $$$M_{i,j} = C_{i\oplus j}$$$

$$$P(T) = P(T - 1) * M$$$

Probability that Bob wins is, $$$\sum_{t \geq 0} P(t, 0)/(n+1)$$$

$$$Q = \sum_{t \geq 0} P(t) = P(0) \times (M^0 + M^1+M^2..) = P(0) \times (I \times (I - M)^{-1})$$$

Probability that Alice wins is $$$1-Q(0)/(n+1)$$$

so i was little skeptical of the approach described in the editorial for Div 2 Question C — Peaceful Rooks, so i tried proving it on my own. please let me know if anything is incomplete, unclear or incorrect. hope this helps someone understand.

idea: if a set of coordinates form a cycle, it is impossible to move a rook from the set to a main diagonal square that is not guarded by another rook in the set.

for example take {(1,2),(2,3),(3,4),(4,1)}: notice that these 4 vertices are using 2 out of the same 4 numbers as both their x and y coordinates. therefore, every one of these 4 numbers must appear exactly twice in total in the set. (you can count them to check)

furthermore, if one chooses any pair (x,y) and tries to move it to (x,x) or (y,y) (the main diagonal), since there are always 2 pairs that contain any number, you can be sure that both of these coordinates will be guarded by some other rook (either their x or their y coordinate will coincide if it exists, and if there are two in total then it does)

generalizing, if we have n nodes that form a cycle, they choose 2 numbers from n numbers to use in their (x,y) coordinate pair. each of these n numbers appear twice — once as an x coordinate and once as a y coordinate, since no rooks attack each other. therefore none of the rooks can be moved to the main diagonal in this state, so we must waste a move breaking the cycle.

proposal: breaking a cycle necessarily allows the rooks that were originally in the cycle to be moved to the main diagonal (in some order) in exactly 1 move each (no more extra moves needed)

proof: first, note that (m < n) so there is always one horizontal empty and one vertical empty

therefore its always possible to break the cycle (moving a piece changes the set of numbers => cycle broken) now our set of numbers from the coordinates of the k pairs is k+1, and 2 of those numbers only appear once in the set: moving a rook horizontally into an allowed position adds a new x value to our set of numbers, and removes an occurrence the old one. the same holds for vertical by symmetry. so now we have at least 2 main diagonal options that are not guarded by another rook in the same set. (but this is not enough, see below question)

another insight is that once the cycle is broken, the rest of the rooks that did not move cannot form a cycle. this is because each rook has one edge going in and one going out, so if the rest of the rooks formed a cycle then the rook that was just moved has no way to fit in the cycle (the rest would already have 1 in and 1 out if they were in a cycle)

the question is, what if rooks from outside this formerly-cyclic-set-of-rooks guards all the main diagonal square options from this set?

let the rook that is moved to break the cycle be rook (a,b) before moving. now once we move this rook to a legal position (a position where no other rook is attack by this rook), say, (a+k,b) (there is always an empty vertical and horizontal so this is always possible) then the column a is now empty. recall that in the cyclic set, a number appears exactly once as an x coordinate and a y coordinate. so there must be some other rook with coordinates (i,a) to complement (a,b) for whatever column i. so since column a is now empty, (i,a) must be able to move to (a,a) in 1 move.

recursively there is now another rook (j,i) in the set for whatever column j. since (i,a) moved to (a,a), column i is empty. so (j,i) must be able to move to (i,i) in 1 move. so this process can be repeated until all the rest of the rooks in the formerly cyclic set can be moved to the main diagonal in 1 move.

this works without having to worry about the interference of rooks from outside the set, because when we move horizontally onto a new column, there is no rook on the same row and the new column is always empty. therefore it will never be guarded. by symmetry moving vertically is the same

now the only exception is the rook that we moved at first : the rook at (a+k,b). how do we know that it will always be able to move to the main diagonal in 1 move?

if u move (a,b) to (a+k,b), then originally there was some rook on (b,h) for some row h to complement (a,b). but recursively we showed that every rook aside from the first rook can be moved onto the main diagonal, so this rook (b,h) can be moved to (h,h) recursively (it does not move to (b,b) because our moved rook is on (a+k,b)). now after this rook moves away from the b column, that means that the b column is necessarily empty. so therefore our rook on (a+k,b) can be moved to (b,b) in one move

therefore, if a cycle formed by a set of rooks is broken (which it always can be), each rook in the set can now be moved to the main diagonal in exactly 1 move each.

спасибо за такой понятный разбор!

I am having difficulty in understanding the problem Div2D editorial. Can anyone help me understand it with DP?

can't understand how the formula from div2.D "sl=0,sr=1 (c1+1)*x+c0*x+out" calculates subsequences of 10 type INSIDE (l, r). E.g. ?101? where did we put "10" inside the formula above? Because out calculates only the cases where one of the elements is outside

Can someone explain the meaning of the editorial in Problem F when it says that it boils down to breaking the array into "threes and a remainder". I was not able to understand the solution mentioned.

EDIT — I got it. Ultimately, the permutation consists of some number of cycles. The number of days it lasts is equal to the products of the lengths of those cycles.

It is optimal to make each cycle length

. And if we have a remainder of

, then we must make 2 cycles of length

.

Suppose we have a cycle length

. We can break it down into

and get a greater product.

I tried problem C and my approach was using disjoint set union, however it is resulting in TLE in one of the test cases. The time complexity appears to be O(T*m). https://codeforces.me/contest/1411/submission/102050815 is my submission link. Could anyone please provide some suggestions on how I can improve my code? Thanks a lot in advance!

EDIT: I got it accepted now using fast I/O (and well "cheating"(although it should work even without knowing the test case, as the max size of the board possible is 10^5) on the last test case#12) https://codeforces.me/contest/1411/submission/102057925. But I would still appreciate some suggestions to optimize it further.

I find the proof for Div2F/Div1D, about why we want to get more cycles of length 3. Actually the theoretical maximum occurs when you split the given number into parts each of size e (= 2.71828).
Although this conclusion may be common to orange and red coders, but I think most people are unfamiliar with it. So I hope some reference of proof can be added into editorials in future. Thanks!

Do you have solution code for these problems?

Could anyone please help me to check if my solution of Div.2 C is correct? If it is correct, could you please try to prove that? Otherwise, could you please provide one test case to hack it?

I explain the process of my solution in the following part, you may understand the solution better through it.

First, I try to find rooks on cell $$$(x,y)$$$ such that there is no rook on the $$$x$$$-th row or on the $$$y$$$-th column, so that I can move it there in one move. To do that, I make a function called solve. Every time I move a rook from $$$(x,y)$$$ to $$$(x,x)$$$ or $$$(y,y)$$$, I check if there is going to be another rook satisfied the condition above because of this operation.

I used the function solve(i) for every $$$i$$$ such that $$$1 \le i \le m$$$ but I got WA. Then I change it into doing this operation $$$1000$$$ times so that I get AC.

Then I add $$$1$$$ to the answer for every $$$i$$$ such that $$$x_i \neq y_i$$$. Finally, I use DSU to calculate the number of cycles.

How to solve the bonus in Div1C?

I've successfully uphacked 132 solutions now on div 2 B. Mostly PyPy solutions, but also Kotlin, Java, Python, Haskell and some C++ solutions. The hacking I've been doing is very simple. I made a counter test for solutions that abuse early exits (if the digits are read from the left). Note that C++ submissions usually read digits from the right, which is why I was only able to hack a few C++ submissions.

Problem setters, you should really think about what constraints you use next time! And if you for some reason find it interesting to have tight constraints then you REALLY should try to make good test cases for it!

EDIT: Gotten 391 successful uphacks now (on div 2 B)

Well, second task seems really easy, especially after I've read the solving, but my code is failing due to time error. How it may be optimised?

102395452

Help me with a problem for 1411G 1.before the process,what is the number of chips on vertex?0? 2.When Alice and bob are begining to play the game,is it meaning that the process is termitalely? 3.Can we think the number of chips are random?