### djm03178's blog

By djm03178, history, 13 months ago,

The problems with Gildong (B, D, F) are by me, and Amugae (A, C, E) are by hyunuk.

• +157

 » 13 months ago, # |   -38 Fast Editorial. :)
•  » » 12 months ago, # ^ |   0 i have no idea why people downvoted this comment
 » 13 months ago, # |   +14 I wrote D different way. Consider each row. If it can be made white, max — min + 1 indices for black dots are <= k. Then we know the rectangle that, if we pick any point in it, will give us +1 to answer (that row will be white) We cannot add 1 to all points of it though, that is O(k^2) operation, so we mark starts with +1 and end points with -1 for each row. That makes it O(k). We do same for columns and pick biggest value.
•  » » 13 months ago, # ^ |   0 reading input takes O(n**2)
•  » » » 13 months ago, # ^ |   0 Yes, and O(n^3) is too slow
•  » » » » 9 months ago, # ^ |   0 You mean O(n^2 * k) right? The editorial above mistakenly says O(n^2), which I was unable to understand how until I read this comment.
•  » » » » » 9 months ago, # ^ |   0 If k is equal to n, then O(n^2 *k) becomes O(n^3) and is too slow, so I did not mean that
•  » » » » » 5 months ago, # ^ |   +1 It's not a mistake in the editorial. The main solution is $O(n^2)$.
•  » » 13 months ago, # ^ |   0 Oh, I had the same idea as yours. But during the contest, I used a BIT to calculate the sum... I forgot I could calculate the sum afterwards. So I'm $O(nk \log n)$. And it passed too.
 » 13 months ago, # |   0 so fast Editorial!
 » 13 months ago, # | ← Rev. 2 →   -6 can E be solved by Hashing?
 » 13 months ago, # | ← Rev. 2 →   +12 What is the test case 35 of C? Edit: works by replacing ceil with (x + n — 1) / n
•  » » 13 months ago, # ^ |   0 same too
•  » » 13 months ago, # ^ |   0 Same here. I feel so sad bruh =))
•  » » » 13 months ago, # ^ |   0 I forget to use long long for one of my variables.
•  » » » » 13 months ago, # ^ |   0 same, feels bad man
•  » » 13 months ago, # ^ | ← Rev. 2 →   +1 ceil is prone to error. Better write your own, like you said, or maybe implement something along these lines: #define ll long long ll ceil(const ll &a, const ll &b) { if(a%b == 0) return a/b; return a/b +1; } 
•  » » » 13 months ago, # ^ |   +5 Better use (a — 1) / b + 1
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +13 You can use (a + b — 1) / b.
•  » » 13 months ago, # ^ |   -9 n=5*10^17, m=10^18. Gcd will be 5*10^17 and it's umportant to keep gcd in long long.
•  » » 13 months ago, # ^ |   0 500000000000000000 1000000000000000000 1 2 716004419141796031 1 358002209570898016 Built-in ceil function failed on this query
•  » » 13 months ago, # ^ |   0 consider use long long and long double for all varibles
•  » » 13 months ago, # ^ |   +5 Instead of using ceil I just switched to zero-indexed (subtract 1 from y) and use the default truncated integer division. Since the only thing we want to do with the group index is to compare equality, there is no need to convert back to one-indexed.
 » 13 months ago, # | ← Rev. 2 →   -16 deleted
•  » » 13 months ago, # ^ |   +5 sometimes , bruteforce is the best solution, just keep in mind the time complexity for the worst case :)
 » 13 months ago, # |   0 I got FST on test 15 on C, can someone please check what's wrong? $\to$ 58603533
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I'm wrong.
•  » » » 13 months ago, # ^ |   0 It should have an overloaded function for long long, and I've added the (famous) #define int long long before everything...
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 You will most probably encounter precision errors as you have use double data type, because the values are as high as 1e18!!
•  » » » 13 months ago, # ^ |   0 I used long double!
•  » » » » 13 months ago, # ^ |   0 Still it will give precision errors!!! check on local compiler!!
•  » » 13 months ago, # ^ |   0 Firstly #define int long long. There is one big cauldron for you guys :)But mainly reason is usage of long double. It is always bad thing when you need actually precise comparsion of long long.
•  » » » 13 months ago, # ^ |   0 I thought long double should be precise enough... RIP rating.
 » 13 months ago, # |   +15 It was honor to participate in.Thanks.수고하셨습니다.양질의 문제들을 제공해주셔서 감사했습니다 :)
 » 13 months ago, # |   +5 Could somebody explain this code? https://codeforces.com/contest/1200/submission/58594933
