dcordb's blog

By dcordb, 6 months ago,

We (the setters) hope you liked the problems. Here is the editorial:

C++ solution
Python solution

Problem idea: dcordb

Solution idea: dcordb and Devil

C++ solution

Problem idea: Devil

Solution idea: Devil

C++ solution

Problem idea: Devil

Solution idea: Devil

C++ solution

Problem idea: Devil

Solution idea: marX and Devil

C++ solution
Python solution

Problem idea: Devil

Solution idea: Devil and dcordb

C++ solution

Problem idea: Devil

Solution idea: marX

C++ solution

Problem idea: gilcu3

Solution idea: gilcu3 and marX

C++ solution

Problem idea: Devil

Solution idea: Devil and antontrygubO_o

C++ solution

Problem idea: marX

Solution idea: marX and Devil

• +125

 » 6 months ago, # | ← Rev. 2 →   +2 Where are the time complexities?I usually find understanding a solution easier when the time complexity is indicated with the solution.Amazing contest, nonetheless.
•  » » 6 months ago, # ^ |   +1 Video Editorial of B1 and B2: Koa and the Beach
•  » » » 6 months ago, # ^ |   +11 Nice explanation, good to see the use of whiteboard which is rare nowadays.
•  » » » 6 months ago, # ^ |   0 Nice Explanation though!I was trying my own method but the "safe state" condition is checked with an if case.My SolutionBut I'm receiving the wrong answer in test case 2 (2142ndtoken)My method is:: Move out of safe step when the tide is going down such that you have the maximum opportunity of reaching next safe stateI'm not getting why its a wrong answer!Please help, thanks in advance!
 » 6 months ago, # |   +58 Lost the entire interest after seeing problem statement of B1 :(
•  » » 6 months ago, # ^ |   +11 That's why people moved to C
•  » » » 6 months ago, # ^ |   +3 C and D protected my life
•  » » » » 6 months ago, # ^ |   +10 seriously dude, you didn't even participate.
•  » » » » » 6 months ago, # ^ |   +4 It's Beyond Science
•  » » » » » » 6 months ago, # ^ |   +4 I think you got it.
•  » » » » » 6 months ago, # ^ |   +3 Maybe he/she uses a fake account lol
•  » » » » » » 6 months ago, # ^ |   +16 I don't get the point of making many accounts. why would you make an alt account just to post bullshit?
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 No idea. Maybe retirednoob can give a better answer
•  » » » » » » » 6 months ago, # ^ |   0 Listen, why people made fake account because they have impostor syndrome. I also have faced same issue. they changed accounts to hide their failures from people. they have changed them self a bit, hopefully they won't do this again.
•  » » » » » 6 months ago, # ^ |   0 seriously dude, he didn't even tell you.
 » 6 months ago, # |   +8 In Div1D, the time complexity is $O(nm)$, so the limits could have been higher as I think of it.Was it intentional (so that one would think of it more as a $O(n^3)$, flow-like problem, for example)? Or possibly a change of mind -- maybe wrote a cubic solution, found the square one after?
•  » » 6 months ago, # ^ |   +44 If you push the limits to as high as possible that will fit within TL, you may be unnecessarily giving away info to the contestants. In this case making it so that $O(nm)$ is the only complexity that fits within TL tells you that the algorithm must be of that complexity. Imo it makes sense to leave it this small so it remains ambiguous (and still doesn't let any inefficient solutions pass).
 » 6 months ago, # |   -18 Long statements + weak pretests
•  » » 6 months ago, # ^ |   -51 Problem setter thinks he is very smart but he is a kid, don't know who allowed him to set problems.
•  » » » 6 months ago, # ^ |   +4 The contest was good and I liked it even tho I couldnt solve any problem, I enjoyed the 2 hours. Speak for yourself.
•  » » » » 6 months ago, # ^ |   +2 It's not about solving problems, just look at the description & difficulty of the problems and points assigned to that problems, Totally unfair. C-1750, B-500/700.
 » 6 months ago, # |   -9 Devil I think you made undirected graph in solution of div2C :)
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 graph will be undirected only , since we need to find size of the connected component , thus we need to visit all the nodes (to mark them and thus to find size of the connected component) . It's "connected" not "strongly connected" in editorial .
 » 6 months ago, # |   +6 lost interest in this round due to B problem statement
 » 6 months ago, # |   +5 Graph solution for problem div2 C (div1 A) is beautiful . Can some tell other approach without using graphs.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Please read the solution in this comment. Also you can read the explanation of the same written by yash1402_. Hope it helps!
