### neckbotov's blog

By neckbotov, history, 17 months ago,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Code

Btw, congratulations to Benq on first-to-solve this problem!

• +55

 » 17 months ago, # |   +6 Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).
 » 17 months ago, # |   -53 I think pretests are weak for B.
•  » » 17 months ago, # ^ |   +26 Pretests are not weak, time-limit is tight
•  » » » 17 months ago, # ^ |   -46 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).
•  » » » » 17 months ago, # ^ |   +11 Numbers are up to 1e18, why do you feed int into gcd/lcm function?
 » 17 months ago, # | ← Rev. 5 →   -42 Wishing everyone HAPPINESS,LOVE,JOY and PROSPERITY.
•  » » 17 months ago, # ^ | ← Rev. 2 →   -13 Can div 2 C be solved without graphs usage? if so can someone explain how to solve it without graphs?
•  » » » 17 months ago, # ^ | ← Rev. 5 →   -27 Thanks in advance!
•  » » » 17 months ago, # ^ |   +7 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.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   -13 Thank you so much !!
 » 17 months ago, # |   0 Why in problem Div1C for the test 3 3 abcthe 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
•  » » 17 months ago, # ^ |   +11 the second case should be 1-2+4=3
•  » » » 17 months ago, # ^ |   0 ah, the first sign is not necessary "minus" :(
 » 17 months ago, # | ← Rev. 3 →   +29 Time limit for B is awfully tight for python. 101868901 and 101909293 have a mere constant factor difference but one TLEs and the other ACsmy -20 is now a -140 :(Upd : Got hacked xD
•  » » 17 months ago, # ^ |   0 Same thing happened with me. After contest, I used dictionary to store the answers. Here is my AC code. CODEdef valid(n): n = str(n) for i in n: if int(i)!=0 and (int(n)%int(i))!=0: return False return True d = dict() for _ in range(int(input())): nn = int(input()) n = nn if nn in d: print(d[nn]) continue while not valid(n): n+=1 d[nn]=n print(n) 
•  » » » 17 months ago, # ^ |   +14 That only works cause no one has bothered to make a counter test for it.
•  » » 17 months ago, # ^ |   0 Yes I got TLE too and that because of python same logic got accepted in any other language
•  » » » 17 months ago, # ^ |   0 Try to submit your code in pypy3 or pypy2. (Same logic accepted)
•  » » » » 17 months ago, # ^ |   0 Thanks mate it would help me for further contest
•  » » 17 months ago, # ^ |   +1 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.
•  » » » 17 months ago, # ^ | ← Rev. 4 →   0 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: HackedUpd2: AC 102366948
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » 17 months ago, # ^ |   0 After uphacking your code I continued hacking. Currently up to 391 uphacks on Div 2 B. The system tests were definitely lacking.
 » 17 months ago, # |   0 Can someone explain B?
•  » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ | ← Rev. 4 →   +4 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.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +10 I think I explained correctly in the rev 1..I gave my best .. But I don't know why I was down-voted.
 » 17 months ago, # | ← Rev. 2 →   +18 Problem C is Intresting!!! we can solve it with DSU too.
•  » » 17 months ago, # ^ |   +1 can u post the link to the code pls?
•  » » » 17 months ago, # ^ |   0 Yes, sure! 101952477
•  » » » » 17 months ago, # ^ |   0 Nice implementation. Mine seems like gibberish. xD
 » 17 months ago, # |   0 Can someone explain the editorial of Division 2C? I am not getting it
•  » » 17 months ago, # ^ | ← Rev. 4 →   +44 1.Ignore the rooks on coordinates of form (x,x) since they are already on the diagonal2.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.
•  » » » 17 months ago, # ^ |   +13 Very good explanation. I was searching for something like this. Thanks a lot.
•  » » » 17 months ago, # ^ |   0 Why do we build the edges like this, I can't unserstand.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +17 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.
•  » » » » » 17 months ago, # ^ |   -7 WOW！ Wonderful explanation. I get it. I'll put it on my blog.
•  » » » » » 17 months ago, # ^ |   +5 Will undirected edge make a difference?
•  » » » » » » 17 months ago, # ^ |   0 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.
•  » » » » » » » 17 months ago, # ^ |   +3 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.
•  » » » » » » » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   +3 Won't there be multiple such graph? Consider 4 points (x,y), (x2,x), (x3,y2), (x4,x3). Nice explanation though.
•  » » 17 months ago, # ^ |   0 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 isnumber of cycles + number of rooks not on any (i,i)This is my submission link 101935324
•  » » » 15 months ago, # ^ |   0 Sir will you please tell me the algo which you used for counting the number of cycles in your Graph,I know DFS but cant get your code,please share some resources if necessary,Thanks in advance.
 » 17 months ago, # |   +26 How to prove that ternary search will work in Div1B/2D?
 » 17 months ago, # |   +18 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