•  » » 13 months ago, # ^ | ← Rev. 2 →   +23 For prefix function one usually uses a string formed by: $S = pattern + \ + text$Where $is a symbol that doesn't belong to the alphabet just to be sure that we won't be getting an invalid prefix value of $pattern$. Here we go with some observations:1) Since $\pi[i]$ is the length of a prefix of $pattern$, then $\pi[i] \leq |pattern|$.2) In the usual preprocess, we initialize $j = \pi[i-1]$, but this can be dismissed by using $j$ as an outside variable and recycling it for the next iteration.3) Combining 1 and 2, we notice that we just need to compute $\pi[i]$ for $0 \leq i < |pattern|$ to get any $\pi[i]$ needed afterwards (it doesn't even depend on the value of $text$ :D). 4) Since we already have all that we need to compute any $\pi[i]$ without any extra data, we don't need to create $S$ as it is, just use a similar preprocess iteration over $text$ and take the last $j$ value (since that would be $\pi[|text| - 1]$, exactly what we need).The rest is just the implementation required to solve the problem and some optimizations (like just taking the last $min(|ans|,|word|)$ characters of $ans$).  » 13 months ago, # | 0 Hey! I got WA on test 26, can anyone point out error in my code? :) Here's my Submission •  » » 13 months ago, # ^ | 0 area1 = ((a==1) ? n*(b-1) : m*(b-1)); area2 = ((c==1) ? n*(d-1) : m*(d-1)); It will overflow here. •  » » » 13 months ago, # ^ | +1 Hey! Thanks for your response. I already figured it out. :)  » 13 months ago, # | 0 why my code fail in test case 35 https://codeforces.com/contest/1200/submission/58607383I'm using ceil function to get each group •  » » 13 months ago, # ^ | 0 same problem here https://codeforces.com/contest/1200/submission/58606476 •  » » 13 months ago, # ^ | 0 just use long double instead of double. the WA verdict was because of precision error due to division of large values •  » » » 13 months ago, # ^ | 0 Missing out due to overflow and precision issues is the worst feeling in coding ... •  » » 13 months ago, # ^ | 0 Hey! couldn't point out the error in your code (most probably some floating point error), but I am wondering why everyone here is talking about using doubles and floats etc. Only using long long works, have a look at this in-contest submission 58608243.  » 13 months ago, # | +1 What is the testcase 35 of C? Can someone spot an error in my code? http://codeforces.com/contest/1200/submission/58603084 •  » » 13 months ago, # ^ | 0 same happening with me...58621017..Anyone please explain..?? •  » » » 13 months ago, # ^ | 0 Replaced ceil with (sx + n — 1) / n and it worked. (https://codeforces.com/contest/1200/submission/58622681) Ceil in C++ is error it seems. •  » » 13 months ago, # ^ | 0 Seems, like in python double comparison is f**ked up. Since this passes by converting to int. https://codeforces.com/contest/1200/submission/58622224 •  » » » 13 months ago, # ^ | +1 Thanks •  » » 13 months ago, # ^ | +1 You should avoid to use real number when integer can solve  » 13 months ago, # | 0 Round was very good. but.. I was terrible. I couldn't solve E and F.  » 13 months ago, # | +12 It's easy to pass E by Hash •  » » 13 months ago, # ^ | 0 But it seems your solution can be hacked since your hashing is not randomized •  » » » 13 months ago, # ^ | 0 Double hash can hardly be hacked •  » » » » 13 months ago, # ^ | +3 I got accepted with quintuple hash 59377951 :)  » 13 months ago, # | 0 Can anyone find out where my code fails on B?I was stucked on it during the whole contest and still can't figure out. Your help would be much appreciated.https://codeforces.com/contest/1200/submission/58622597 •  » » 13 months ago, # ^ | ← Rev. 3 → +3 Okay three main issues: m == 0 should be changed to m < 0 > in else should be changed to >= And you can further decrease by k amount in else even after making them equal. Here is your modified code that passes:https://codeforces.com/contest/1200/submission/58624658 •  » » » 13 months ago, # ^ | +9 Wow man, thanks!i was able to figure out 1st and 2nd one but can't see that we can still decrease it. Tysm :)  » 13 months ago, # | ← Rev. 3 → 0 n = int(input()) words = list(input().split()) left = list(words[0]) for i in range(1, len(words)): RP = 0; for j in range(min(len(left), len(words[i]))-1, -1, -1): LP = len(left)-1-j; if (left[LP] == words[i][RP]): RP += 1 elif (left[LP] == words[i][0]): RP = 1 else: RP = 0 left.extend(words[i][RP:]) print("".join(left)) this is my submitted solution for E. I thought this approach is right, but it turned out to be not. could any one tell me why it is wrong? :D LP and RP are positions for left words and right words(indices for comparison) respectively •  » » 13 months ago, # ^ | +3 Some points why this doesnt work: You are incrementing LP and never looking back When your match fails, LP never goes to original LP+1, it continues from where it failed. You are missing to check all potential candidates which might have matched.  » 13 months ago, # | +3 I didn't understand the case that the wall at 12 o'clock always exists.What if n==1 or m==1? •  » » 13 months ago, # ^ | 0 I think , it means g = gcd( 1, 1 ) = 1 , that is only 1 common point that is 12 o'clock wall is there and both m and n are in same reason.  » 13 months ago, # | +5 Are the tests on E too weak or is there some "good" upper bound on the depth of links in suffix automata? My submission:https://codeforces.com/contest/1200/submission/58614095The 998ms is quite close to the time limit, but honestly I expected this will simply TL. •  » » 13 months ago, # ^ | 0 This part of your code works in linear time of current string's length, because you mark all suffixes of string: int term = last; while (term > 0) terminal[term] = 1, term = st[term].link; Total complexity is $O(W^2)$, where $W$ is sum of strings length. So, tests are weak. •  » » » 13 months ago, # ^ | 0 I hoped there would be some property of suffix automata links that would make the maximal link depth "much less than linear". Do you have examples where the maximum depth is really something like N or N/2? •  » » » » 13 months ago, # ^ | 0 Maybe something like this? 100000 a a a a a a a ... aaaa (99999 single a's and then 1 word of as a's as possible) for (int t = 0; t < n; t++) { while (term > 0) terminal[term] = 1, term = st[term].link; } Because the for loop for 1e5 times and the while loop for t times since all states are terminal states. •  » » » » 13 months ago, # ^ | +1 Maximal link depth equals to number of suffixes = string's length, so on reversed test of Gremio your solution will fail (prove: your solution is hacked within this test). Reversed, because firstly, you build big automaton, and then on each iteration you go throw all states of it.  » 13 months ago, # | +8 Hi — can someone let me know why my E solution is timing out? — https://codeforces.com/contest/1200/submission/58623121I imagine it to execute in linear time since all I'm doing is for the current final string and the next word to be processed, I'm hashing the suffixes and prefixes of same lengths and determining the largest length at which the hashes are equal.This length is the length of the prefix of the next word that I know I can skip since it's already present in my current ans string.My reasoning is, since I'm looking at every next word's character only once, the time complexity should be linear. Am I wrong here, or is my implementation inefficient?Any help would be much appreciated! •  » » 13 months ago, # ^ | ← Rev. 2 → +5 I believe the problem is in the way you are building the string ans with the string's += operator. According to here, time complexity could be as much as linear in the length of the resulting string, even if you are adding one character on the end at a time. Try push_back instead, which should be constant time amortized. •  » » » 13 months ago, # ^ | +5 Hi! Thanks for reading my code, I tried resubmitting after changing the line to push_back yet it still times out — https://codeforces.com/contest/1200/submission/58624588:( •  » » » » 13 months ago, # ^ | +29 I read your code and I made some changes for it to work.1) To avoid TLE, use the $ans$ global string, don't create a new one inside each call of the function ret since that will make it really slow.2) When we are using a modulo and we multiply, we should use the conditional if(val >= MOD) val %= MOD; Since the substraction of $MOD$ might not be able to get $val$ in the desired range $[0,MOD-1]$.3) For the rolling hash, one should use as $B$ factor a number greater than the maximum possible value of the characters we use: Since you are using ASCII code, the maximum value is $ASCII('z') + 1 = 122 + 1 = 123$, so $B = 26$ isn't enough. $B = 257$ and $B = 311$ are pretty good options for ASCII chars :D4) Your code doesn't print anything when $n = 1$, so I changed the way of computing the answer to: First add $A_{0}$, then for each $A_{i}$ with $1 \leq i < n$ add the correct substring.5) The total length might go up to $10^{6}$ so we need $p$ array to be at least that big.Your code with the modifications: 58630674 •  » » » » » 13 months ago, # ^ | +22 Oh wow! This is an incredibly helpful comment! Thank you a ton for reading and fixing my code, I really appreciate it. And thanks for sharing nice rolling hash values, this was one of the first times I'd implemented rolling hash out of intuition. Thanks! :) •  » » 13 months ago, # ^ | +10 for(10**5) ret(A[i+1]);And in ret() you copy the original string string a = ans;Copy can take 10**6 . So, in total 10**10 •  » » » 13 months ago, # ^ | +1 Thanks a lot. This helped! :)  » 13 months ago, # | +10 In C , how to prove that g = gcd(n , m) is the no. of dual walls. •  » » 13 months ago, # ^ | +6 Denote a wall by its clockwise angle from the 12 o'clock position, out of the full $360^\circ$. So the inner walls occur at $\frac{0}{n},\frac{1}{n},\dots,\frac{n-1}{n}$ and the outer walls occur at $\frac{0}{m},\dots,\frac{m-1}{m}$. An inner wall and outer wall coincide when there is a pair $(x,y)$ such that $0\le x< n,\ 0\le y< m$, and $\frac{x}{n}=\frac{y}{m}$. That is, $xm=yn$. So, $xm=yn$ is a common multiple of $m$ and $n$, so it is divisible by $\mathrm{lcm}(m,n)=\frac{mn}{\gcd(m,n)}$. So we write $xm=yn=\frac{kmn}{\gcd(m,n)},$and simplify to $x=\frac{kn}{\gcd(m,n)},\quad y=\frac{km}{\gcd(m,n)}.$The restrictions$0\le x
•  » » » 13 months ago, # ^ |   0 Nice!
 » 13 months ago, # |   0 My code of Div2-B, in my PC is given the correct answer to case:110 50 160319 47 107 192 866 475 139 594 636 345answer:NO But in codeforces is given YES Code:58603788Anyone can help me?
 » 13 months ago, # |   +11 Thanks for good contest, but personally for me editorial for E was useless and misleading, can't make head or tail of it... What is the purpose of taking min(z, y) if z is smaller than y anyway? Also the whole idea of authors solution seems very unclear to me, especially using prefix function(I got AC with z-function). I don't say that the solution is wrong ot smth but would really appretiate some alternative description of it)
