chokudai's blog

AtCoder Beginner Contest 272 Announcement
By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 272.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

  • Vote: I like it
  • +53
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my favourite

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve task E?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Just keep incrementing the i-th element by (i+1) and put them into a set for each m. Need to speed up the process by only caring about the cases where the number just becomes 0 and smaller than n. My solution

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

      I'm not able to get the intuition on why it will fit in the time limit :/

      Any hints regarding the same?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Because first element is used at most n/1 times, second — n/2 times and so on. So, in total maximum sum over all answers = n * (1/1 + 1/2 + ... + 1/n) ~ n * log(n).

        → Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Actually I don't think problem F fits for its position, it would be better to swap it with G indeed.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    in F you just implement hash + bs, G is some thinking

    upd. uh, just realized that TL is 2 sec (not 4 as I though) and my $$$O(nlog^2n)$$$ runs 1.4, so mostly you are right

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I stalked your submission and your library for string hashing looks very cool: https://atcoder.jp/contests/abc272/submissions/35487307

      Binary search to get lcp, then use lcp to lexicographically compare substrings, and then sort with those comparisons to get SA. I've never seen it done this way, I might steal this template for my personal use!

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

        thanks and enjoy other codes of mine :)

        One major moment in this solution is stable_sort. It has less calls to comparator than usual sort (that gives TLE)

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

      Can you please explain your solution?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Sort all cyclic shifts for both given strings. Then find for each shift number of greater or equal by two pointers

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried using BFS in Problem D, but I am not able to pass the 3 tests. Can someone help me find the issue? https://atcoder.jp/contests/abc272/submissions/35485981

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is always the f**king sqrt!

    Corrected version: https://atcoder.jp/contests/abc272/submissions/35512682

    Please note that both sqrt/sqrtl return float. You cannot compare float with int using ==.

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

      Sqrt messed up my yesterday coderforces also :( Now I use sqrtl everywhere. Now I will append (ll) in front of it every time.

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

        BINARY SEARCH PLEASE!

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

        sqrtl is not perfect either. Use binary search.

        Code
        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lmao I did the same exact thing, but I was only doing virtual.

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

    Just avoid the sqrt by squaring on both sides of the equation.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

On problem D, I think it will be possible to solve the problem in $$$O(N^2+\sqrt{M})$$$ by precalculating the possible movements. (I did it in $$$O(N^2+(\sqrt{M})^2)=O(N^2+M)$$$ through a brute-force precalculation.) Did anyone solve D with this method also?

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

    I also first enumerated the possible moves, but I did so by enumerating all $$$(i, j)$$$ s.t. $$$i, j \in [-N, N]$$$, which takes $$$O(N^2)$$$ to enumerate them.

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I used the SA-IS algorithm in problem F but failed. I thought my idea was genius but the jury thought I was an idiot. Would you please review it?

Submission(272F)

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Before reviewing it, I first pressed the upvoting button.

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

      Yes, there are counterexamples.

      Let $$$T=\texttt{"dcbaf"},\,S = \texttt{"afdcb"}$$$.

      Here is my code:

      string s1 = s, t1 = t;
s1.pop_back();
t1.pop_back();
string large = t + t1 + s + s1;

      In my concatenation, the large is $$$\texttt{"dcbafdcbaafdcbafdc"}$$$. The first $$$\texttt{"fdcba"}$$$ starts from No.4 (0-indexed) whose suffix is $$$x=\texttt{"fdcbaafdcbafdc"}$$$, the second $$$\texttt{"fdcba"}$$$ starts from No.10 whose suffix is $$$y=\texttt{"fdcbafdc"}$$$. $$$x < y, j=4, i=1$$$. My algorithm would not count this pair but this pair is definitely valid.

      For the correct answer, please refer to the tutorial/editorial.

      This is the link to the original problem (ABC272F Two Strings).

      Welcome to my blog about ABC272F: https://mirror.codeforces.com/blog/entry/107776.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem E is very nice for "learning how to analyze complexity". In fact during contest, I could not convince myself that the complexity is O(NlogN) rather than O(NM), but after reading the editorial, I really like the idea of "important values".

Besides, problem F is somehow about suffix array, which is really really a difficult topic for me, not even to talk about that clever construction in editorial. It seems that I should find time to learn suffix array again.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how hashing solution works for F?

I am not able to think how to compare strings lexicographically using it

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain for problem $$$G$$$ why we need to check only $$$log_{3/4}(1-L)$$$ times randomly according to the editorial?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Let $$$ P(success) = L $$$

    $$$ P(failure) = 1-L $$$

    $$$ P(failureInOneRound) = 1-\frac{1}{4} = \frac{3}{4}$$$

    We fail only if we fail on all steps. Let the number of steps be x, then

    $$$ P(failure) = P(failureInOneRound)^x = (\frac{3}{4})^x$$$

    On equating P(failure) you'll get the desired value of $$$ x = \log_\frac{3}{4}(1-L) $$$

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

      Its probably a dumb question but how is $$$P(success) = 1/4$$$. I mean they said it in the editorial but how did they arrive at this conclusion?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        S = Subset of array which will be in answer. |S| $$$ \geq \lfloor \frac{n}{2} \rfloor + 1 $$$. For getting correct answer we want that both values which are chosen must belong to S. Its probability, p = $$$ \frac{|S|*(|S|-1)}{n*(n-1)} $$$.

        $$$ |S|*(|S|-1) \geq (\lfloor \frac{n}{2} \rfloor+1)*(\lfloor \frac{n}{2} \rfloor) \geq (\frac{n}{2})^2-(0.5)^2$$$ (-0.5 term will come when n is odd) $$$ \geq \frac{n^2-1}{4} \geq \frac{n^2-n}{4}$$$

        Substituting in p, we get p $$$ \geq \frac{1}{4} $$$

        → Reply