iLoveIOI's blog

Discussion page for Panasonic Programming Contest 2020?
By iLoveIOI, history, 5 years ago, In English

Is there a discussion page? If not here is one.

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

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

I was waiting for one but didn't see it, thanks.

For problem D, (generating all lexicographically least isomorphic strings of length N) I didn't get it during the contest but it turned out to be a pretty easy DFS. The definition they gave about isomorphic strings is the rigorous one, but I couldn't really work with it so I used my own: the string $$$s_1s_2s_3\ldots s_n$$$ gets mapped to an integer sequence by matching letter $$$s_1$$$ to $$$1$$$, then in general, $$$s_i$$$ is mapped to the rank in which we first saw the letter $$$s_i$$$. So e.g. $$$babcza \mapsto 121342$$$. And isomorphic means two strings get mapped to the same sequence. To do a DFS through these sequences, one can define states as pairs $$$($$$ max integer used so far, $$$s)$$$ where $$$s$$$ is a sequence. Then to advance a state, you can append $$$s$$$ with one of $$$1,2,\ldots,$$$ max, plus one additional state which increases the maximum. This generates all the states, then you can sort them and output at the end, or just push to the stack in the right order so that during the DFS they are alphabetical.

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

    Nice explaination!

    Can you also provide a explaination for problem C? Why can't we use the sqrt function to solve that question?

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

      You can use sqrt function but some of the cases have precision over 200 significant digits,hence either adding an epsilon value as given in the editorial or changing the precision value of sqrt function will lead to AC.

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

      In the editorial they gave a nasty example where $$$\sqrt{a}+\sqrt{b}$$$ and $$$\sqrt{c}$$$ were equal to many decimal places (15 or something). In such cases it is better to try and convert it into an integer comparison.

      If $$$\sqrt{a}+\sqrt{b} < \sqrt{c}$$$ then we get, on squaring, since both sides are positive the inequality is preserved: $$$2\sqrt{ab} < c-a-b$$$

      Again we can square it, but careful, as we must check $$$c > a+b$$$ so that both sides are positive. If so, then we get $$$4ab < (c-a-b)^2$$$ which is required condition (along with $$$c > a+b$$$).

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

    hey i didn't understand what you are trying to say.

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

      Start the dfs with the state (0,"") as defined above; this can transition to (1,"1"); then this can transition to (1,"11") or (2,"12"). The former can transition to (1,"111") or (2,"112"), while the latter can transition to (2,"122") or (3,"123"). Continue like so until you get to sequences of length N, then output the results as strings where 1 maps to 'a', 2 maps to 'b', etc.

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

        why we can't have a transition of (3,"13") or (4,"14")

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

          Because we have to choose the smallest string lexicographically, so for any string we would place a smaller element in the starting. For example, abc and acb are both isomorhpic strings but we should print abc because it is lexicographically smaller.

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

    I think The problem Statement is correct But Confusing

    See for N=1

    All the isomorphic string are a,b,c,d,e,............,z(smallest one is a)

    for N=2

    aa,bb,cc,dd,ee,ff,gg,..........,zz(with first and second value equal. All isomorphic to each other and the smallest one is aa)

    ab,ac,ad,......,az,ba,bc,bd,.....bz,ca,cb,cd,....,cz,...........................zz (with first and second value different. All isomorphic to each other and the smallest one is ab)

    So for N=3

    aaa(smallest with all value same)

    aab(smallest with first two same and last one different)

    aba(smallest with first and last same and middle one different)

    abb(smallest with last two same)

    abc(smallest with all three different)

    So this is what is required finding ALL smallest isomorphic strings(normal) of length N

    And All the method told in this comment section works

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

How to solve E?

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

    The editorial solution is here: https://img.atcoder.jp/panasonic2020/editorial.pdf but in Japanese.

    Define for signed integers $$$k$$$, the $$$k$$$-overlap from string $$$s$$$ to $$$t$$$, as the string $$$s_0 s_1\ldots s_{m-1}$$$ and $$$t_0t_1\ldots t_{n-1}$$$ "aligned at" the indices $$$s_0$$$ and $$$t_k$$$. This is actually the $$$-k$$$ overlap, and the $$$+k$$$ overlap is defined by aligning $$$s_k$$$ and $$$t_0$$$. You can think of starting off with $$$s$$$ and $$$t$$$ left-aligned, and then $$$+k$$$ means slide $$$s$$$ to the left, while $$$-k$$$ means slide $$$s$$$ to the right. We say the overlap is "good" if $$$s_0=t_k, s_1=t_{k+1}$$$, $$$s_2=t_{k+2}$$$ etc. for all valid indices. It only takes one mismatch to make the overlap bad. And note that if the magnitude $$$|k|$$$ is large enough, then the overlap is trivially good (because there is no overlap at all).

    Looking at the code, they are building arrays ab, ac, and bc, which you can think of as:

    $$$ab[k]$$$ = true means the $$$k$$$-overlap from string $$$a$$$ to $$$b$$$ is bad

    and similarly for ac and bc (actually they do a translation by +50,000 so that ab[-k] is defined).

    Lastly to get the answer, they try out various overlaps (in the last double loop, they are unfortunately using letters $$$i$$$, $$$j$$$ in the way that I use $$$k$$$). Precisely, a good superstring for $$$a,b$$$ and $$$c$$$ must simultaneously have a good overlap for pairs $$$(a,b)$$$, $$$(a,c)$$$, and $$$(b,c)$$$. But the reason we don't have to do a triple loop over all possible overlaps $$$k_1,k_2,k_3$$$, is that once you fix an overlap for any of the two pairs, like $$$a,b$$$ and $$$a,c$$$, then you are forced to use a certain overlap for the last pair $$$b,c$$$. In other worsd, $$$k_3$$$ for pair $$$(b,c)$$$ is some formula depending on $$$k_1$$$ and $$$k_2$$$.

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

Can anyone who got AC give output for N=3 and N=4 in problem D?

Also, will an English editorial be released?

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

    For N=3 aaa aab aba abb abc For N=4 aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd

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

How to solve F?

→ Reply