When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

djm03178's blog

By djm03178, history, 5 years ago, In English

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

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +157
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Fast Editorial. :)

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    reading input takes O(n**2)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
            Vote: I like it +1 Vote: I do not like it

          It's not a mistake in the editorial. The main solution is $$$O(n^2)$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it -6 Vote: I do not like it

can E be solved by Hashing?

»
5 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

What is the test case 35 of C?

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same too

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here. I feel so sad bruh =))

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    consider use long long and long double for all varibles

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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   Vote: I like it -16 Vote: I do not like it

deleted

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'm wrong.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It was honor to participate in.
Thanks.

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why my code fail in test case 35

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

I'm using ceil function to get each group

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

It's easy to pass E by Hash

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it
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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # |
  Vote: I like it +8 Vote: I do not like 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!

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it +29 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +22 Vote: I do not like it

          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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like 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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Ohh... Thank you guys! Happy coding.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

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

58609028

Can anyone help me?

Thanks.

UPD: I found the mistake.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how to solve D with KMP? Thanks!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E can also be done with hash

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

SUBMISSION what is wrong with this solution for B?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's one of the correct solutions.

    code
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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;

»
5 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right. I fixed editorial. thank you!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if there are many loops?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Solution for D : 91561246