awoo's blog

By awoo, history, 5 years ago, translation, In English

1202A - You Are Given Two Binary Strings...

Idea: adedalic

Tutorial
Solution (adedalic)

1202B - You Are Given a Decimal String...

Idea: adedalic

Tutorial
Solution (adedalic)

1202C - You Are Given a WASD-string...

Idea: adedalic

Tutorial
Solution (adedalic)

1202D - Print a 1337-string...

Idea: Roms

Tutorial
Solution (Roms)

1202E - You Are Given Some Strings...

Idea: Roms

Tutorial
Solution (adedalic)

1202F - You Are Given Some Letters...

Idea: adedalic

Tutorial
Solution (PikMike)
  • Vote: I like it
  • +187
  • Vote: I do not like it

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

U good bro?

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

In C:

Why do we have to check lastMax and firstMin? Can't we always decrease 1 by inserting any character if the width is more than 2. (same for height)

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

it's impressive how hard were the problems during the contest, but what simple and elegant solution they have.

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

    hard to find out right idea, but when you have one, it seems easy to write down the code, I think. So these problems are still quite hard for a div.2 contest, my thought also.

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

    Except problem C

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

How do we use a suffix array for problem E?

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

    Build a suffix array for $$$t$$$. For each string $$$s$$$ the suffixes of $$$t$$$ that have $$$s$$$ as a prefix form a (possibly empty) contiguous subsegment of the suffixes in SA order. So you can binary search for the first and last positions in SA order where $$$s$$$ occurs. Comparing can be done in $$$O(\vert s \vert)$$$ so you get the range in $$$O(\vert s \vert \log \vert t \vert)$$$.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it -7 Vote: I do not like it

      Hello, I am new to suffix arrays can you please explain in more detail?

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

Problem E.

By building suffix automaton of $$$t$$$ and its reverse, you can simply solve the problem in linear time (suppose that $$$|\Sigma|=26$$$ is a constant). Just run each $$$s_i$$$ (or its reverse) on the suffix automaton and mark the end state, then it exists at all end positions in its subtree. Count the number of strings that exists at each position and then you could get the answer.

Aho-Corasick automaton can do the things as well.

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

    Can you please elaborate more. What do you mean by "then it exists at all end positions in its subtree"

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

      A state which refers to a prefix of the string would create a new end position (equals to its length $$$l$$$), so the number of occurrence at position $$$l$$$ equals to the number of occurrences of its suffixes, which lies on its the path to the root.

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

    I'm a bit confused as to how Aho-Corasick works for this problem. Would you mind explaining that part as well?

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

      Just run $$$t$$$ on the automaton of $$$s_i$$$, for each prefix of $$$t$$$, if you go from the current state through fail transitions, then all the string on the path occurs. This however doesn't works well, but what you need is just precalculating the number of strings on the path of each state.

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

Can you use exgcd in B?

I used exgcd to solve

$$$ax+by\equiv n - m(\mod 10)$$$

,

where a and b is the x-y in the x-y generator. But I couldn't get it right...