•  » » 6 months ago, # ^ | ← Rev. 2 →   +14 If any character in $A$ is greater than $B$ at a particular index then it is not possible to transform $A$ to $B$.$Rule$ : Do not touch the indices in which $A$ and $B$ match.And now follow the following processFirst we look at the indices with contain $"a"$ in the string $A$ and look at the same indices in $B$ and let minimum among those indices in $B$ be $X$. Now replace characters in $A$ in those indices to $X$. Now one operation is performed. Similarly repeat the process to $"b"$, $"c"$ $.....$ $"t"$
•  » » 6 months ago, # ^ |   0 Yes,I used set to solve that problem --> Link
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 I used C++ Maps (storing pairs and their frequency) to solve the problem. I'm surprised to see so many people using graphs. -> 87923309
•  » » 6 months ago, # ^ |   +14 It is obvious that, if the first string has a character with higher value than the second string in at least one position, there is no solution.Now for the non trivial case: If we need to transform at least one instance of character x into a higher character y, then there is no harm in transforming ALL instances of x into y (it is still going to be one move), as long as we consider the potential y characters in increasing order (otherwise we might leap over relevant characters and increase some instances of x too much). While there potentially is a benefit, i.e. reduction of the number of necessary moves in cases like the following example: for strings aab and bcc we need to transform a -> b, a -> c, b -> c, and when transforming both a's to b then both b's to c, we achieve the desired result without the need to spend an extra move for a -> c transformation. The potential x characters should be considered in increasing order too, to avoid making a move before it gains full potential accumulated from potentially transforming lower characters into x first. Fill a matrix M with 20 rows and 20 columns as follows M[x][y] = true, if at least on instance of the x-th character ultimately needs to be transformed into the y-th character, false otherwise. Only the half of the matrix strictly above the diagonal is of interest, because if M[x][y] = true for some x, y where x > y, then we are back at the trivial case, and if x = y, there is no transformation required. Now iterate over potential x-th characters in increasing order, for each iterate over potential y-th characters, where y > x. For the first encountered M[x][y] = true entry (if any), count plus one move, and iterate over the rest of the entries in the same row, i.e. over z-th characters for z > y. For each entry M[x][z] = true, make M[y][z] true, as this is simulating transforming all instances of the x-th characters into the y-th, while keeping track into what characters they need to be transformed ultimately.P.S. Really, this approach is not that far away from the graph solutions, since the matrix can be seen as an adjacency matrix of the graph. It is a matter of interpretation and I did not have a graph in mind when coming up with the solution.
• »
»
6 months ago, # ^ |
-30

include <bits/stdc++.h>

using namespace std; int main() { int t; cin >> t; while (t--) { int n; string a, b; cin >> n >> a >> b; vector<set>v(20); int f=1; for(int i=0;i<n;i++){ if(a[i] > b[i]){ f=0; break; } if(a[i] < b[i]) v[a[i]-'a'].insert(b[i]-'a'); } if(f==0){ cout<<"-1"<<endl; } else { int c=0; for(int i=0;i<20;i++){ if(v[i].size()>0){ c++; set::iterator itr,itr2; itr2 = v[i].begin(); itr=v[i].begin(); itr++; for(;itr!=v[i].end();itr++){ v[*itr2].insert(*itr); } } } cout<<c<<endl; } }

return 0;


}

Simple Solution Using vector<set> . Easy to Understand.

•  » » » 6 months ago, # ^ |   0 it is better use ideone for sharing code...
•  » » 6 months ago, # ^ |   +8 C++ std::priority_queue is also a nice way to solve this problem
•  » » » 6 months ago, # ^ |   0 Can you please share your solution with priority_queue? Thanks in advance.
 » 6 months ago, # |   +27 dcordb can you please you spoiler to display editorial (blogs), it will be more convenient like previous editorials.
 » 6 months ago, # |   +240 Solution of div1C only gives the answer but doesn't really explain how one might come up with that in the first place, so I'll try.First observation is having lots of letters in the first string is bad for us, so we want to join letters as much as possible. That is, suppose the solution does operations A->B, followed by A->C. We could have changed all As to Bs in the first operation to do A->B, B->C instead. B->A followed by C->A can also be replaced by B->C, C->A.From this, we might intuit that the solution consists of one very long chain in which we have a "snowball" collecting all original letters into the same letter.If the graph has no cycles, then such a snowball can simply follow the topological sort of the DAG (this is div1A). If there are cycles, then some vertices will be visited more than once. If you know that a vertex is going to be visited more than once anyway, you might as well put it as the first and last vertices in the order, since this guarantees that vertex can reach/is reachable by all others.What about the vertices you only visit once? Clearly there cannot be any cycles between them, so they are a DAG (and as we know any DAG can be solved with the topological sort). So the solution looks like: visit some set of vertices S, do topological sort on the rest, visit S again. To minimize the number of operations we want the DAG to be the maximum possible.