•  » » 13 months ago, # ^ |   +10 Basically, suppose that you have currently formed the string $ans$ and you will add the string $word$. Then, to minimize the letters added, we need the longest string such that is a suffix of $ans$ and also a prefix of $word$ (we won't need to add this string since it's already formed in $ans$). Fortunately, prefix function computes exactly that if we use $word$ as pattern and $ans$ as text (so the answer would be $\pi[|ans|-1]$ with $\pi$ applied to the text).However, this method would be a TLE since $ans$ might be very long, so we use the following optimization: Since the string wanted is a prefix of $word$, then it's size is at most $|word|$. Thus, we just need to use the last $min(|ans|,|word|)$ characters of $ans$ to use as the text for the prefix function (since any more characters would be unused in the possible prefix).We finally end up with a complexity of $O\left(\sum\limits_{i=1}^{n}|word_{i}|\right)$ since each run of prefix function is linear respect to the length of $word$.I hope this helped :D
•  » » 13 months ago, # ^ |   0 can u please explain how u have solved D que??
•  » » » 13 months ago, # ^ |   +3 For problem D one can define a bad row or column as a segment that has at least one Black cell. Now, if we can compute how many bad segments turn all white when painting the square with upper left cell in $(i,j)$ in efficient time we can solve the problem iterating over all the valid cells.Now, we must notice that if we are handling with a horizontal line, we need to paint the leftmost and the rightmost black cell to make it all white. Thus, if our row is $r$ and the indices of the former black cells are $L$ and $R$ respectively, we see that if we want to make the bad line white we must choose a $(i,j)$ in the rectangle defined by the points $(minX,minY)$ and $(maxX,maxY)$, if and only if the distance between $L$ and $R$ is at most $k$. Since it will be a complete rectangle of cells to which we have to add 1, we can use the prefix sums technique for 2 dimensions, we will do: ac[minX][minY] += 1; ac[maxX+1][maxY+1] += 1; ac[minX][maxY+1] -= 1; ac[maxX+1][minY] -= 1; Now we can add up all the bad lines that will become white for each chosen cell using Inclusion-Exclusion Principle (check Max 2D Range Sum Preprocess for a better idea :D).But the most important question is: What are $minX,minY,maxX,maxY$? To answer this, we need to check that since any pair $(x,y)$ with $minX \leq x \leq maxX$ and $minY \leq y \leq maxY$ paints the bad line completely, it must hold that: $y \leq L \wedge y + k - 1 \geq R$Thus, $R - k + 1 \leq y \leq L$ and following a similar idea we get that $r - k + 1 \leq x \leq r$. Note: remember that also $x$ and $y$ are non-negative. We finally have: $minX = max(0,r - k + 1)$ $minY = max(0,R - k + 1)$ $maxX = r$ $maxY = L$You can handle with vertical bad lines in a similar way :DFinally, add all the values in $ac$ correctly and maximize the number of bad lines. After that, add the number of already white lines.I tried to explain the whole idea. I hope that it helps.Complexity: $O(n^{2})$.My code with the idea: 58630175
•  » » » » 13 months ago, # ^ |   +6 thanks for an excellent explanation and your time! Really helped a lot.
 » 13 months ago, # |   +9 Can anyone explain why these submissions : 58626941, 58626900 did not pass the tests but this one did — 58627018 ? Are small primes that useless?
