AtCoder Beginner Contest 272 Announcement

20 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Kyou_mo_kawaii

20 месяцев назад, # ^ |

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!

→ Ответить

20 месяцев назад, # ^ |

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)

→ Ответить

20 месяцев назад, # ^ |

Can you please explain your solution?

→ Ответить

20 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

20 месяцев назад, # ^ |

Can you please explain your 2 pointer approach? I think there are going to be multiple pointers at once

→ Ответить

20 месяцев назад, # ^ |

Exactly like this task

→ Ответить

munnabhaimbbs

20 месяцев назад, # |

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

→ Ответить

20 месяцев назад, # ^ |

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 ==.

→ Ответить

munnabhaimbbs

20 месяцев назад, # ^ |

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

→ Ответить

20 месяцев назад, # ^ |

BINARY SEARCH PLEASE!

→ Ответить

getgoodalready

20 месяцев назад, # ^ |

← Rev. 3 →

sqrtl is not perfect either. Use binary search.

Code

long long __sqrt(long long n) {
  long long L = 1, R = 2e9, M;
  while (R-L > 1) {
    M = L + R >> 1;
    if (M * M <= n) L = M;
    else R = M;
  }
  return L;
}

→ Ответить

cleanser

20 месяцев назад, # ^ |

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

→ Ответить

llc5pg

20 месяцев назад, # ^ |

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

→ Ответить

chromate00

20 месяцев назад, # |

← Rev. 2 →

-20

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?

→ Ответить

WaterColor2037

20 месяцев назад, # ^ |

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.

→ Ответить

20 месяцев назад, # |

← Rev. 3 →

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)

→ Ответить

WaterColor2037

20 месяцев назад, # ^ |

← Rev. 2 →

Spoiler

→ Ответить

20 месяцев назад, # ^ |

Before reviewing it, I first pressed the upvoting button.

→ Ответить

20 месяцев назад, # ^ |

← Rev. 5 →

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://codeforces.com/blog/entry/107776.

→ Ответить

SummerSky

20 месяцев назад, # |

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.

→ Ответить

jainmilind

20 месяцев назад, # |

Can anyone explain how hashing solution works for F?

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

→ Ответить

milind0110

20 месяцев назад, # |

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

→ Ответить

20 месяцев назад, # ^ |

+16

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) $$$

→ Ответить

milind0110

20 месяцев назад, # ^ |

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?

→ Ответить