# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 181 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/21/2021 01:24:34 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).I think pretests are weak for B.

Pretests are not weak, time-limit is tight

my AC soln after the contest: https://codeforces.com/contest/1465/submission/101907158 , my WA soln during the contest: https://codeforces.com/contest/1465/submission/101883576 just changed the number from lcm of digits in the given number to 2600(although I know 2520).

Numbers are up to 1e18, why do you feed int into gcd/lcm function?

Wishing everyone HAPPINESS,LOVE,JOY and PROSPERITY.

Can div 2 C be solved without graphs usage? if so can someone explain how to solve it without graphs?

Thanks in advance!

You don’t need to find cycles in a graph explicitly, you can use disjoint sets (union find) to group rooks, list out the number of diagonals a group can attack, and add to the number of moves required based on that.

A group that can only attack one diagonal is already on the diagonal and requires 0 moves(loop), a group that can attack as many diagonals as there are rooms requires rooks+1 (cycle), and a group that can attack more than there are rooks requires rooks moves(tree).

It’s graph-like, but it’s chess so that’s to be expected.

Thank you so much !!

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

the second case should be 1-2+4=3

ah, the first sign is not necessary "minus" :(

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

Same thing happened with me. After contest, I used dictionary to store the answers. Here is my AC code.

CODEThat only works cause no one has bothered to make a counter test for it.

Yes I got TLE too and that because of python same logic got accepted in any other language

Try to submit your code in pypy3 or pypy2. (Same logic accepted)

Thanks mate it would help me for further contest

Just hacked your lower constant solution. That one passed only cause there wasn't an early exit counter test case.

Btw the reason why PyPy is super slow here is that PyPy is 32 bit on CF, so this problem requires you to do a ton of work on big integers. This code would have easily passed on pretty much any other online platform. Remember to always look out for slow big integer operations in the future! Especially in problems like this where a lot of the big integer calculations easily can be avoided.

Thanks for the info, I don't use python during CF rounds often, this was one of the first. I made a few resubmissions with minor changes. 102364715 passes with 1980ms (its the same except for one line) and the same hacked code passes when I add fast IO 102365085.

Upd: Hacked

Upd2: AC 102366948

Just hacked both of those with a better counter test case.

Btw if you really want something not hackable using early exits you should skip mod checks for both 0s and 1s 102367618. My TLE hack makes your solution do

`% int('1')`

around 2.5e8 times. By skipping 1s, then an upper bound on the number of operations becomes something like 1.3e8 times.EDIT: After looking through your recent submissions, I saw that using ord instead of int helps a ton. So I updated the "unhackable" solution above to reflect this. Looking at the numbers, it looks like doing

`int('1')`

2.5e8 times is the real killer.After uphacking your code I continued hacking. Currently up to 391 uphacks on Div 2 B. The system tests were definitely lacking.

Can someone explain B?

2520 is the smallest number that is divisible by all the number between 1 to 10 so we will iterate from n to n + 2520 because there will be one number for sure that will be divisible by all the digit. So just apply brute force

LCM(1,2,3,4,5,6,7,8,9)=2520 So ::>> EVERY MULTIPLE OF 2520 is divisible by all digits( 1,2,3,4,5,6,7,8,9 )

NOW let x=n(GIVEN NUMBER). SO just iterate x ,i.e., do x++ UNTIL THE given CONDITION in question SATISFIES.This will take at most 2519 iterations.

I think I explained correctly in the rev 1..

I gave my best .. But I don't know why I was down-voted.

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

can u post the link to the code pls?

Yes, sure! 101952477

Nice implementation. Mine seems like gibberish. xD

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

1.Ignore the rooks on coordinates of form (x,x) since they are already on the diagonal

2.Make directed edge between two rooks if x coordinate of the one rook matches y coordinate of the other rook. Suppose there is rook on coordinate (x,y) and another on $$$(x_1,x)$$$ then there will be edge from rook on (x,y) to rook on $$$(x_1,x)$$$.

From point 2 we will get a graph . Answer will be number of vertices + number of cycles in the graph . This is because for each vertex we have to do at least one operation . Whereas for cycle , we need to do at-least 2 operation for any one of the vertex on cycle to break the cycle. Note : Here we are not counting vertices (of form (x,x)) in point 1 in our calculation thus no need to subtract as given in the Editorial.

For example in following 5*5 matrix (sorry for bad picture), minimum number of operations is 5 (4 vertex + 1 cycle). Red dots are rooks and red edges form the graph.

Try yourself in less than 5 operations and you won't be able to do it.

Very good explanation. I was searching for something like this. Thanks a lot.

Why do we build the edges like this, I can't unserstand.

I hope you got "How" part . Thus i will explain "why" part .

Suppose rook0 on the coordinate (x,y) and x≠y , in one move we can move it to (x,x) or (y,y) . But if there is some other rook, say rook1 on column x and rook2 on row y then we cannot move this rook on (x,x) or (y,y) . Thus we have to move rook1 or rook2 first in order to move the rook0 on diagonal in one move.

But it might be possible rook1 and rook2 themselves cannot move on the diagonal if they have case similar to rook0 .

By forming edges like i mentioned we can find those group (cycles) of rooks where each rook in group cannot move to diagonal in one move until one of it is moving to some diagonal point with "2" moves.

WOW！ Wonderful explanation. I get it. I'll put it on my blog.

Will undirected edge make a difference?

Number of cycles will remain same in both cases because each vertex will have maximum degree 2. There will be just disjoint cycles (i.e there won't be case like two cycles connected to each other). Hence no difference in answer.

In cases where (x,y) and (y,x) both form edges, the undirected edge will lead to the wrong count of cycles. So, in my opinion, directed edges are more apt.

It depends on what algorithm you are using to find the cycles . Number of cycles won't be effected by directed or undirected edges in this problem.

Yeah , for most algorithms directed edge will be safer to avoid multiple counts of same cycle.

Won't there be multiple such graph? Consider 4 points (x,y), (x2,x), (x3,y2), (x4,x3). Nice explanation though.

Well i considered it to be a graph with n nodes where each coordinate (i,i) ( 1<=i<=n) are considered as nodes. There is an edge between a node at (i,i) and (j,j) if there is a rook at (i,j). Ignore the rooks placed on coordinates of the type (i,i) because those nodes form self loops. Now simply count the number of cycles in the graph.

Now the answer is

number of cycles + number of rooks not on any (i,i)

This is my submission link 101935324

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

Same with me . Don't know whats the point of making those submission fails system test! Atleast , they could have added a pretest that would take longer time, so that people could get that point of log factor!

I think its not due to log factor but constant factor of

`set`

. i am not sure.First, note that the last digit will always be taken with a plus sign, and the one before the last — with a minus signIsn't it the first digit, not the one before the last?

Edit: Nvm, I understand why now.

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

Hey neckbotov, can you explain why can't we treat each vertex independently? I mean why not just find out if a vertex is winning or losing by simply traversing topological order in reverse. Essentially, why can't the grundy number for a vertex be 0 or 1?

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.

I constructed it with bidirectional edges and it worked as well if you accept multiple edges. Otherwise you wont be able to see the cycle of length 2 easily (for such a cycle you need two rooks that have switched coordinates, e.g. 1 2 and 2 1).

That part makes sense now.

Can you clarify why x->y and/or y->x should even be edges in the first place though? Does not seem intuitive to me why something like rooks={(1, 2), (2, 3)} should create the graph 1->2->3

my idea was that a rook on row r and col c will guard the diag elements r,r and c,c. so if another rook has an eye on at least one of these elements then these two rooks are connected somehow. I came up with idea to use graphs as i recognized that rooks may or may not build cycles (a cycle of size 3 was in the sample). so i build the idea to find these cycles with graph theory and then it is pretty obvious that a rook is the connection between 2 nodes which represent a diagonal element.

My implementation is bit different. I created graph of pairs — $$$(x,y).$$$ You can look at my code. Not sure, if it's helpful.

I'll try to explain a bit.

Start dfs from any pair $$$(a,b)$$$ if it is not visited and explore its connected component. A pair $$$(c,d)$$$ is connected to pair $$$(a,b)$$$ iff $$$d=a$$$ or $$$c=b$$$. I'm first assuming there is $$$cycle$$$ in the connected component. Start from $$$(a,b)$$$. If it has $$$0$$$ connected nodes, we are sure there will no cycle as we can put $$$(a,b)$$$ at any of the $$$2$$$ suitable points. If it has only $$$1$$$ connected node, we can be sure that there is no cycle (we can move that rook at only suitable point) but we will still put the only connected node into the stack (if its un-visited) to explore further total number of nodes in the connected component. If it has $$$2$$$ neighbor nodes, put them into stack (if they are un-visited).

Finally, after each dfs, $$$ans+=x + c$$$ where $$$x$$$ is nodes in the connected component and $$$c=1$$$ if there is a cycle in the component else $$$0$$$

I'm not sure if cycle is correct term for it but I mean is if in any connected component, if we find any node $$$(x,y)$$$ for which either of it's $$$2$$$ suitable positions is free, we can displace that rook to its any suitable position thus breaking the locks. If we can't find any such position, we have pay 1 extra than the total nodes in the component.

Either will do, but not both. We need to move a rook from $$$(x,y)$$$ to either $$$(x,x)$$$ or $$$(y,y)$$$.

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.

Another approach would be:-

Make a copy of the original string (call it "ss"), and fill all '?' with '0' in string ss.

Then calculate the answer for string ss and store it in "temp".

Initialize "ans" and assign it the value of "temp".

Then, start iterating backward in the original string s (i.e. from i=n-1). On positions where s has '?', recalculate temp by subtracting the number of comments if this position had '0' in it, and adding the term if this position would have '1' in it, greedily.

Then, update:

ans=min(ans,temp)

The final minimum number of comments is obtained in "ans".

Since we have to update prefix array(that stores either no of 1 or 0 upto i) every time we change from 0 to 1 in the string ss, so how should we implement that exactly....do we have to use segement tree or something else

Check their submission. Apparently you can directly edit the string? I always thought they were immutable...

Can anyone tell why this code for Div2-C is giving WA on test-5?

Code...

.

Yes, it is

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 ?

Read D

I am similar with you, and I choose to sleep

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

Test case 12 has not been there at the time of the system test! It has been added later. xmt You're lucky to get away with that :D Anyway, you would be gaining CM I guess, Congrats!!

The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

wow, what is the difference? do you have an example?

The problem B numbers are Lynch-Bell Numbers

It's not. Lynch bell numbers can't have repetitive digits.

Oh yes! My bad.

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.com/contest/1465/standings]

The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

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

I arrived at the same solution eventually. 101922707

Instead of time D&C we can build a segment tree on all paths present in queries, and turn them on/off.

Ideas from yesterday's 1458F - Range Diameter Sum were somewhat helpful.

Ah, right, if you really want it to be fully online, you store the paths in an augmented BBST or a compressed segtree with implicit size $$$N^2$$$.

It's funny that 1458F is related to a problem in this contest, and also problem B in the OpenCup GP of Xiaomi, all in the same weekend.

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

This is not a proof but let me share my idea.

Let's consider the situation where all the signs are a minus sign(i.e. the n — 2 prefix signs are all minus signs) and you can turn an arbitrary minus sign into a plus sign. In this case, the result of calculation will become minimum. Let this value be

V.When you want to obtain some value greater than

V, it is always better to choose as big a number as possible and change its sign(but even after the change,Vshould not exceeds the value we want) because you want to adjustVwith small numbers afterwards. (In other words, why do you use several small numbers to make a big number that already exists? You are missing out!)Can you please help me with the part on how we can obtain any sign we want on the first

integers ? It was not clear to me from the editorial.

Since we already have the observation that last is

`+`

and second last is`-`

, we can find a way to split.For example:

`---+++-+-++-+`

. We split left most`-`

one by one, so it becomes`+++-+-++-+`

. Then if remaining are all`+`

, then we done. Or we find the left most`-`

then split there,`+++-+-++-+ => (---+)(+---++-+)`

, so our left part also done. Then we recursively solve for the right part.The remaining split will looks like:

`+---++-+ => (-+)(--++-+) => ++-+ => (--+)(+) => +`

Wow ! I got it. So we just focus on the minus signs and do them one by one.

Yeah, right. And choose right place to split so the last two elements are

`-+`

Yeah I also have the confusion, especially when we convert from negative to positive, like: -13 = -16 + 2 + 1 So when we meet -13, how can we decide whether +16 or just leave it here

I struggle with it a lot yesterday, but the solution from ecnerwala convince me a lot, you can take a look at his stream.

The basic idea is that he treat +-2^S[i] as -2^S[i] + (0 or 2^{S[i]+1}). So we can add all S[i] to T and decompose it into binary with power of i+1.

More formally, sum(+-2^S[i]) = T => sum(2^S[i+1] or 0) = T + sum(2^S[i])

Suppose number we need to reach is $$$tot$$$.Since sign of a[n],a[n-1] is fixed , we can subtract and add their powers from $$$tot$$$. Now we initialize $$$s=0$$$ and we need to reach $$$tot$$$ using characters from 1 till n-2 .

I used following greedy method (and i hope editorial refers to same greedy method) : sort the string from 1 till n-2 . Now iterate from n-2 to 1 and if $$$s>tot$$$ subtract $$$2^{a[i]}$$$ else add.submission

Proof: Suppose we are at index $$$i$$$ and $$$s>tot$$$ . If in optimal solution we do $$$s += 2^{a[i]}$$$ (contrary to what i mentioned) , then sum of numbers left , say $$$H$$$ , must be greater than $$$2^{a[i]}$$$ (otherwise $$$s + 2^{a[i]} - H > tot$$$ and answer won't exist) . Also since $$$H>2^{a[i]}$$$ and array is sorted , there must be some subset say $$$SS$$$ of $$$a[1],a[2],a[3]...a[i-1]$$$ such that sum of their power of 2 is equal to $$$2^{a[i]}$$$ .We also need to add subtract at least $$$2^{a[i]}$$$ in future , else $$$s$$$ will be greater than $$$tot$$$.But then we can do $$$s -= 2^{a[i]}$$$ instead and we can add sum of power of 2 of subset $$$SS$$$ in future. Similar proof for case $$$s<=tot$$$ .

Poman Numbers ( Div2 E/ Div1 C )Explanation of the greedy part of the solution + Commented CodeCode103545539

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

I found B to be the most tricky one!!!!

Can there be any approach of c without using graphs?

I didn't use graph but the solution is too long, basic idea is to see whether we can give a move when some points go to diagonal 101886029

Thankyou I was searching for this.

Another approach 101883649.

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.`

?Ques- Since the weights of the items are powers of two, we can choose them greedily,how?

Ans --> Firstly, let T = abs(T) because if we can make T from the array then -T can also be made by just reversing the symbols i.e + to -; and viceversa.

Now, get the sum of all elements and if sum is less than T then ans is clearly no, otherwise lets assume that T can be made using sum therefore sum_left = sum — T now for our assumption to be true we should be able to make val = sum_left/2 from the array elements :

i) if sum_left is odd then our assumption is false and print 'no'

ii)else we can simply check by sorting array in descending order and subtracting a[i] from val if val >= ai

finally if val becomes 0 our assumption was true i.e print 'yes' else 'no'

Code Link: 101958203

Thanks!

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.

watch the stream by ecnerwala

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

Your vector only contains n's digits, not x. Therefore, it will add +1 until the number x is divisible by the every digits n. My english is very bad, so i think you get the main idea

It looks like you are using the original digits to determine whether subsequent numbers are fair. Why aren't you running getDigit(v,x) after you increment x?

For example if your number is 16, then the digits you will get are 1 and 6. This is not a fair number so you have to increment. It looks like your submission is checking 17,18,... against the digits 1,6 rather than against 1,7; 1,8. In this example 18 will show up fair because it is divisible by 1,6. 18 is not a fair number though because it is not divisible by

itsdigits 1,8.Can anyone tell me that why Binary Search is not applicable in Div2 B?

for div2C , my greedy solution was find the number of rooks that are not in the main diagonal and store them in a vector.Let size of vector be sz.Now for all x1 in x coordiantes of the vector , if there is no y coordinate that is = x1, then it will take sz operations,else itll take sz+1 operations.It gave WA, can someone suggest an alternate greedy approach and say whats wrong with this https://codeforces.com/contest/1465/submission/101892078

How to solve the Div2 C with dsu?

I hope you know about DSU .If not , read here , very easy to understand.

Suppose we have two vertices $$$v_1,v_2$$$ in the graph formed having edge between them . Then we connect root parent of $$$v_1$$$ and root parent of $$$v_2$$$ in DSU "join" operation . But while joining if we found that they are already in same tree (i.e have same root "parent") then there is a cycle since there was a path between $$$v_1,v_2$$$ earlier and thus adding one edge between them will make a cycle.

Now count all the cycles using above method and use the formula either described in editorial or here.

Thank u very much. I have got it.

For Coordinates (x,y) how we are assigning the parents? And how the vertices are defined in your answer?

How to solve div2-D with DP?

From DP I think the time complexity would be O(n^2).

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.

I also faced a similar issue

Let's say there are 3 rooks at (a, b), (b, c) and (c, d). In your WA solution, if you start your dfs from c, you will mark c and d as visited and then call dfs(a), this will return true because c is marked visited, but it was from a different component, you need a way to differentiate the nodes marked visited in the dfs(a) call and the ones marked earlier, this is what you are doing in your AC solution when you mark them 1 during the call and 2 after the call is finished.

Solved.

Ohk, Yes I get your point. Thanks a lot for explanation.

Hi dargelirli! 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.com/contest/1465/submission/101926615

use long long instead of int to avoid overflow

It is still not working

When you passed by value to your solve() function, it's accepting int, not long long. Change that and it's accepted.

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).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.

WLOG assume $$$x > y$$$. Suppose we claim that

replacing the question markswith a sequence like $$$10010$$$ gives best solution. The editorial just shows that you can change it to $$$11000$$$ to get a better solution (ie swapping 01 by 10 till it is not possible anymore). So in reality we do not know how many question mark get converted to 1, so we go over all prefixes of 1.DSU solution of problem C (Div 2)

Thanks!!

one doubt we are returning parent[a]=find(parent[a]), if i do like find(find(parent[a])) im getting TLE

Because it will take n^2 time for every iteraation

okay

can someone explain div 2 D...

so amazi

anyone who didnot use brute force in div2B?

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).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?

By binary-search principle. Just sort all powers of two except the last two. Go from maximum number to minimum. Initially all signs is

`+`

From each number change the sign if and only if after change sum of all`n`

2-powers (let's name it`sum`

) greater or equal to`T`

. After all changings, if`sum=T`

then answer is`Yes`

OOH I got it thanks!!! But is it possible if the weights weren't powers of two?

In this problem weights always are powers of 2, by the formula. If you about all problems, it's impossible. For example, you need to obtain

`-1`

having 3 numbers:`5 4 2`

. This algorithm will swap sign of 5, sum will be equal to 1. After this, the algorithm won't obtain -1. But if remain sign of 5 and change signs of other numbers, sum is`5-4-2 = -1`

1411A — In-game Chat Whats wrong in finding if lens — nosOfBracketInEnd <= nosOfBracketInEnd to find if it is bad.

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?

My potential solution to $$$D$$$:

It can be seen that result will be in form of $$$ax + by$$$, where $$$a$$$ is the number of subsequences $$$01$$$, y of $$$10$$$, similarly. It also can be seen that $$$a + b$$$ $$$=$$$ $$$cnt_0 \cdot cnt_1$$$. ($$$cnt_c$$$ — number of occurrences of $$$c$$$ in the final string). Now, we can brute force result with the binary search. Total complexity — $$$O$$$$$$(Kn)$$$. ($$$n$$$ — string size, $$$K$$$ — number of iterations in binary search)

If you don't know the right solution please don't spread wrong solution.

I said potential

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)$$$

Hey, Can you explain why can't we treat each vertex independently? I mean why not just find out if a vertex is winning or losing by simply traversing topological order in reverse. And then if we have X winning vertices[P(x) = X/(n+1)], then calculating the answer is pretty straightforward.

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

outsidethis 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.

Really appreciate the hard work you have put in writing this explanation. Thanks :)

I need help to debug this https://codeforces.com/contest/1465/submission/102001052

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

when it says sl = 0 and sr = 1, it is only calculating the contribution by sl and sr, thats why any subsequence of type "10" hasn`t been mentioned

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.

Hi bro, do you know how to prove it is always optimal to take three?

UPD:nvm, I find itWe can prove it with Mathematical Induction and seperately with each modulus.

Anyway, I did not understand how to apply this fact in the solution of the problem. Can you tell me how we construct cycles of length

in the permutation ?

Sorry, I haven't looked into that part

For any permutation of size $$$n$$$ that is also a single cycle of length $$$n$$$, you can renumber it such that:

This is not a necessary step; just for convenience.

Now, a cycle of size $$$n=a+b$$$ can be split into two cycles with size $$$a$$$ and $$$b$$$ each by swapping $$$p_a$$$ and $$$p_{a+1}$$$. If you are feeling doubtful, try with some small example (like $$$a=3, b=5$$$).

On the other way around, you can also join two cycles by swapping any pair of $$$(p_i, p_j)$$$ values from each cycle.

In this way, the cycles can be arbitrarily split and joined on each swap. Thus, after calculating the size of each cycle in the permutation, you don't have to think anymore about how cycles are made out of permutations. If the sizes of the cycles are $$${5, 3, 2}$$$ (which would mean $$$n=10$$$), then (for example) you can split 5 into $$$5=1+4$$$ or join 5 and 3 to form 8.

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.com/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.com/contest/1411/submission/102057925. But I would still appreciate some suggestions to optimize it further.

can we solve div2 D Grime Zoo using Dynamic Programming ?..

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!

Problem C,Why im getting TLE https://codeforces.com/contest/1465/submission/102178111 what is the use of parent[a]=find(parent[a]) we can return simply find(find(parent[a]) ?

can someone explain problem D

Do you have solution code for these problems?

what is the expected difficulty of problem div2C.

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. ThenI 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)

I agree that pushing constraints till limit is not always a best practice. But I was quite surprised to see that the limits were actually high to deny some solutions!

If anyone tells me a problem:

`itoa`

and a few modular arithmeticsThen I would have said that 2 seconds are just enough.

The ×18 underlying in itoa, the early return scheme, and the environment being 32-bit (can I have a reference on this? It's been long since I read it) puts this TLE behavior on a precise blind spot that the setters failed to address.

After testing more, I've realized that the issue with the constraints is mostly just due to $$$1e3 \cdot 2520 \cdot 18 \approx 4.5e8$$$ being huge. With a bad constant factor (like in Python calling

`int('1')`

over and over, or in C++ storing all digits in a vector) you simply get TLE.The way people avoided TLE during the contest was to abuse early exits in the divisibility checking. Unfortunately there were no good counter tests for this. So far I've TLE uphacked > 400 solutions (many submissions were from the contest). My opinion is that a div 2 B should not have tight constraints unless it stops some kind of unwanted solution. This time around I believe the constraints were simply unnecessarily tight.

If problem setters for some reason find it fun/interesting to set tight constraints, then they should also make test cases for it. This time around the constraints were tight, but a ton of solutions still got through because of lacking system tests.

If you are asking about why PyPy is 32 bit on CF: https://doc.pypy.org/en/latest/faq.html#what-is-needed-for-windows-64-support-of-pypy .

So true! The 18 looks innocuously small like alphabetic 26 or digital 10 and that might be why the setters missed it, but it contributes much so that the resulting time complexity became something as large as $$$O(N^2 \log N)$$$ solutions for $$$N \approx 3000$$$ problems, which is dangerous enough.

On the other hand, I keep thinking of the disaster that would have took place if the test included the worst cases...

Your PyPy document link was also helpful, I didn't know this. Thank you!

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

As I wrote in the comment above yours I've been TLEing tons of PyPy solutions, and you got TLE on one of my test cases.

The trick to avoid TLE is just to make your code run slightly faster. Easiest way is to switch

`x != '0'`

into`x > '1'`

. Also try switching`int(x)`

into`(ord(x) - 48)`

.Thank you!

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?