•  » » 13 months ago, # ^ |   +7 The prime must be at least the number of characters we need to take care of. We have letters 'a' to 'z', letters 'A' to 'Z', and numbers '0' to '9' — a total of 62 characters. Thus, it's best to have a prime > 62
•  » » 13 months ago, # ^ |   +11 For rolling hash you need your $p1$ to be greater than the maximum possible integral value of the characters you'll use. Since we have an alphabet of size $62$, your $p1$ must be at least $62$ (considering that you mapped the characters to the range $[0,61]$).
•  » » » 13 months ago, # ^ |   +6 Ohh... Thank you guys! Happy coding.
 » 13 months ago, # |   0 why is my solution to E not passing TL? 58613989 I did it the same complexity as the editorial but the string i was running kmp on is simply the string in the editorial reversed.
•  » » 13 months ago, # ^ |   +3 The culprit is ans = ans + s[i][j]; Concatenation and string copying takes linear time, and you do this operation for each character, making your solution quadratic. Try ans.push_back(s[i][j]); instead, which is constant amortized.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 Uhm... isn't it already optimized? ans = ans + s[i][j] must already be optimized by the compilator... If not my mind is blown.Edit: you are right. it passed in 77 ms when b4 it was over 1000 ms. I deserve to commit not alive. Thank you!
 » 13 months ago, # | ← Rev. 2 →   0 My solution of E using double hashing failed on test #65.58609028Can anyone help me?Thanks.UPD: I found the mistake.
 » 13 months ago, # |   0 Can someone please explain how to solve D with KMP? Thanks!