•  » » 17 months ago, # ^ |   0 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!
•  » » 17 months ago, # ^ |   0 I think its not due to log factor but constant factor of set. i am not sure.
 » 17 months ago, # | ← Rev. 2 →   0 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.
 » 17 months ago, # |   +36 D1E Walsh-Hadamard transform solution: https://codeforces.com/blog/entry/85746?#comment-735491
•  » » 17 months ago, # ^ |   0 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?
 » 17 months ago, # | ← Rev. 2 →   +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.
•  » » 17 months ago, # ^ |   0 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).
•  » » » 17 months ago, # ^ |   0 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
•  » » » » 17 months ago, # ^ |   0 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.
•  » » 17 months ago, # ^ | ← Rev. 5 →   +4 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.
•  » » 17 months ago, # ^ |   0 Either will do, but not both. We need to move a rook from $(x,y)$ to either $(x,x)$ or $(y,y)$.
 » 17 months ago, # |   0 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.
•  » » 17 months ago, # ^ |   +18 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".
•  » » » 16 months ago, # ^ |   0 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
•  » » » » 16 months ago, # ^ |   0 Check their submission. Apparently you can directly edit the string? I always thought they were immutable...
 » 17 months ago, # | ← Rev. 5 →   0 Can anyone tell why this code for Div2-C is giving WA on test-5? Code...  map < int, int > which_col; ll n, m; cin >> n >> m; vector < pair < ll, ll >> v; ll non_diagnal = 0; for (int i = 0; i < m; i++) { ll a, b; cin >> a >> b; which_col[a] = b; // check for row b which has col a if (a != b) non_diagnal++; } ll cycles = 0; vector < bool > vis(n + 1, false); for (int i = 1; i <= n; i++) { if (!vis[i] && which_col[i] > 0) { vis[i] = true; ll j = which_col[i]; while (which_col[j] > 0 && !vis[j]) { vis[j] = true; j = which_col[j]; if (vis[j]) { cycles++; break; } } } } cout << non_diagnal + cycles << "\n"; 
 » 17 months ago, # | ← Rev. 2 →   0 .
•  » » 17 months ago, # ^ |   0 Yes, it is
 » 17 months ago, # |   -16 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 ?
•  » » 17 months ago, # ^ |   +60 Read D
•  » » 17 months ago, # ^ |   +1 I am similar with you, and I choose to sleep
 » 17 months ago, # |   0 why his code got AC, but the same code I got TLE?
•  » » 17 months ago, # ^ |   +1 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!!
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 The following change 101919959 fixes the issue. (Using the vis in while loop to validate)
•  » » » 17 months ago, # ^ |   0 wow, what is the difference? do you have an example?
 » 17 months ago, # | ← Rev. 2 →   -14 The problem B numbers are Lynch-Bell Numbers
•  » » 17 months ago, # ^ |   0 It's not. Lynch bell numbers can't have repetitive digits.
•  » » » 17 months ago, # ^ |   0 Oh yes! My bad.
 » 17 months ago, # |   0 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]
•  » » 17 months ago, # ^ |   0 The following change 101919959 fixes the issue. (Using the vis in while loop to validate)
 » 17 months ago, # | ← Rev. 3 →   +41 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))$: 101920713AC in $O(n + q \log (q))$: 101921489
