Блог пользователя awoo

Автор awoo, история, 5 лет назад, По-русски

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

Идея: adedalic

Разбор
Решение (adedalic)

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

Идея: adedalic

Разбор
Решение (adedalic)

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

Идея: adedalic

Разбор
Решение (adedalic)

1202D - Print a 1337-string...

Идея: Roms

Разбор
Решение (Roms)

1202E - You Are Given Some Strings...

Идея: Roms

Разбор
Решение (adedalic)

1202F - You Are Given Some Letters...

Идея: adedalic

Разбор
Решение (PikMike)
  • Проголосовать: нравится
  • +187
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

U good bro?

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +93 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Except problem C

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do we use a suffix array for problem E?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 9   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    in fact bfs can run faster

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      This problem taught me that:

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe hash table failed you this time

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +43 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится
    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится +18 Проголосовать: не нравится

            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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

IN Problem D:

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

Is there a problem with the model solution?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    5: 1337737

    7: 1337337

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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