•  » » 6 months ago, # ^ |   +10 Really, thanks.
 » 6 months ago, # |   -25 Check out this video editorial of Problem CBrute Force Approach, hope you will like it :)
 » 6 months ago, # |   0 Question : C2 Koa and the Beach Can someone explain why the below test case below should have "NO" as a answer: 20 26 32 31 27 14 7 2 23 22 21 19 27 31 12 23 31 0 11 28 20 31 30
 » 6 months ago, # | ← Rev. 2 →   +34 I don't like editorial of 1384B2 - Koa and the Beach (Hard Version) So I'll write my own. I think it should be easier.Let s(p, t) is answer on question "is there way to reach position p at cycle of tide t?". I'll make numbering of tide cycle in following way [k, k-1, k-2..., 1, 0, 1, 2 ... k-1]. It will be much easier to understand later.So, now obviously, if 0 is island, then s(0, t) is true for any t. Next, suppose some s(p, t) is true, then if we get this existing way to reach p at cycle time t and just standby there, eventually we can either drown or stay infinitely. Obviously, if we drown then it is because tide increased. This means that for all i up to some point x value of s(p, i) is also true, unless you can stand there forever. So either whole segment from i to x is true, or all s(p, t) is true for this p. Position p where you can stand forever lets call safe position similarly with editorial.Now important part: we can drown only when tide increase, highest allowed tide is easy calculated. And that's why cycle of tide I defined in the way above, with increasing in the end. Because higher allowed tide — longer we can stay. And, this also means that cycle time with "bad" level of tide is in prefix and suffix of cycle. This all means that for any position p there is first (lowest) t for which s(p, t) is true. And, in this notation all possible cycle time for position p gives range from first time to the time when highest possible tide is reached during rise of tide. Thus, to solve the task we only need to find for each position p first t when s(p, t) is true.Now, consider three cases: if you stand on safe position p, to get earliest t in cycle for next position p+1 you should move at fall, so you move to next position at fall of tide and highest allowed tide. if you stand on unsafe position p when tide is rising, you just need to move forward as soon as possible, because if now you can't move forward, then on next time you can't also move forward, but if you can right now — it's earliest moment in cycle you can reach next position. if you stand on unsafe position p when tide is falling you just need to wait until you can move forward and not drown on next position p+1. So, for each position we just update earliest t, and total time complexity is O(n). 87931302
•  » » 6 months ago, # ^ |   -15 Video Editorial of B1 and B2: Koa and the Beach
•  » » » 6 months ago, # ^ |   +2 I liked the way you explained it. Nice and clear. But I don't like the fact that this problem was kept at B.
•  » » 6 months ago, # ^ |   0 could you explain why test case 3: 4 3 4 0 2 4 3 has a solution(i.e Yes)?
•  » » » 6 months ago, # ^ |   +3 4 3 4 0 2 4 3 On position 0 we can stay forever — it's island, so we should move on fall, so we move at t (cycle time) at 0 and arrive at t = 1 on position 1 because there will be 0+2 height which is less than 4. Also, at position 1 we can stay forever, so we should move at fall again. So, we will wait until t = 0 again and move at t = 0 and if we move then on next position we will have 2+2 which is alright, but we can't stay here forever because 2+3 > 4. This means that we now on falling tide and unsafe position. We need to move next as soon as possible. If we move now to position 2 we will have 4 + 1 height and drown, so we should wait once and after move we will have 4 + 0 height which is alright. Now, at position 2 we are in unsafe position and tide is rising, so we should move now (without any "if", because situation may only become worse). Now we move to position 4 and have height 3 + 1 which is alright. Similarly, on position 4 we are in unsafe position and tide is rising so we should move now, and successfully reach end. Each of this actions give earliest t for each positions, so earliest t array is: 0, 1, 3, 4, and corresponding tide: 3, 2, 0, 1.
 » 6 months ago, # |   +15 Next time please try to make smaller readable problems. Appreciated your efforts.
 » 6 months ago, # | ← Rev. 2 →   0 The largest directed acyclic graph can be computed using dynamic programming in n*2^n.I remember a nice CF blog on this, could anyone point it out.
 » 6 months ago, # | ← Rev. 2 →   0 DP solution to B1:87940952. dp[i][j]--> Can we be at location i at time j? So, if any of dp[n][j] is true, we can reach the island.
•  » » 5 weeks ago, # ^ |   0 i might be late, but can you just tell me how did you calculate the upper bound of second state of dp? i mean the time factor...
 » 6 months ago, # | ← Rev. 2 →   0 EDIT: Got it!My Code is Exactly like Editorial's.Can anyone Please tell me why is gives wrong for this simple case, ALTHOUGH it's giving correct output in my local Compiler.Tese Case: 13ddddddMy Local Output: 0Cf Compiler: 1
•  » » 6 months ago, # ^ |   +13 You don't clear your global arrays after printing -1.
•  » » » 6 months ago, # ^ |   0 Oh Crap!I've been stuck here like since forever. Thanks !
 » 6 months ago, # |   +5 I found the following trick to solve Div2 B with simple implementation. The idea is like sliding window and updating the initial interval of $(-k, k)$ that corresponds to decreasing tide $(-k, 0)$ and increasing tide $(0, k)$. This way of set up simplified the implementation so much, but unfortunately, I came up with this at the end of the contest. Here's my solution
 » 6 months ago, # |   +13 Kudos to testers and those who arranged the problems in order of difficulty.
 » 6 months ago, # |   +51 Solution videos for people who prefer to have things explained visually are available here.
 » 6 months ago, # |   0 Can B1 use array to memory state?
•  » » 6 months ago, # ^ |   0 It's ok！
 » 6 months ago, # | ← Rev. 2 →   0 How is my idea for Div1A different from the editorial?
•  » » 5 months ago, # ^ |   0 test yếu anh ơi
 » 6 months ago, # |   0 https://codeforces.com/contest/1384/submission/87885055 I am generating a 200 length string and initialising (n+1) strings with that. Now I just copy the common prefix of ith string to (i+1)th string and after the common prefix I just add a character different from the previously used one. Can someone please tell me what is the problem with my solution? It is failing at test case 32.
 » 6 months ago, # | ← Rev. 4 →   +3 In Div2C.For the testcase 1 4 aacb bcddThe topological order is acbd But we can't select the each pair of consecutive nodes because c-->b is not possible.Am i missing something?