And also, DFS Brute force can even pass? --> 58442948

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

    The equation $$$c$$$ % $$$g$$$$$$c$$$$$$d$$$ $$$(a$$$ $$$,$$$ $$$b)==0$$$ may not be tenable in some cases when you're solving $$$ ax+by=c $$$.

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

      It is actually implemented as $$$ax+by = 10k+(n-m)$$$ for some $$$k$$$.

      If no solution was found, the answer shall be $$$-1$$$.

      The complexity should be $$$O(nA\log A)$$$, where $$$A = 10$$$

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

        Sorry...I didn't read your comment carefully...

        The total complexity of your solution could be $$$ O(A^3logA+A^2|s|) $$$ .

        I don't know whether it is right ...

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

    This dfs algorithm will pass,because it controls the deep no more than ten,and each will have two choice so no more than 2^10=1000,and total 10^6,never TLE

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

    in fact bfs can run faster

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

      This problem taught me that:

      When you think of a brute-force solution, write it down, maybe it can pass...

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

        I used the following python code to evaluate their efficiency. And I found that, as $$$A$$$ increases, my solution becomes faster than the problem setters'...

        Here is the code I used $$$\to$$$ Link to Code

        Here is the result I got $$$\to$$$ Link to Result

        Did I get it wrong? Please point it out :D

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

        In fact,Whether will get TLE depends on the FOR you have.

        for example

        rep(i,n)
           rep(j,n)
              {
        ...
        }
        

        is O(n^2)

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

          I cannot get your point. Can you please explain further?

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

            we call an algorithm is O(n^2) if there is one FOR in a FOR

            O(n^3) if a for in a for and all in a for

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

    There are several questions while you are solving the problem using exgcd.

    1. The formula is $$$ax + by \equiv n - m \mod 10$$$. So actually it is $$$ax + by - 10k = n - m$$$. It means there are 3 variables in the equation: $$$x$$$, $$$y$$$, $$$k$$$. If you really want to use exgcd, you should enumerate one of the variables and solve the other two ones.

    2. For example, you enumerate x, and use exgcd to solve the equation, the solutions to $$$y$$$ and $$$k$$$ maybe are not the minimum $$$x + y$$$ since this problem you need to find the minimum number of digits. And that means, you need to iterate through all possible solutions to the equation. ($$$+ \frac {n - m - ax} {gcd (b, 10)}$$$ if you enumerate x)

    3. In this problem, when $$$n - m = 0$$$, you have to find a solution in which $$$k \ge 1$$$ (this k defined same as above). And that's a little bit difficult.

    I tried to solve this problem using exgcd during the contest and I failed too. So at last I used brute force to solve the equation. (During the contest, I had a stupid mistake: Didn't consider about $$$n - m = 0$$$). This is my code: 58471355.

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

Why my submission for E gets TLE? It should be N sqrt N. Hashing seems like it would be fast too. Is it finally time for me to read that old stanford suffix arrays pdf again? Please help, thanks.

https://codeforces.net/contest/1202/submission/58480361

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

    Maybe hash table failed you this time

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

      qwq, how to make it fast? Or just give up and study some real data structures?

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

        You can try to make different contribution maps for each length — this maps can't be large at the same time.

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

          Thanks! Unfortunately even after trying this + only using one hash instead of two + using a faster hash for the strings that are not t, it still gives TLE. I think it's just not possible to solve the problem with hashing. If anyone has solved it with hashing, I would be very interested in seeing it.

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

            https://codeforces.net/contest/1202/submission/58518083

            Was able to get AC using hashing. Used different maps for different lengths. 2854 ms is not good though...

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

            Here's a sqrt hashing solution that fits in under 60% of the time limit: 68428902

            The main improvements over your version are to iterate over every distinct length that occurs in $$$S$$$ and find matches of that length within $$$T$$$. When you get a match, you can add the appropriate count to both the start and the end of the substring.

            This makes the hashing much more cache-friendly and avoids having to hash each substring twice (your solution hashes each once at the start and once at the end). It also removes the need for the hash table entirely.

            Considering that this is still over half the time limit, I think it's fair to say that the time limit on this problem was quite strict for sqrt solutions.

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

Solved D in a weird kind of way.

Let the String be $$$(1^A3^B7) (1^C3^D7)$$$ where $$$d^P$$$ represents digit $$$d$$$ occurring $$$P$$$ times. Bracket is given for clarity.

Number of subsequence 1337 in this string is:

$$$S = A*{B \choose 2}+C*{D \choose 2}+A*{(B+D) \choose 2}$$$

So, what we need to do is find such $$$A$$$,$$$B$$$, $$$C$$$ and $$$D$$$ such that $$$S$$$ becomes $$$n$$$ and also $$$A+B+C+D+2<=10^5$$$

So, I wrote 3 nested for loops over $$$A$$$,$$$B$$$ and $$$D$$$ to find $$$C$$$. And it turns out it always finds some sets of values (and does it very quickly which I don't know why)

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

    Can somebody write a proof as to why does this work everytime?

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

      First of all, I'll try to proof that there is always a solution with the given structure.

      Make $$$D = 2$$$ just to make our life easier (since it will isolate $$$C$$$ and we will be able to factorize $$$A$$$). Our expression will be:

      $$$ A \cdot \frac{B(B-1)}{2} + C + A \cdot \frac{(B+2)(B+1)}{2} = n $$$

      Since $$$C$$$ can take any value that we would need, we can send it to the right part of the equation:

      $$$ A \cdot \left(\frac{B^{2} - B}{2} + \frac{B^{2} + 3B + 2}{2}\right) = n - C $$$

      Operating:

      $$$ A \cdot \left(\frac{2B^{2} + 2B + 2}{2}\right) = n - C $$$
      $$$ A \cdot \left(B^{2} + B + 1\right) = n - C $$$

      Now we ask, how does this help since $$$n$$$ could be a prime? The answer is that $$$C$$$ helps us to adjust the divisibility of $$$n$$$ to make it divisible by some integer $$$x \leq \sqrt{n}$$$ (Remember that among $$$p$$$ consecutive integers there is a multiple of $$$p$$$). So if we make $$$B^{2} + B + 1$$$ the maximum integer such that is $$$\leq \sqrt{n}$$$ (thus $$$\leq \sqrt{10^{9}} \approx 31622$$$) and $$$C$$$ the one we need to make $$$n-C$$$ divisible by $$$B^{2} + B + 1$$$ (thus $$$C \leq B^{2} + B + 1 \leq 31622$$$) then $$$A$$$ will have an integer solution.

      The length of the string would be:

      $$$ B \leq 177, C \leq 31622, A \leq 31622, D = 2 \rightarrow A + B + C + D + 2 \leq 63425 $$$

      Which is a valid answer. The reason why you find such an early answer might be this one, $$$A$$$ iterates at most 31622, $$$B$$$ iterates at most 177 and $$$D$$$ at most 2.

      I'm not sure if this is the latest answer you could get (since there might be an earlier answer), but it helps I guess :P

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

In problem C we can also use data structures to maintain the minimum/maximum value.

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

Can somebody pls explain how floyd warshall algorithm is used to solve B ?

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

    Look at my submission 58631999. For every x-y-counter we need to calculate the shortest path between any pair of digits.

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

I have some questions about problem F.

Problem is tagged with binary search. What application in possible solution it can have? I can only think of binary searching for borders of each periods segment resulting in $$$O(\sqrt{n} \cdot log(n))$$$ solution. Are there any alternative ideas with binary search?

It seems that solutions for problem F operate each letter independently (making the same actions on each and then combining the resulting limitations). It can be proven that we can always construct a string with given minimal period if we have at least two different letters in it (and this is always the case for the problem) as long as the limitations for each letter are fulfilled. So, is there any specific reason to restrict the size of alphabet to $$$2$$$?

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

    My solution, when I proposed the problem was, indeed, to binary search borders for the fixed $$$\frac{n}{k}$$$. But my proof that the suitable periods forms a segment is heavily based of the fact that there are only two letters.

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

      Intuitively, it feels that having a larger alphabet cannot make things worse in such constructive problems (constructing a string with given content and period).

      We have a proof that we can always construct a string $$$S$$$ of form $$$(X+Y) \cdot q + X$$$ (in other words period repeated $$$q$$$ times with some prefix of period at the end) which will have minimal period $$$(X+Y)$$$ where $$$X$$$ contains $$$cnt_{(X,a)}$$$ letters $$$a$$$ and $$$cnt_{(X,b)}$$$ letters $$$b$$$ and the same for $$$Y$$$. Violating limitation inequality for letter $$$a$$$ will result in making either $$$cnt_{(X,a)}$$$ or $$$cnt_{(Y,a)}$$$ negative, so it is always possible as long as these coefficient are non-negative and $$$(X+Y)$$$ contains both letters at least once.

      Now, consider alphabet $$$\alpha$$$ with $$$|\alpha| > 2$$$ and coefficients $$$cnt_{(X,e)}, cnt_{(Y,e)} \geq 0$$$ for each $$$e \in \alpha$$$. We can just move to alphabet $$$\{a, b\}$$$ by dividing $$$\alpha$$$ into two non-empty sets and mapping first set of letters to $$$a$$$ and second set to $$$b$$$. Get $$$cnt$$$-s for $$$a$$$ and $$$b$$$ by summarizing $$$cnt$$$-s of mapped letters, they will also be non-negative (as a sum of non-negative values). Find some $$$X$$$ and $$$Y$$$ in alphabet $$$\{a, b\}$$$. Then we can move back to $$$\alpha$$$ replacing any $$$cnt_{(X,e)}$$$ letters $$$a$$$ in $$$X$$$ to letter $$$e$$$ for each $$$e$$$ that was mapped to $$$a$$$ (and doing the same for letter $$$b$$$ and for string $$$Y$$$). This wont break the period in $$$S$$$, because the letters from $$$\alpha$$$ that were mapped to different letters will for sure be non-equal after moving back. Some of letters that were mapped to the same letter may become non-equal, but this will not break anything because each $$$S_i$$$ and $$$S_j$$$ that must be equal to match periods both will be equal to either some $$$X_k$$$ or $$$Y_k$$$, and character is always equal to itself.

      I'm sure we can find a general proof without reduction to smaller alphabet, but I failed to find it in more or less elegant form without considering dozens of cases.

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

        Intuitively, increasing alphabet makes things more complicated. About mapping: consider the case: $$$2$$$ letters $$$X$$$, $$$1$$$ letter $$$Y$$$ and $$$1$$$ letter $$$Z$$$. Mapping $$$(X) \to A$$$ and $$$(Y, Z) \to B$$$ allows period $$$k = 2$$$ ($$$ABAB$$$), but there is no way to make $$$k = 2$$$ with $$$X$$$, $$$Y$$$, $$$Z$$$.

        From the other side, we know that $$$s_i = s_{i \mod k}$$$ so we can split $$$s$$$ in $$$k$$$ chains of equal characters: $$$n \mod k$$$ chains of length $$$\frac{n}{k} + 1$$$ and $$$k - n \mod k$$$ of length $$$\frac{n}{k}$$$. In case of two characters we need to represent only one of integers ($$$a$$$ or $$$b$$$) as $$$cnt_0 \cdot \frac{n}{k} + cnt_1 \cdot (\frac{n}{k} + 1)$$$. But in case of $$$m$$$ characters we must represent $$$m - 1$$$ integers simultaneously and it's much harder.

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

          Clearly, such mapping will not work if we apply it to whole string $$$S$$$ before eshablishing it's structure. But we can firstly say that it consists of $$$(q+1)$$$ strings $$$X$$$ and $$$q$$$ strings $$$Y$$$. And of course we have to check letter limitations for original letters: we have to make sure $$$X$$$ and $$$Y$$$ contain non-negative amount of each letter. In case of $$$cnt = [2, 1, 1]$$$ letters with $$$cnt_i = 1$$$ will not allow distributing letters into two complete periods.

          About the second part, from that point of view that definitely seems to be more complicated than for alphabet of size $$$2$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it
    void solve(int l, int r) {
      if (n / l == n / r) { /* solve stuff here */ }
      else { int mid = (l + r) / 2; solve(l, mid); solve(mid+1, r); }
    }
    

    This is an easier way to code problems like this sometimes.

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

      Wow, that's really nice and elegant way to use D&C here. Resulting in $$$O(log(N) \cdot C)$$$, where $$$C$$$ is number of segments.

      Thanks for sharing this!

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

        I think it's just $$$O(C)$$$ — similar to building a segment tree.

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

          Yes, similarily to building segment tree amount of splitting nodes will be equal to amount of leaf nodes. And if each segment will be of size $$$1$$$ and we will have $$$N$$$ segments, we will have $$$O(C) = O(N)$$$. But similarily to querying segment tree on a range we split original range into $$$O(log(R))$$$ ranges (where $$$R$$$ is the size of range) that fit into some vertexes of a tree. In our case we will not continue building deeper than such ranges, so we will have $$$O(log(N) \cdot C)$$$ leaf nodes in that tree and /* solve stuff here */ will be visited this amount of times.

          That seems to be the analysis for arbitrary set of segments. Probably, there is a specific analysis for that case that gives better complexity.

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

            Yes now I see it is not a clear $$$O(C)$$$, but I added a counter to the function, and the number of states visited is close to $$$4C$$$: http://ideone.com/kloEB0

            I'll try to explain what I think is special about these segments: consider the $$$2C$$$ endpoints of the segments, if we build a dynamic segment tree over the range $$$[1, n]$$$ with these points, then the number of nodes won't be less than the number of nodes in our case (because reaching $$$[x, x]$$$ may take longer than reaching $$$[x, y]$$$ where $$$n/x == n/y$$$).

            If $$$n$$$ is close to $$$C$$$, then the number of nodes is $$$O(n)$$$ as in the normal segment tree. In our segments, the density of the endpoints is more to the left. I tried for many values of $$$n$$$, at least 85% of the endpoints are in the range $$$[1, 2C]$$$. So it is like you are building a normal segment tree in $$$O(C_{85}+logn)$$$ on 85% of the points, and a dynamic segment tree in $$$O(C_{15}\times logn)$$$ on 15% of them.

            So I think we can safely use this method assuming it works in $$$O(C)$$$, at least for the usual limits ($$$0.15\times log10^9 < 5$$$).

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

IN Problem D:

why I input: 1 4 the model solution prints: 133737

Is there a problem with the model solution?

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

For problem B, the precalculation table could be further simplified to only require $$$O(A^4)$$$ time and $$$O(A^3)$$$ space, making the final time complexity $$$O(|s| + A^4)$$$

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

very clean and easy to understand editorial, thanks. Also interesting problems

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

In problem F we can also empirically verify that for each range with same $$$g$$$ can have one of following forms:

  • none of periods is possible

  • all periods are possible

  • all periods are possible except for the lowest

  • all periods are possible except for the highest

  • all periods are possible except for the lowest and the highest

To check which is the case we only need to check if the lowest is possible, the highest is possible and if none of them is also any in the middle.

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

In Problem D-1337 String, can someone give me the shortest possible answers for n=5 and n=7. Is it 11111337 and 1111111337 ?

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

    i dont know if they are minimal but they are shorter than your examples:

    5: 1337737

    7: 1337337

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

1202B can be done in O(n+A^3). Though this improvement is irrelevant with given bounds, I think it's still worth noting.

Filling u..v and x..y is identical if v-u=y-x (mod A). Hence we only need track how many of each kind difference exist in string (for example, 8..4 and 1..7 both count as difference 6). Edge weight 1 SSSP can be done in simple linear BFS, so the inner loop will only take O(A).

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

Hi, for problem E I have implement the idea in the editorial (the MAG idea with only basic string structures), my submission is here: 65325941. But I get TLE still. Any ideas what I'm doing wrong here? Thanks.

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

Problem B is a quite elegant dp Problem.

Honestly, Editorial's method seems tough, so here's my simple Floyd dp solution , where basically we just calculated dp[x][y][i][j] i.e. for each fixed counter (x-y), the min. digits needed to go from digit i to digit j. My solution is just another implementation of this.

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

You can also solve 1202C using a randomized approach. Randomly insert a random character (either 'W', 'A', 'S', or 'D') and find the best rectangle.

138389957