•  » » 13 months ago, # ^ |   0 Isn't E？
•  » » 13 months ago, # ^ |   0 I solved E by KMP following the editorial. https://codeforces.com/contest/1200/submission/58665108I think the key point is to reset the longest border value in the center of c which is defined by editorial.
•  » » » 13 months ago, # ^ |   0 I think i could solve E by double hash ,but time didnt wait me:(
 » 13 months ago, # |   0 E can also be done with hash
 » 13 months ago, # |   0 Problem F's idea is similar to this problem https://codeforces.com/problemset/problem/1137/C
 » 13 months ago, # |   0 Can Someone please check why my code is giving WA on test case 9 in problem div2-D? 58651885
 » 13 months ago, # |   0 Can someone explain why my solution does not work, problem E : https://codeforces.com/contest/1200/submission/58657466. I use hash-function to compare substrings.
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 Try this test: "3 abc def cdef". Answer should be abcdef, but your program outputs abcdefcdef. Did you found your misunderstanding? :v
 » 13 months ago, # |   0 SUBMISSION what is wrong with this solution for B?
 » 13 months ago, # |   0 I use a silly way to solve C,but to my surprise it could get right for(int i=2;i<=70000000;i++) { if(t1%i==0&&t2%i==0) while(t1%i==0&&t2%i==0) { t1/=i;t2/=i; } } 
 » 13 months ago, # |   0 Can some please tell me why i am getting WA in test case 5 for problem E https://ide.geeksforgeeks.org/zDbvJinjIP
 » 13 months ago, # |   0 In problem B the test case is 2 3 1 0 999999 0 1000000 3 0 500000 0 500000 1000000 my answer is both YES but the answer is NO how??