•  » » 6 months ago, # ^ |   0 I think it's abcd.aacb -> bbcb -> bccc -> bcdd
•  » » 6 months ago, # ^ |   +8 I don't know but gave you +1 for ma boi killua
 » 6 months ago, # |   +4 Although the quality of problems is quite good, but the score distribute is not reasonable. Div2 B that cost me 1 hour time only values 500+750 score. Div2 C is quite easy, but values 1750. I solved 5 problems but get a lower rank than someone solved 4 problems because of this score distribute. Sad~
 » 6 months ago, # |   +3 In the code of div1 E, the DP transition is dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod; I understand get(0) and get(dist[i]+1) are the two cases in the editorial, but what does (dist[i] <= dist.back()) mean ?
•  » » 6 months ago, # ^ |   +3 Oh, I see. It seems that (dist[i] <= dist.back()) means let $w$ just end there !
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +8 Yes it does that, it simply checks if string $s$ can end at $i$. For future references here is same solution that handles that part more clearly: Div1E C++ solution#include using namespace std; const int mod = 1000000007; int main() { ios::sync_with_stdio(false), cin.tie(0); string s; cin >> s; int suf0 = 0; while(!s.empty() && s.back() == '0') { s.pop_back(); suf0++; } if(s.empty()) { cout << suf0 << '\n'; return 0; } int n = s.length(); vector dist(n); for (int i = 0; i < n; ++i) if (s[i] == '0') dist[i] = (i ? dist[i-1] : 0) + 1; vector dp(n), nxt(n+1, n); auto get = [&](int i) { return nxt[i] < n ? dp[nxt[i]] : 0; }; for (int i = n-1; i >= 0; --i) { dp[i] = ((s[i] == '1') + get(0) + get(dist[i] + 1)) % mod; nxt[dist[i]] = i; } int ans = n; if (nxt[0] < n) ans = (1LL * get(0) * (nxt[0] + 1)) % mod; ans = 1LL * ans * (suf0 + 1) % mod; cout << ans << "\n"; return 0; } Here I removed zeroes at the end of $s$ (and multiply by this, plus $1$ to ans), and replaced that transition with an easier one to understand (it. checks if $s$ can end at $i$ with a $1$).
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Why w end there must meet this condition?I think i understood it, your solution is more clear.
 » 6 months ago, # |   0 I find that if s="0", the solution will RE because it visited nxt[dist[0]+1] (dist[0]+1=2) and the size of nxt is $2$ !
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 Yes sorry, it will RE, it was an error modifying it to post it here, but model solution is correct.
 » 6 months ago, # |   0 In Div1E/Div2C, what is the motivation for: "and the answer is $2⋅n−|LDAG|−1$"?
•  » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ |   +21 That's bad when people have to look for explanations for editorials in random comments in random places of the blogs.
 » 6 months ago, # |   +1 Why the simple greedy solution isn't mentioned in editorial for Div2C?
 » 6 months ago, # |   -13 If you are keeping python as a submission language then please do some homework and check the comparative time it's gonna take in python or else change codeforces to cppforces.
•  » » 6 months ago, # ^ |   +3 Codeforces is already cppforces. Plenty of problems can't be solved using Python.
•  » » » 6 months ago, # ^ |   0 Just tell me why can't be solved. Are there any logic that python doesn't support or recursion call stack that cannot be increased. It's all about time. You just have to increase the time limit for python in order to make python compatible for solving the same logic.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   +13 You want to have all the benefits python offers and no drawbacks. Obviously this won't do. Python is slower and that's the price you pay for its flexibility and coding speedAlso, learn to use pypy. I see that you used vanilla python, that's rarely a good idea in cp. Pypy is hardly ever not enough for the first d2 problems if you have a correct algorithm
•  » » » » 6 months ago, # ^ |   0 That's just the way things are currently, where C++ has a big advantage over other languages. I'm not saying that it's right or wrong, but until this changes you'll probably be better off switching to C++.
 » 6 months ago, # |   +1 Case: x%4 == 3 if y%2=1 the first player takes one 1 and the game now is exactly the previous case with the first player as the second player. I think the author means the first player takes first 0 and then the game is exactly the previous case . Previous Case: x%4 == 3 && y%2 == 0 Or Maybe i am too naive to understand the Author's logic :)
•  » » 6 months ago, # ^ |   0 Thanks, it's fixed now :)
•  » » » 6 months ago, # ^ |   0 It's my pleasure man ! that you have considered it from your highness . Have a nice day / night ahead and Great luck for your future too :)
 » 6 months ago, # |   +3 Can anyone explain how we can solve Div2C using DSU?
 » 6 months ago, # |   0 felt more like Div.1 contest
 » 6 months ago, # |   0 Greedy solution for C 87971209
 » 6 months ago, # |   0 IMO in Div.2 only problem C and maybe D had somewhat of a proper score allotted to it. Rest all should have had a higher score allotted to them. Especially B2.
 » 6 months ago, # |   +3 For String Transformation 1, I am really struggling to understand the answer after the 2nd sentence. I would like to understand this graph solution, could anyone please explain it in more detail?
 » 6 months ago, # | ← Rev. 2 →   0 Can you please help me find error in my code ! This is Div 2 B (easy version) I have tried to copy the solution presented in the editorial, in python.It's giving max recursion error for test case: 20 40 69 59 67 9 69 34 27 6 0 4 25 34 28 35 17 0 9 28 62 1 9 87974537
 » 6 months ago, # |   0 This is how I solved Div2Blet h be an array where h[i] = l - d[i]Then divide h into segments [L, R] where h[L] >= kh[R] >= kh[i] < k (L < i < R)For each segment check if exist 2 indices i and j such that i + h[i] < j - h[j] then there is no solution. Otherwise, a solution exists
 » 6 months ago, # | ← Rev. 2 →   +11 for mask in 1..2^n-1 for u in mask: is_dag[mask] |= is_dag[mask & (1 « u)] && ((mask & reach[u]) == 0)) Should it be: for mask in 1..2^n-1 for u in mask: is_dag[mask] |= is_dag[mask ^ (1 « u)] && ((mask & reach[u]) == 0)) 
