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

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | antontrygubO_o | 166 |

5 | Vovuh | 165 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

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

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #578 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 08:08:56 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Fast Editorial. :)

i have no idea why people downvoted this comment

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.

reading input takes O(n**2)

Yes, and O(n^3) is too slow

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.

so fast Editorial!

can E be solved by Hashing?

What is the test case 35 of C?

Edit: works by replacing ceil with (x + n — 1) / n

same too

Same here. I feel so sad bruh =))

I forget to use long long for one of my variables.

same, feels bad man

ceil is prone to error. Better write your own, like you said, or maybe implement something along these lines:

Better use (a — 1) / b + 1

You can use (a + b — 1) / b.

n=5*10^17, m=10^18. Gcd will be 5*10^17 and it's umportant to keep gcd in long long.

500000000000000000 1000000000000000000 1 2 716004419141796031 1 358002209570898016 Built-in ceil function failed on this query

consider use long long and long double for all varibles

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.

I make A very complicated by trying to use priority queue and I didn't solve it.... but the solution actually is very easy .... it's always good to simplify things

sometimes , bruteforce is the best solution, just keep in mind the time complexity for the worst case :)

I got FST on test 15 on C, can someone please check what's wrong? $$$\to$$$ 58603533

I'm wrong.

It should have an overloaded function for long long, and I've added the (famous)

`#define int long long`

before everything...You will most probably encounter precision errors as you have use double data type, because the values are as high as 1e18!!

I used long double!

Still it will give precision errors!!! check on local compiler!!

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.

I thought long double should be precise enough... RIP rating.

It was honor to participate in.

Thanks.

수고하셨습니다.

양질의 문제들을 제공해주셔서 감사했습니다 :)

Could somebody explain this code? https://codeforces.com/contest/1200/submission/58594933

For prefix function one usually uses a string formed by:

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

Hey! I got WA on test 26, can anyone point out error in my code? :) Here's my Submission

It will overflow here.

Hey! Thanks for your response. I already figured it out. :)

why my code fail in test case 35

https://codeforces.com/contest/1200/submission/58607383

I'm using ceil function to get each group

same problem here https://codeforces.com/contest/1200/submission/58606476

just use long double instead of double. the WA verdict was because of precision error due to division of large values

Missing out due to overflow and precision issues is the worst feeling in coding ...

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.

What is the testcase 35 of C? Can someone spot an error in my code? http://codeforces.com/contest/1200/submission/58603084

same happening with me...58621017..Anyone please explain..??

Replaced ceil with (sx + n — 1) / n and it worked. (https://codeforces.com/contest/1200/submission/58622681)

Ceil in C++ is error it seems.

Seems, like in python double comparison is f**ked up.

Since this passes by converting to int.

https://codeforces.com/contest/1200/submission/58622224

Thanks

You should avoid to use real number when integer can solve

Round was very good. but.. I was terrible. I couldn't solve E and F.

It's easy to pass E by Hash

But it seems your solution can be hacked since your hashing is not randomized

Double hash can hardly be hacked

I got accepted with quintuple hash 59377951 :)

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

Okay three main issues:

`m == 0`

should be changed to m < 0`>`

in else should be changed to`>=`

`k`

amount in else even after making them equal.Here is your modified code that passes:

https://codeforces.com/contest/1200/submission/58624658

Wow man, thanks!

i was able to figure out 1st and 2nd one but can't see that we can still decrease it. Tysm :)

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

Some points why this doesnt work:

I didn't understand the case that the wall at 12 o'clock always exists.What if n==1 or m==1?

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.

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/58614095

The 998ms is quite close to the time limit, but honestly I expected this will simply TL.

This part of your code works in linear time of current string's length, because you mark all suffixes of string:

Total complexity is $$$O(W^2)$$$, where $$$W$$$ is sum of strings length. So, tests are weak.

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?

Maybe something like this?

(99999 single a's and then 1 word of as a's as possible)

Because the for loop for 1e5 times and the while loop for t times since all states are terminal states.

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.

Hi — can someone let me know why my E solution is timing out? — https://codeforces.com/contest/1200/submission/58623121

I 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!

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

