djm03178's blog

By djm03178, history, 5 years ago,

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

• +157

| Write comment?
 » 5 years ago, # |   -38 Fast Editorial. :)
 » 5 years 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.
•  » » 5 years ago, # ^ |   0 reading input takes O(n**2)
•  » » » 5 years ago, # ^ |   0 Yes, and O(n^3) is too slow
•  » » » » 4 years 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.
•  » » » » » 4 years 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
•  » » » » » 4 years ago, # ^ |   +1 It's not a mistake in the editorial. The main solution is $O(n^2)$.
•  » » 5 years 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.
 » 5 years ago, # | ← Rev. 2 →   -6 can E be solved by Hashing?
 » 5 years ago, # | ← Rev. 2 →   +12 What is the test case 35 of C? Edit: works by replacing ceil with (x + n — 1) / n
•  » » 5 years ago, # ^ |   0 same too
•  » » 5 years ago, # ^ |   0 Same here. I feel so sad bruh =))
•  » » » 5 years ago, # ^ |   0 I forget to use long long for one of my variables.
•  » » 5 years 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; } 
•  » » » 5 years ago, # ^ |   +5 Better use (a — 1) / b + 1
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +13 You can use (a + b — 1) / b.
•  » » » 3 years ago, # ^ |   0 or a/b+(a%b>0)
•  » » 5 years 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.
•  » » 5 years ago, # ^ |   0 500000000000000000 1000000000000000000 1 2 716004419141796031 1 358002209570898016 Built-in ceil function failed on this query
•  » » 5 years ago, # ^ |   0 consider use long long and long double for all varibles
•  » » 5 years 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.
 » 5 years ago, # | ← Rev. 2 →   -16 deleted
•  » » 5 years ago, # ^ |   +5 sometimes , bruteforce is the best solution, just keep in mind the time complexity for the worst case :)
 » 5 years ago, # |   0 I got FST on test 15 on C, can someone please check what's wrong? $\to$ 58603533
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I'm wrong.
•  » » » 5 years ago, # ^ |   0 It should have an overloaded function for long long, and I've added the (famous) #define int long long before everything...
•  » » 5 years 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!!
•  » » » 5 years ago, # ^ |   0 I used long double!
•  » » » » 5 years ago, # ^ |   0 Still it will give precision errors!!! check on local compiler!!
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 I thought long double should be precise enough... RIP rating.
 » 5 years ago, # |   +15 It was honor to participate in.Thanks.수고하셨습니다.양질의 문제들을 제공해주셔서 감사했습니다 :)
 » 5 years ago, # |   +5 Could somebody explain this code? https://codeforces.com/contest/1200/submission/58594933
•  » » 5 years 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$).  » 5 years ago, # | 0 Hey! I got WA on test 26, can anyone point out error in my code? :) Here's my Submission •  » » 5 years ago, # ^ | 0 area1 = ((a==1) ? n*(b-1) : m*(b-1)); area2 = ((c==1) ? n*(d-1) : m*(d-1)); It will overflow here. •  » » » 5 years ago, # ^ | +1 Hey! Thanks for your response. I already figured it out. :)  » 5 years 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 •  » » 5 years ago, # ^ | 0 same problem here https://codeforces.com/contest/1200/submission/58606476 •  » » 5 years ago, # ^ | 0 just use long double instead of double. the WA verdict was because of precision error due to division of large values •  » » » 5 years ago, # ^ | 0 Missing out due to overflow and precision issues is the worst feeling in coding ...  » 5 years ago, # | +1 What is the testcase 35 of C? Can someone spot an error in my code? http://codeforces.com/contest/1200/submission/58603084 •  » » 5 years ago, # ^ | 0 same happening with me...58621017..Anyone please explain..?? •  » » » 5 years 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. •  » » 5 years 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 •  » » » 5 years ago, # ^ | +1 Thanks •  » » 5 years ago, # ^ | +1 You should avoid to use real number when integer can solve  » 5 years ago, # | 0 Round was very good. but.. I was terrible. I couldn't solve E and F.  » 5 years ago, # | +12 It's easy to pass E by Hash •  » » 5 years ago, # ^ | 0 But it seems your solution can be hacked since your hashing is not randomized •  » » » 5 years ago, # ^ | 0 Double hash can hardly be hacked •  » » » » 5 years ago, # ^ | +3 I got accepted with quintuple hash 59377951 :)  » 5 years 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 •  » » 5 years 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 •  » » » 5 years 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 :)  » 5 years 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 •  » » 5 years 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.  » 5 years ago, # | +3 I didn't understand the case that the wall at 12 o'clock always exists.What if n==1 or m==1?  » 5 years 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. •  » » 5 years 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. •  » » » 5 years 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? •  » » » » 5 years 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. •  » » » » 5 years ago, # ^ | +1 Maximal link depth equals to number of suffixes = string's length, so on reversed test of Junco_dh 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.  » 5 years 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! •  » » 5 years 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. •  » » » 5 years 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:( •  » » » » 5 years 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 •  » » » » » 5 years 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! :) •  » » 5 years 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 •  » » » 5 years ago, # ^ | +1 Thanks a lot. This helped! :)  » 5 years ago, # | +10 In C , how to prove that g = gcd(n , m) is the no. of dual walls. •  » » 5 years 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
•  » » » 5 years ago, # ^ |   0 Nice!
 » 5 years 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?
 » 5 years 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)