•  » » 6 months ago, # ^ |   0 Yes, it should be.
•  » » 6 months ago, # ^ |   0 Fixed, thanks.
 » 6 months ago, # | ← Rev. 2 →   0 haha
 » 6 months ago, # | ← Rev. 2 →   0 In problem C, I didn't use the graph approach and instead used for loop traversals to go through the array a like this:for(int i=0;ib[i]){ count=-1; flag=1; } } if(flag!=1){ for(int i=0;i
 » 6 months ago, # | ← Rev. 3 →   0 For DIV2C/DIV1 AFor this sample input 17 dgdfjjklhejkklWe can transform in just 5 steps,but author's solution is showing 6.Operations 3-e2-h4-j1,5,6 — k1,7 — lam I missing something?
•  » » 6 months ago, # ^ |   +3 1, 5, 6 — k is not correct. 1 is d while 5 and 6 are j.
•  » » » 6 months ago, # ^ |   0 Thanks,it seems I didn't read the problem statement properly
 » 6 months ago, # |   0 Can someone please explain me the graph solution of problem 3. I am not able to understand it from the editorial.
 » 6 months ago, # |   0 B2 solution by greedy 88017812
 » 6 months ago, # |   0 div 2 C seems to be a standard ques!! if yes then can you plz tell me more about this type of question!
•  » » 6 months ago, # ^ |   0 Maybe you'll find it useful https://codeforces.com/blog/entry/80593?#comment-668966 By the way, can you please tell how the number of transformations required for abcb to tsrs is 3 (as there are 3 connected components?)
•  » » » 6 months ago, # ^ |   0 a to t in 1 move , b,b to s,s in 1 move and c to r in one move so total 3 moves requires
•  » » » 6 months ago, # ^ |   0 i have 2 solutions for this problem1 (https://codeforces.com/contest/1384/submission/88019936) is what i did during contest and its kind of general solution i guess andthe other one(https://codeforces.com/contest/1384/submission/88049338) is very interesting solution
 » 6 months ago, # |   0 Anyone to explain :1383B — GameGame" editorial more easily please...?
 » 6 months ago, # | ← Rev. 2 →   0 For C1 my approach seems to be different from what the comments are mentioning. (*I also don't seem to have a proper proof for it but it seems to work intuitively and would be nice if someone wants to look into this*)I took characters of string B and sorted them in the increasing order. (Let's call the smallest value of such a sorted sequence as SML)My claim is that if we try to change the characters of string A whose character in the corresponding same position in B is same as SML or once such character is found then every occurence of the same character in A will be changed to SML and the number of such distinct characters which were changed to SML will be added to our final answer.Now first turn is over SML will pick the next smallest element and will redo the above again.Finally all characters in A will be changed to the ones in B and the answer will be minimum.I used set of pairs to implement it.If there are any counters to the above explanation they are most welcome. (Since I am not sure why my approach actually works besides few samples I checked with pen and paper)https://codeforces.com/contest/1384/submission/88045399
 » 6 months ago, # |   0 In Div.1F, the time limit seems so tight after some very strong hack testcases were added, and it's so difficult to pass them. By the way, can anyone tell me how to get max flows quickly.
 » 6 months ago, # | ← Rev. 2 →   +6 I have some questions on 1383B - GameGame : why we dont have to consider higher bits when we're processing the first bit that the number of ones is odd? (or : why we can turn these numbers into an array of $x$ ones and $y$ zeros? should we consider the influences of higher bits (though their number of ones is even) ?)i'll appreciate it if you can explain these questions to me :)