:(

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

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 :D

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

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! :)

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`

Thanks a lot. This helped! :)

In C , how to prove that g = gcd(n , m) is the no. of dual walls.

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

and simplify to

The restrictions $0\le x<n,\ 0\le y<m$ require that $$$0\le k<\gcd(m,n)$$$. The dual walls correspond exactly with each integer $$$k$$$ in this range, therefore the number of dual walls is $$$\gcd(m,n).$$$

Nice!

My code of Div2-B, in my PC is given the correct answer to case:

1

10 50 160

319 47 107 192 866 475 139 594 636 345

answer:NO

But in codeforces is given YES Code:58603788

Anyone can help me?

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)

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

can u please explain how u have solved D que??

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: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:

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:

You can handle with vertical bad lines in a similar way :D

Finally, 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

thanks for an excellent explanation and your time! Really helped a lot.

Can anyone explain why these submissions : 58626941, 58626900 did not pass the tests but this one did — 58627018 ? Are small primes that useless?

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

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

Ohh... Thank you guys! Happy coding.

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.

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

My solution of E using double hashing failed on test #65.

58609028

Can anyone help me?

Thanks.

UPD: I found the mistake.Can someone please explain how to solve D with KMP? Thanks!

Isn't E？

I solved E by KMP following the editorial. https://codeforces.com/contest/1200/submission/58665108

I think the key point is to reset the longest border value in the center of c which is defined by editorial.

I think i could solve E by double hash ,but time didnt wait me:(

E can also be done with hash

Problem F's idea is similar to this problem https://codeforces.com/problemset/problem/1137/C

Can Someone please check why my code is giving WA on test case 9 in problem div2-D? 58651885

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.

Try this test: "3 abc def cdef". Answer should be abcdef, but your program outputs abcdefcdef. Did you found your misunderstanding? :v

SUBMISSION what is wrong with this solution for B?

I use a silly way to solve C,but to my surprise it could get right

Can some please tell me why i am getting WA in test case 5 for problem E https://ide.geeksforgeeks.org/zDbvJinjIP

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??

They are both YES. What made you think the answer is NO?

sorry my answer is NO but the right ans is YES . i made a small mistake in my code .

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.

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

Thanks! :)

Can anyone please pin down code solution for Div2D following the editorial explanation?

Here's one of the correct solutions.

codeHi,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.

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

Thank you very much.

read up on something called the chinese remainder theorum, it gives a very nice insight on problem F

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

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.

Thank you so much:)

yea sure

Hello everyone! Can someone help me please? I have WA 7 for task D. But i dont understand why.

Submission: https://codeforces.com/contest/1200/submission/58679744;

Did you find the problem?

No. I threw it up

can anyone explain an example on constructing string c in E. I do not get this F(k)[x-y...x]

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

You are right. I fixed editorial. thank you!

In C, why do we subtract 1 from sy and ey?

did somebody solved D using dp ??

great!

anyone please explain why my code give tle on test case 3 of problem E https://codeforces.com/contest/1200/submission/58709633

i found my problem

For problem

F, can someone explain how is theLCMterm 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

statehere.https://codeforces.com/blog/entry/69035?#comment-534568 this might help.

I still have some confusion. Suppose you visit any vertex

V. Now, after adding the integer written at that vertex toc, the next vertex would be the one present at the indexc%m_i. Since,c%m_ican take atmost 10 distinct values, we can infer that the state of a vertex can be defined by the vertex number andc%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.

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

1and2. Vertex1has 2 outgoing edges and vertex2has 3 outgoing edges and both of theirkvalues 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 thate_1[0]is 2, then you see both (1,0) and (1,2) will go to vertex2. 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

cof length LCM(1..10). Of course, 10! also works, but this only increases the number of states to 3628800 *nso 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.Ah, yes. That clears it up. Thank you.

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

Is there only me who thinks that the order of D and E should be swapped?

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.

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

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

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.

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.

my solution for B using binary Search . First AC 59940618

Why the hecking heck is there bloody runtime error on testcase 3 in problem F

https://codeforces.com/contest/1200/submission/60314255

I'm really really lost. helpppp plsss i'm dyinngggg

Nvm, i found my mistake, it was really dumb

How is the time complexity calculated in problem F? Shouldn't it depend on the number of loops in the graph?

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.

But if there are many loops?

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.

Thanks!

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 ?

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.

Thanks for the reply, it helped me a lot.