•  » » 13 months ago, # ^ |   0 They are both YES. What made you think the answer is NO?
•  » » » 13 months ago, # ^ |   0 sorry my answer is NO but the right ans is YES . i made a small mistake in my code .
 » 13 months ago, # |   +5 Can someone help me? Why is this solution getting TL, problem E: https://codeforces.com/contest/1200/submission/58670102.I have ans — it's a result string.I use prefix-function to find the length of biggest prefix for each string s.The parameter for prefix-function is (s + "#" + ans).For example: if we have "abcdef" and "cdef"The parameter will be "cdef#abcdef". The biggest prefix is "cdef", size — 4.So i will add "", to the answer.
•  » » 13 months ago, # ^ |   0 You need to, optimize the string you use for your prefix function, since ans can be really long. Your just need to take the last $min(|ans|,|s|)$ characters of $ans$ since your common string cannot exceed that length. Also try not to use too much the $+$ operator for strings, it's faster to push_back the characters :D
•  » » » 13 months ago, # ^ |   +5 Thanks! :)
 » 13 months ago, # |   0 Can anyone please pin down code solution for Div2D following the editorial explanation?
•  » » 13 months ago, # ^ |   0 Here's one of the correct solutions. code#include using namespace std; const int MAX_N = 2000; string s[MAX_N], t[MAX_N]; int row_first[MAX_N], row_last[MAX_N]; int col_first[MAX_N], col_last[MAX_N]; int row_ans[MAX_N][MAX_N], col_ans[MAX_N][MAX_N]; int base = 0; int n, k; void find_first_last(int *first, int *last, string *board) { int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) if (board[i][j] == 'B') first[i] = min(first[i], j), last[i] = max(last[i], j); if (last[i] == -1) base++; } } void solve(int *first, int *last, int ans[][MAX_N]) { int cur, i, j; for (i = 0; i < n - k + 1; i++) { cur = 0; for (j = 0; j < k; j++) if (last[j] != -1 && i <= first[j] && last[j] <= i + k - 1) cur++; ans[0][i] = cur; for (; j < n; j++) { if (last[j] != -1 && i <= first[j] && last[j] <= i + k - 1) cur++; if (last[j - k] != -1 && i <= first[j - k] && last[j - k] <= i + k - 1) cur--; ans[j - k + 1][i] = cur; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int i, j; cin >> n >> k; for (i = 0; i < n; i++) cin >> s[i]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) t[i] += s[j][i]; fill(row_first, row_first + MAX_N, MAX_N); fill(row_last, row_last + MAX_N, -1); fill(col_first, col_first + MAX_N, MAX_N); fill(col_last, col_last + MAX_N, -1); find_first_last(row_first, row_last, s); find_first_last(col_first, col_last, t); solve(row_first, row_last, row_ans); solve(col_first, col_last, col_ans); int ans = 0; for (i = 0; i < n - k + 1; i++) for (j = 0; j < n - k + 1; j++) ans = max(ans, row_ans[i][j] + col_ans[j][i]); cout << ans + base << '\n'; } 
 » 13 months ago, # |   0 Hi,can someone explain why we are using 2520 states for problem F in detail?I initially thought of defining a state using two variables using vertex v and value c (v,c) but c is very large leading to large number of total states. I wouldbe thankful if someone explained why we are taking 2520 states for each vertex v.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 2520 is the lowest common multiple of 1,2,...,10 — all possible numbers of outgoing edges.So (v, 2521) is essentially the same state as (v, 1) because they have the same remainder modulo 1,2,...,10