•  » » 6 months ago, # ^ | ← Rev. 2 →   +16 If number of ones is even for any higher bits. Then irrespective of distribution, both players will have either odd or both players will have even number of bits . So both will end up having same value(because of same parity) for that bit. This is the explanation I gave to Myself .
•  » » » 6 months ago, # ^ |   +3 many thanks!
•  » » 6 months ago, # ^ |   +3 If the number of $1$ is even for a bit, then the final result could be only: Both two players take even count from it, they both get $0$ on that bit. Both two players take odd count from it, they both get $1$ on that bit. which will always make a tie on that bit. The order doesn't matter.It could be confusing, so you can have a simulation.
•  » » » 6 months ago, # ^ |   0 thx!
 » 6 months ago, # |   +8 In div 1 E editorial, I don't understand this part:"if the $(j+1)$-th character in $w$ is 0, and we have $k$ zeros after the last 1 in $w$ find the next block of $k+1$ zeros in $s$, (ie first $i'>i$ such that for each ($0\le k' •  » » 6 months ago, # ^ | +8 Oh that was a typo, as it says in editorial and as you can see in sample solution, if you have a block of$k$zeros, and you want another$0$, you should search for first block of at least$k+1$zeros.For example:$s = ...100\underline{0}100000$you are on the underline (suppose$w = ...1000$) and you want another zero, for this you can merge$0001$with some previous$1$(remember we ensured that one always exists) and search for next block of at least$4$zeros (the merge would look like$...10001|0000...$). In this way you would have$w = ...10000$. •  » » » 6 months ago, # ^ | 0 Thanks, I understand the greedy part now but am now having trouble understanding the DP. The editorial says"Let$dp(i)$be the number of strings that we can obtain using the last$n-i$characters from$s$"However, running the model code tells me the dp states used in it are not exactly the same. It gives the following values for these suffixes: s: 0 1 1 1 0 0 dp: 9 9 6 3 2 1 Note that the actual number of things you can construct from 011100 is 18, not 9. It should be double the number of things you can construct from 11100 because you can choose whether or not to put the 0 at the beginning. Could you explain what the dp states in the solution actually represent? Thanks! •  » » » » 6 months ago, # ^ | +8 Yes, the dp is well defined in each one, remember that at the end we use$dp(i)$where$i$is the position of the first one. •  » » » » 6 months ago, # ^ | +8 If it helps, try thinking about it in this other way (this is how I first solved):Let$dp(i, c)$be the number of strings we can obtain from last$n - i$characters of$s$such that they start with exactly$c$($c \ge 0$) zeros. The transitions are the ones in editorial.Then you can notice that you don't need second state if at the transition you force to add$k$($k \ge 0$) zeros and then a$1$.Oh and about dp giving$9$, well remember you had a zero before first$1$, so you should multiply by a$2$(ie. ans is$dp(2) \cdot 2$). •  » » » » 6 months ago, # ^ | ← Rev. 3 → +8 I have a feeling that we might misunderstand that text for dp[i]. A better example of explaining the mismatch would be: i 0 1 2 3 4 5 6 7 8 9 s 0 1 1 1 0 0 1 0 0 0 dp 47 40 28 16 11 6 4 3 2 1 Notice i=5, s[i]=0, according to the text, it is the number of string we could make using last n-i=10-5=5 characters. This number should be 8 instead of 6 (following the def. of dp)I think a better way to explain dp[i] is the following:dp[i] is the number of strings that you make where you must keep all preceding consecutive 0s when s[i] = 0, otherwise (if s[i]=1), it's the number of string that you can make to so that you keep this s[i] = 1.This explanation is kind of echoing with the greedy method in the tutorial.In the example above, dp[5] is the number of extensions where you must keep s[4] and s[5] and you try to extend this with a 1 or a 0 (corresponding to the get(0) and the get(dist[i]+1) component). More specifically, when s[i] is not followed by a 0 (like in the case for s[5]), you have to seek for the consecutive 0 block that is large enough. And finally, you can extend it with nothing if the ending 0 block is large enough or you are extending a 1. That's the dist[i] <= dist.back() component.This is what dcordb was talking about for the leading 0s I believe.I hope the tutorial is technically clearer for the ignorant like me :P. But I think the problem and the solution are both quite good and I very much appreciate the efforts of the problem setter.  » 6 months ago, # | 0 In the solution for b1 what does this code correspond to? function go I mean, I understand the meaning but I haven't seen this kind of syntax till now....... •  » » 6 months ago, # ^ | ← Rev. 2 → -10 It is the return type of a lambda expression. •  » » » 6 months ago, # ^ | 0 ok thanks! •  » » 6 months ago, # ^ | -10 It's a lambda function in C++. Read about them Here. •  » » » 6 months ago, # ^ | 0 Will do thanks! •  » » 6 months ago, # ^ | ← Rev. 2 → +52 Despite what the other commenters say it's actually not a lambda! It's a std::function.A std::function does type erasure magic and you can assign lambdas, function pointers, and callable structs (anything that is callable) to it. This type erasure comes at a cost.To actually have a lambda function you need to assign it to an auto variable. The type of the lambda is generated at compile time and you can't know it/type it yourself.Edit: For clarity. The right hand side of the assignment is a lambda function. But it gets converted to a std::function in the assignment. •  » » » 6 months ago, # ^ | 0 All right...  » 6 months ago, # | 0 Omkar , yes bro. I am from the group XD  » 6 months ago, # | 0 Is there any other approach for problem C  » 6 months ago, # | 0 Problem B1 : How the depth increased by time t = (t % 2k) ?? If so then the depth can be increased more than k which is not possible according to the statement. Help please... •  » » 6 months ago, # ^ | 0 its more like depth increases by A[t], where t = (t%2k), take for example k = 3 array A = [0,1,2,3,2,1] so at time t = 0, depth increases by A[t%2k] = A[0]. similary at t = 4, depth increases by A[4%6] = A[4] = 2. •  » » » 6 months ago, # ^ | 0 Thanks brother...Now i get it :) » 6 months ago, # | -27 include<bits/stdc++.h> using namespace std; typedef long long ll ; set<tuple<ll, ll, bool>> mark ; bool dfs(ll n, ll pos, ll &tide, bool &down , vector &d , ll k , ll l) { if(pos > n) return true ; if(mark.find({pos,tide,down}) != mark.end()){ return false; } mark.insert({pos,tide,down}) ; tide += down ? -1 : +1 ; if(tide == 0) down = false ; if(tide == k ) down = true ; if(d[pos] + tide <= l && dfs(n , pos, tide , down , d, k , l)) return true ; if(d[pos+1] + tide <= l && dfs(n , pos+1 , tide , down , d , k , l)) return true ; return false; } int main(){ ll t ; cin>>t ; while(t--){ mark.clear() ; ll n , k , l; cin>>n >> k >> l ; vector<int> d(n+2 , -k ) ; for(int i=1 ; i<=n ; i++) { cin >> d[i] ; } ll tide = 0; bool down = false; if( dfs(n,0 , tide, down , d, k, l) ) cout<<"Yes"<<'\n' ; else cout<<"No" << '\n' ; } return 0; } I am struggling why my code is showing wrong ans •  » » 6 months ago, # ^ | 0 next time post submission link and what task  » 6 months ago, # | ← Rev. 2 → 0 my dp solution for B1 using 2 states — https://codeforces.com/contest/1384/submission/88165283I want to verify time complexity — I think it should be n * k as for every index k times are possible i.e. earliest you could reach is i + 1 and latest you could reach is i + k  » 6 months ago, # | 0 1383E - Strange Operation I think my understanding of DP is very good. But even I had trouble with editorial even thought I solved it in the first place! So, for those who want to learn all that magic few people understand, I'll try to explain it as much as I can. Horrible wall of textFor completeness, I'll repeat some of things from editorial. First thing we need to know is: maximum of bits is equivalent to bitwise OR. And result of any sequence of merging two bits is equivalent to: pick set of segments, replace them by their bitwise OR.Now, suppose we have feeling that this task should be DP, then what our thoughts? Well, main thought: what is state? State should be all possible way to do something. And here is a trouble: how can we make sure that all those ways are different? The state itself should guarantee that. And mind is blowing when you think that this one can be vanished or keeped, similarly zero can remain or keeped. And here where I stuck. Then, I had idea to have dp based on fixed one, but it doesn't help, because even if I knew how many ones I have before, I had no idea how to make sure all sequences are different.Honestly, here I stuck, but I had feeling that I should somehow know that my sequences are different for sure. But I had no idea. So I read beginning of editorial. Very beginning. To get a hint. And this hint was enough. Hint was a bit other, but here is hint I propose for all of you who read this: for any string we can make, we should be able to construct it, so find out how to check is it possible to construct given string.Task from now is: find out algorithm for checking: can we make from sequence$s$sequence$t$. That's it. And solution is easy: for each part of$t$we will pick first place where we can make it in$s$. So, we will start from empty sequence, and append bits to it. This leads to two cases: if next bit we need is 1 then we just find next unused 1 in$s$. If next bit is 0 then we need to find first place with enough number of zeroes we want, because in$t$we can only shrink number of zeroes. There is one corner case: we can't skip anything if we don't have ones yet, but we can deal with it separately.Now, crucial observation: sequence of steps of this greedy algorithm is deterministic, so any different input t for fixed s gives certain sequence of steps. I didn't say unique. It's true but it's much harder statement than I want to prove first. First, we will change greedy slightly for easier analysis.Let's change greedy in following way: for next bit 0 instead of looking for group of enough size we will look for first zero instead. And if you can't get next zero without remove of previous one — we just forbid this action. It's a bit vague words so I'll provide example: s = 001010110001 t = 0101001 0 1010 - what we was able to make Here we can't make second 0 because we need to somehow jump to next group of zeroes. So, my initial solution had this as a bug in idea, but it is good way to explain I think. Why? Well now we have addition of 0 and 1 single bit by bit and we able to tell can we make$t$by steps of this greedy algorithm. You can think of it as if we count all different sequences of bits which can be made by this greedy algorithm. We will solve this first, because it's easier and it will give idea how to solve initial task.Now, if we look carefully on how this greedy algorithm works we will see that depending on next bit (zero or one) we make different jumps in$s$. Thus, we can draw arrows from each cell: one arrow where we land if next digit is 0, and one arrow where we land if digit is 1. Some of cells don't have jump by zero (because we already have 0 and we can't remove 0 and arrow by zero means we want zero, but next symbol in$s$is not 0 so we should remove trailing zeroes and make new group but we decided to forbid it, because it's simpler version) This is graph of transitions. And crucial thing is: in this graph each edge from vertex is jump by different next bit. This means that any unique path corresponds to unique bit string. The number of different paths in graph like that is easy to calculate, because this graph is top sorted. So Either we go forward add value of dp in current position into dp of all positions where we can jump into — I call it forward push dp in my terminology. Either we go forward and add into dp of current position sum of dp of all positions from where we could come here — forward pull dp in my terminology. Either we go backwards and add into current dp of current position sum of dp of all positions where we can jump into — backward pull dp Either we go backwards and add value of current dp in current position into all positions from where we could come here — backward push dp I don't know if anyone else use similar terminology. push is when you add influence into next position, and pull is when you grab around values. Backward and forward makes sense only if you have ordering like in our case.Now two things not covered yet: we haven't talk about ending. We can end at any 1 (by bitwise OR of everything else in the end). And we can end at zero if it's in the end. Also, we need to take into account reaching first 1. So total number of unique sequences of bits of this greedy algorithm is: number of ways to get first 1 multiplied by number of unique paths to ones or trailing zeroes.At last, back to original problem. Note: I don't want to explain my solution in details. It's not important. My idea to fix this was using greedy algorithm we had before modification was made. Instead of picking first zero I just need to make all possible ways of jumps by number of zeroes. It's up to$|t|$number of arrows from each cell. Each arrow is where I would land if I need exactly certain number of zeroes. To deal with it I postpone jumps into next groups of zeroes. Actually it was postpone addition of values of dp instead of jumps itself. And to avoid big amount of postponed addition I used stack and it did work. By the way it was forward push dp, and it was only over 1 bits. 88154272Now, instead of my idea, we will do a bit different thing. Now we can see how each sequence of bits without skip of groups of zeroes is possible to make. All we need is somehow if we don't have enough zeroes, somehow we want be able to go to the next group of zeroes. And here comes the trick! If we stand in third zero in group, like this: ...100001... ^- we stand here then there is only one way to reach third zero in group: to start from first one and make step by zero arrow twice. Why? Well, because all arrows by 1 is pointing into 1. It means, that by index of zero in group we know exact number of trailing zeroes we have! And, it means, if we stand in last zero in group and want one more zero, then we need group with at least one more zero. And after addition of this additional zero we also know how many zeroes we will have, so we know to which zero we need to make arrow by zero. This zero where we will make arrow — will have number of zeroes strictly determined by position in its group. So everything match. Index of zero is at the same moment: part of state and how many trailing zeroes we already have. Basically each position define last used bit for merge and number of trailing zeroes at once. And that is core of the solution. All what is left is to take care of zeroes in front of string and in end of string.Now, regarding the code in editorial. It is just backward pull dp (in my terminology) over graph I just described.$dist$is number of zeroes before (index of zero in group, 0 if it's bit 1).$nxt$is position of next zero at certain distance (with certain index of zero).  » 6 months ago, # | ← Rev. 4 → +101 I might be too late to the party, but I am presenting my own solution for 1E anyway.Let's solve the problem where the first and last character are both 1, because the beginning and ending zeros can be counted and multiplied into the final answer trivially.Between any two consecutive 1's, let's count the number of 0's, and store it in an array a. So we can "compress" our string into$\texttt{1 } a_1 \texttt{ 1 } a_2 \texttt{ 1 ... 1 } a_k \texttt{ 1}$, where$a_i$is the occurrence of 0's between the$i^{th}$1 character and the$(i + 1)^{th}$1 character. The problem can be then transformed into: for each element$a_i$, replace it with a value from$0$to$a_i$, or remove the element from the array completely. Count the number of possible arrays that can be made this way.I denote$dp_i$to be the number of different arrays that end in the value$i$, and denote$tot$to be the total number of different arrays. Clearly$tot$would be our answer, and$tot = (\sum{dp_i}) + 1$. Let's maintain this$dp$and$tot$.Iterate over$a$. When we loop over$a_i$, clearly only$dp_j$where$0 \leq j \leq a_i$change, so let's see how they change. We have two cases of what to do with$a_i$: Remove this element completely.$dp_j$does not change. Replace$a_i$with$j$. We can make$tot - dp_j$new arrays this way, since we create$tot$arrays from appending$j$to the previously existing arrays, but$dp_j$of them has appeared before. Therefore,$dp_j = dp_j + tot - dp_j = tot$. In other words, when we loop over$a_i$, we assign$dp_j = tot$for all$0 \leq j \leq a_i$, then update our$tot$. The complexity would still be$O(|s|)$.However, I think this solution is much more interesting because this can solve the problem if you are given the string in a compressed manner. When a block of$0$'s comes, update the$dp$like mentioned. When a block of$1$'s comes, calculate what$dp_0$would be after processing all the$1$'s. We can use a stack to implement this in$O(|compress(s)|)\$.
 » 6 months ago, # |   0 Can anyone explain the solution of div2-D/div1-B more elaborately? I can't catch the core of the given solution. Thanks in advance...
 » 6 months ago, # |   0 Div 2 D/Div 1 B was beautiful, thanks
 » 5 months ago, # | ← Rev. 2 →   0 i'm trying to solve B1 problem with the following approach-start at t=0 and see if we can reach i+1 without drowning. if we cannot then wait at i. and if both are not possible then start at t='k' seconds and repeat the above steps. if both are impossible, then return false. If anyone of the two gives i==n-1 then return true.Why is this not working? I'm new to competitive prog. so don't judge :)
 » 5 months ago, # |   0 on the problem string transformation 1, I think the test is really week. My solution is o(n^2+nlogn) but still accepted.
•  » » 5 months ago, # ^ |   0 #include #include #include #include using namespace std; long long solve() { vector f[300]; long long n; cin >> n; string a,b; cin >> a; cin >> b; for (int i=0;i b[i]) return -1; vector > dp; for (int i=0;i> t; while (t--) { cout << solve() << endl; } return 0; } 
 » 5 months ago, # |   0 Is there is any other source to understand how to solve problem c string transformation as i can not understand the editorial?
 » 10 days ago, # |   0 What's with all those hacks in div1F?