•  » » 17 months ago, # ^ |   +17 I arrived at the same solution eventually. 101922707Instead 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 - Сумма диаметров were somewhat helpful.
•  » » » 17 months ago, # ^ |   +8 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.
 » 17 months ago, # |   +23 What's the proof for the greedy addition/subtraction in D1C?
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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, V should not exceeds the value we want) because you want to adjust V with 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!)
•  » » » 17 months ago, # ^ |   0 Can you please help me with the part on how we can obtain any sign we want on the first $n - 2$integers ? It was not clear to me from the editorial.
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 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: +---++-+ => (-+)(--++-+) => ++-+ => (--+)(+) => +
•  » » » » » 17 months ago, # ^ |   0 Wow ! I got it. So we just focus on the minus signs and do them one by one.
•  » » » » » » 17 months ago, # ^ |   0 Yeah, right. And choose right place to split so the last two elements are -+
•  » » 17 months ago, # ^ |   0 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
•  » » 17 months ago, # ^ | ← Rev. 3 →   +8 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])
•  » » 17 months ago, # ^ | ← Rev. 5 →   +3 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.submissionProof : 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$ .
•  » » 17 months ago, # ^ |   +8 Poman Numbers ( Div2 E/ Div1 C )Explanation of the greedy part of the solution + Commented Code Code /* IDEA 1. We have to assign signs (+,-) to different powers and make the "sum of powers" = T 2. ( As sign of last two powers is already fixed ) Change T = T - ( -2^(str[n-2]) + 2^(str[n-1]) ) T = abs(T) -> because if we can make T, we can also make -T 3. Initially consider the powers to be negative let sum = sum of powers = (-)2^(str[0]) + (-)2^(str[1]) + (-)2^(str[2]) ...... (-)2^str[n-3] let rem = T - sum -> The number we need to add to sum , to make it equal to T 4. We have taken 2^x as a negative power, ( i.e added -2^x to sum ) Suppose later on we want to change this sign to positive ( i.e we want to add +2^x to sum ) , we can add 2^(x+1) to the sum because: (+)2^x = (-)2^x + ( 2^(x+1) ) -> 8 = -8 + 16 Therefore we can try to contruct rem from the powers of 2. Read the code to understand better. */ #include using namespace std; #define int long long int n, T, pwr[26], cnt[60]; string str; void read() { cin >> n >> T >> str; pwr[0] = 1; for(int i = 1; i < 26; i++) pwr[i] = 2*pwr[i-1]; } int32_t main() { read(); // signs of last two powers are already fixed T = T - (-pwr[ str[n-2] - 'a' ] + pwr[ str[n-1] - 'a' ]); // If we can make T we can also make -T T = abs(T); int sum = 0, rem = 0; for(int i = 0; i < n-2; i++) { int x = str[i] - 'a'; // assigning all the powers negative sign sum -= pwr[x]; // incrementing the cnt[x+1], as we can add 2*(x+1) power to later // on change the sign of this power (2*x) to positive cnt[x + 1]++; } // rem -> The number we need to add to sum to make it equal to T. rem = T - sum; // cnt[i] -> the number of 2^i we have // We can either use the powers available in cnt or leave them as it is // Using a power will means we are reversing the sign of the power to positive. for(int i = 0; rem != 0 and sum != T; i++){ if( (rem&(1LL<
 » 17 months ago, # |   +13 Can someone please explain to me D. Grime Zoo? Thanks.
 » 17 months ago, # |   0 I found B to be the most tricky one!!!!
 » 17 months ago, # |   0 Can there be any approach of c without using graphs?
•  » » 17 months ago, # ^ |   0 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
•  » » » 17 months ago, # ^ |   0 Thankyou I was searching for this.
•  » » 17 months ago, # ^ |   0 Another approach 101883649.
 » 17 months ago, # | ← Rev. 2 →   +6 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.?
•  » » 17 months ago, # ^ | ← Rev. 9 →   0 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 >= aifinally if val becomes 0 our assumption was true i.e print 'yes' else 'no'Code Link: 101958203
•  » » » 17 months ago, # ^ |   0 Thanks!
 » 17 months ago, # |   0 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.
•  » » 17 months ago, # ^ |   0 watch the stream by ecnerwala
 » 17 months ago, # |   0 Can anyone tell why thus code is failing for 1234567890 https://codeforces.com/contest/1465/submission/101931003
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 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
•  » » 17 months ago, # ^ |   0 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 its digits 1,8.
 » 17 months ago, # |   0 Can anyone tell me that why Binary Search is not applicable in Div2 B?
 » 17 months ago, # |   0 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
 » 17 months ago, # |   0 How to solve the Div2 C with dsu?
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 17 months ago, # ^ |   0 Thank u very much. I have got it.
•  » » » 17 months ago, # ^ |   0 For Coordinates (x,y) how we are assigning the parents? And how the vertices are defined in your answer?
 » 17 months ago, # |   +14 How to solve div2-D with DP?
•  » » 17 months ago, # ^ |   0 From DP I think the time complexity would be O(n^2).
 » 17 months ago, # |   0 In question C, I got WA on test case 5. Here is link to my WA solution: here Here is link to Accepted solution: hereCan anyone help me, what's the difference in both of dfs? Everything else is exact same.
•  » » 17 months ago, # ^ |   +1 I also faced a similar issue
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 Solved.
•  » » » 17 months ago, # ^ |   0 Ohk, Yes I get your point. Thanks a lot for explanation.
•  » » » 15 months ago, # ^ | ← Rev. 3 →   0 Thanks
 » 17 months ago, # |   +34 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..
 » 17 months ago, # |   0 Someone plss help me with problem B https://codeforces.com/contest/1465/submission/101926615