•  » » » 13 months ago, # ^ |   0 Thank you very much.
•  » » » » 12 months ago, # ^ |   0 read up on something called the chinese remainder theorum, it gives a very nice insight on problem F
 » 13 months ago, # |   0 Can someone find the reason why my code get a TLE on problem D? i think my code's complexity is O(n*n).https://codeforces.com/contest/1200/submission/58674158
•  » » 13 months ago, # ^ |   +1 it's not O(n*n)... it's O(n*n*k). in the last loops you are calling a function func which works in O(k) time.
•  » » » 13 months ago, # ^ |   0 Thank you so much:)
•  » » » » 13 months ago, # ^ |   0 yea sure
 » 13 months ago, # |   0 Hello everyone! Can someone help me please? I have WA 7 for task D. But i dont understand why.
•  » » 13 months ago, # ^ |   0 Did you find the problem?
•  » » » 13 months ago, # ^ |   0 No. I threw it up
 » 13 months ago, # |   0 can anyone explain an example on constructing string c in E. I do not get this F(k)[x-y...x]
 » 13 months ago, # | ← Rev. 2 →   +9 In problem E 2.Otherwise Construct c as $W_{k+1}[y−x...y]+F(k)$. We can get F(k+1) from the same process described in 1.here i can't understand could it be Construct c as $W_{k+1}[1...x]+F(k)$?
•  » » 13 months ago, # ^ |   0 You are right. I fixed editorial. thank you!
 » 13 months ago, # |   0 In C, why do we subtract 1 from sy and ey?
 » 13 months ago, # |   0 did somebody solved D using dp ??
 » 13 months ago, # | ← Rev. 2 →   0 great!
 » 13 months ago, # |   0 anyone please explain why my code give tle on test case 3 of problem E https://codeforces.com/contest/1200/submission/58709633
•  » » 13 months ago, # ^ |   0 i found my problem
 » 13 months ago, # |   0 For problem F, can someone explain how is the LCM term coming? (Specifically, how is the number of states for a particular vertex 2520 and the logic behind decomposition of the graph in various states). I'm not sure what the author means by state here.
•  » » 13 months ago, # ^ |   +1 https://codeforces.com/blog/entry/69035?#comment-534568 this might help.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 I still have some confusion. Suppose you visit any vertex V. Now, after adding the integer written at that vertex to c, the next vertex would be the one present at the index c%m_i. Since, c%m_i can take atmost 10 distinct values, we can infer that the state of a vertex can be defined by the vertex number and c%m_i (which is almost 10), So any vertex can have almost 10 different states (as we can determine the next vertex just by looking at c)This was my initial thought process but I'm not quite sure where I went wrong. Can you please elaborate on this.Another thing that I couldn't understand is the role of LCM. (Like, why didn't we just multiply all the numbers from 1 to 10, or maybe add them). What is the role of LCM in this case.
•  » » » » 13 months ago, # ^ |   +1 Each of them has indeed at most 10 outgoing edges, but you shouldn't consider them same only by their remainders.Suppose that there are two vertices 1 and 2. Vertex 1 has 2 outgoing edges and vertex 2 has 3 outgoing edges and both of their k values are 0. If you only consider the remainder for the states, you'll say that (1,0) is a same state as (1,2). But let's assume that e_1[0] is 2, then you see both (1,0) and (1,2) will go to vertex 2. However, (2,0) and (2,2) are different states and will use different outgoing edges. That's why you should consider (1,0) and (1,2) differently, even though 0 % 2 == 2 % 2.Now about the role of LCM: You can think of it similar to problem C. Consider that you have infinite number of rulers of same length, and put them next to each other horizontally, starting from position 0. Then do it again for another set of rulers of different length. Which position is the first position that the rulers' end meet at? It's their LCM. That means, the entire graph has a common cycle of c of length LCM(1..10). Of course, 10! also works, but this only increases the number of states to 3628800 * n so it's infeasible to consider all of the states (and this was one of the solutions that I intended to prevent from passing). 1+2+...+10 doesn't work, though.
•  » » » » » 13 months ago, # ^ |   0 Ah, yes. That clears it up. Thank you.
 » 13 months ago, # |   0 Can anyone help me debug my solution for Div-2 D. I have been trying to find the bug since a day but in vain. Any help will be highly appreciated. :) My submission
 » 13 months ago, # |   0 Is there only me who thinks that the order of D and E should be swapped?