•  » » 5 years 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
•  » » 5 years ago, # ^ |   0 can u please explain how u have solved D que??
•  » » » 5 years 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
•  » » » » 5 years ago, # ^ |   +6 thanks for an excellent explanation and your time! Really helped a lot.
 » 5 years 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?
•  » » 5 years 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
•  » » 5 years 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]$).
•  » » » 5 years ago, # ^ |   +6 Ohh... Thank you guys! Happy coding.
 » 5 years 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.
•  » » 5 years 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.
•  » » » 5 years 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!
 » 5 years 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.
 » 5 years ago, # |   0 Can someone please explain how to solve D with KMP? Thanks!
•  » » 5 years 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.
 » 5 years ago, # |   0 E can also be done with hash
 » 5 years ago, # |   0 Problem F's idea is similar to this problem https://codeforces.com/problemset/problem/1137/C
 » 5 years ago, # |   0 Can Someone please check why my code is giving WA on test case 9 in problem div2-D? 58651885
 » 5 years 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.
•  » » 5 years 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
 » 5 years ago, # |   0 SUBMISSION what is wrong with this solution for B?
 » 5 years ago, # |   0 Can some please tell me why i am getting WA in test case 5 for problem E https://ide.geeksforgeeks.org/zDbvJinjIP
 » 5 years 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??
•  » » 5 years ago, # ^ |   0 They are both YES. What made you think the answer is NO?
 » 5 years 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.
•  » » 5 years 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
•  » » » 5 years ago, # ^ |   +5 Thanks! :)
 » 5 years ago, # |   0 Can anyone please pin down code solution for Div2D following the editorial explanation?
•  » » 5 years 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'; } 
 » 5 years 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.
•  » » 5 years 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
 » 5 years 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
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 Thank you so much:)
•  » » » » 5 years ago, # ^ |   0 yea sure
 » 5 years ago, # |   0 Hello everyone! Can someone help me please? I have WA 7 for task D. But i dont understand why.
•  » » 5 years ago, # ^ |   0 Did you find the problem?
•  » » » 5 years ago, # ^ |   0 No. I threw it up
 » 5 years 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)$?
•  » » 5 years ago, # ^ |   0 You are right. I fixed editorial. thank you!
 » 5 years ago, # |   0 anyone please explain why my code give tle on test case 3 of problem E https://codeforces.com/contest/1200/submission/58709633
•  » » 5 years ago, # ^ |   0 i found my problem
 » 5 years 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.
•  » » 5 years ago, # ^ |   +1 https://codeforces.com/blog/entry/69035?#comment-534568 this might help.
•  » » » 5 years 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.
•  » » » » 5 years 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.
 » 5 years 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
 » 5 years ago, # |   0 Is there only me who thinks that the order of D and E should be swapped?
•  » » 5 years 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.
 » 5 years 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).
 » 4 years 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?
•  » » 4 years 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.
•  » » » 4 years ago, # ^ |   0 But if there are many loops?
•  » » » » 4 years 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.
•  » » » » » 4 years ago, # ^ |   0 Thanks!
 » 4 years 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 ?
•  » » 4 years 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks for the reply, it helped me a lot.
 » 3 years ago, # |   0 Solution for D : 91561246