•  » » 17 months ago, # ^ |   0 use long long instead of int to avoid overflow
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 It is still not working
•  » » » » 16 months ago, # ^ |   0 When you passed by value to your solve() function, it's accepting int, not long long. Change that and it's accepted.
 » 17 months ago, # |   0 Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).
 » 17 months ago, # |   0 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.
 » 17 months ago, # |   +6 Can anyone explain D a bit clearly? I dont understand the editorial.
•  » » 17 months ago, # ^ |   +8 WLOG assume $x > y$. Suppose we claim that replacing the question marks with 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.
 » 17 months ago, # |   0 DSU solution of problem C (Div 2)
•  » » 17 months ago, # ^ |   0 Thanks!!
•  » » 17 months ago, # ^ |   0 one doubt we are returning parent[a]=find(parent[a]), if i do like find(find(parent[a])) im getting TLE
•  » » » 17 months ago, # ^ |   0 Because it will take n^2 time for every iteraation
•  » » » » 17 months ago, # ^ |   0 okay
 » 17 months ago, # |   0 can someone explain div 2 D...
 » 17 months ago, # |   0 so amazi
 » 17 months ago, # |   0 anyone who didnot use brute force in div2B?
 » 17 months ago, # |   0 Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).
 » 17 months ago, # |   +6 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?
•  » » 17 months ago, # ^ |   +1 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
•  » » » 17 months ago, # ^ |   0 OOH I got it thanks!!! But is it possible if the weights weren't powers of two?
•  » » » » 17 months ago, # ^ |   +1 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
 » 17 months ago, # |   0 1411A — In-game Chat Whats wrong in finding if lens — nosOfBracketInEnd <= nosOfBracketInEnd to find if it is bad.
 » 17 months ago, # |   +1 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?
 » 17 months ago, # | ← Rev. 2 →   0 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) •  » » 17 months ago, # ^ | 0 If you don't know the right solution please don't spread wrong solution. •  » » » 17 months ago, # ^ | 0 I said potential  » 17 months ago, # | 0 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)$
•  » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # |   +21 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 emptytherefore 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 samenow 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 movetherefore, 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.
•  » » 17 months ago, # ^ |   0 Really appreciate the hard work you have put in writing this explanation. Thanks :)
 » 17 months ago, # |   0 I need help to debug this https://codeforces.com/contest/1465/submission/102001052
 » 17 months ago, # |   0 I am having difficulty in understanding the problem Div2D editorial. Can anyone help me understand it with DP?
 » 17 months ago, # |   +3 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
•  » » 17 months ago, # ^ |   0 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" hasnt been mentioned
 » 17 months ago, # | ← Rev. 2 →   0 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 $= 3$. And if we have a remainder of $1$, then we must make 2 cycles of length $2$.Suppose we have a cycle length $L > 3$. We can break it down into $3 \times (L - 3)$and get a greater product.
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Hi bro, do you know how to prove it is always optimal to take three?UPD: nvm, I find it
•  » » » 17 months ago, # ^ |   +3 We 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 $3$in the permutation ?
•  » » » » 17 months ago, # ^ |   0 Sorry, I haven't looked into that part
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 For any permutation of size $n$ that is also a single cycle of length $n$, you can renumber it such that: $\left( p_1, p_2, \cdots, p_{n-1}, p_n \right) = \left( 2, 3, \cdots, n, 1 \right)$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.
 » 17 months ago, # | ← Rev. 2 →   0 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.
 » 17 months ago, # |   0 can we solve div2 D Grime Zoo using Dynamic Programming ?..
 » 17 months ago, # | ← Rev. 2 →   +9 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!
 » 17 months ago, # |   0 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]) ?
 » 17 months ago, # |   0 can someone explain problem D
 » 17 months ago, # |   0 Do you have solution code for these problems?
 » 17 months ago, # |   0 what is the expected difficulty of problem div2C.
 » 17 months ago, # |   0 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.
 » 17 months ago, # |   0 How to solve the bonus in Div1C?
 » 17 months ago, # | ← Rev. 6 →   +19 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)
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 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: has 1e3 cases I/O is a single 64-bit integer per case the solving step runs 2520 times at most each step comprises of itoa and a few modular arithmetics Then 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.
•  » » » 17 months ago, # ^ |   +8 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. and the environment being 32-bit 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 .
•  » » » » 17 months ago, # ^ |   0 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!
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ |   0 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)`.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 Thank you!
 » 16 months ago, # |   0 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?