•  » » 13 months ago, # ^ |   0 Some testers thought so, too. But the official result shows that it was a good decision to put it this way. D is just about some ideas and implementations, while E requires some pre-knowledge about some specific algorithms.
 » 13 months ago, # |   0 "Suppose the last element of the failure function smaller than the length of Wk+1 is z". Could you elaborate this ? As far as I understood this sentence implies that z < y(length of Wk+1) and L = z, so L need not be min(z, y).
 » 13 months ago, # |   0 Please help me a little here.In question F how do we came to conclusion that for each vertice there are 2520 states. p.s i am knew to competetive coding
•  » » 13 months ago, # ^ |   0 Actually, you can think there are 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 states.But as you see, if we have 8 ,we dont need 2、4 any more. If we have 9, we dont need 3 anymore. So 5 * 7 * 8 * 9 = 2520.
•  » » » 13 months ago, # ^ |   0 No I do get why LCM is taken but do not get why for each vertice there is 1*2*3*...9 states considering that these correspond to c. Like for eg. We could be visiting one vertex again and again with c being in A.P. P.s now the test is over can you give me your code I do think this is a question of Chinese remainder theorem.
 » 13 months ago, # |   0 my solution for B using binary Search . First AC 59940618
 » 12 months ago, # |   0 Why the hecking heck is there bloody runtime error on testcase 3 in problem Fhttps://codeforces.com/contest/1200/submission/60314255I'm really really lost. helpppp plsss i'm dyinngggg
•  » » 12 months ago, # ^ |   0 Nvm, i found my mistake, it was really dumb
 » 12 months ago, # | ← Rev. 2 →   0 How is the time complexity calculated in problem F? Shouldn't it depend on the number of loops in the graph?
•  » » 12 months ago, # ^ |   0 Every state is visited at most once. If you're about to re-visit a particular state, then that means you already know the answer for that state (the loop that it'll end on) — so you can just use it without re-visiting it.
•  » » » 12 months ago, # ^ |   0 But if there are many loops?
•  » » » » 12 months ago, # ^ |   +3 It doesn't matter. Each state ends in exactly one loop, and no two loops share a same state. No matter how many loops there are, you only need to check at most 2520n states.
•  » » » » » 12 months ago, # ^ |   0 Thanks!
 » 12 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1200/submission/58692995: Isn't this solution O(N*N*2520 + Q) ? How did it not TLE ? djm03178, is this the timestamp method being referred to, in the editorial ?
•  » » 12 months ago, # ^ |   0 Well it's not that kind of timestamp I mentioned. What I referred to is that you use different timestamp for different travels. This way you can look through all the vertices you visited in the loop (i.e. you can backtrack what states you have visited), and only increase the answer if the visited time is not same as this travel, and update the timestamp for that vertex.Anyways the time complexity for that submission is actually O(min(2520n, q)*n), since it requires at most one run of the loop per query. It should be fast enough since the loop barely does any work.Maybe I could make a case where that makes a lot of cache misses, but I don't know.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Thanks for the reply, it helped me a lot.
 » 3 weeks ago, # |   0 Solution for D : 91561246