Is there a discussion page? If not here is one.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
7 | adamant | 154 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Is there a discussion page? If not here is one.
Name |
---|
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.
Nice explaination!
Can you also provide a explaination for problem C? Why can't we use the sqrt function to solve that question?
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.
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$$$).
hey i didn't understand what you are trying to say.
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.
why we can't have a transition of (3,"13") or (4,"14")
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.
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
How to solve E?
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$$$.
Why 50000?
50,000 isn’t strictly necessary but you do need some large number. For overlap between any two strings a and b, the maximum you will consider is 2*n because you might have a situation like acb where the strings are totally disjoint. My submission https://atcoder.jp/contests/panasonic2020/submissions/10951173
Can anyone who got AC give output for N=3 and N=4 in problem D?
Also, will an English editorial be released?
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
Thanks.
How to solve F?