We will hold AtCoder Beginner Contest 272.
- Contest URL: https://atcoder.jp/contests/abc272
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221008T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: PCTprobability, nok0, kyopro_friends, Nyaan
- Tester: Nyaan, kyopro_friends
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
my favourite
How to solve task E?
Just keep incrementing the i-th element by (i+1) and put them into a set for each m. Need to speed up the process by only caring about the cases where the number just becomes 0 and smaller than n. My solution
I'm not able to get the intuition on why it will fit in the time limit :/
Any hints regarding the same?
Because first element is used at most n/1 times, second — n/2 times and so on. So, in total maximum sum over all answers = n * (1/1 + 1/2 + ... + 1/n) ~ n * log(n).
but after all this process how you find mex?
take a look at this code Code
Actually I don't think problem F fits for its position, it would be better to swap it with G indeed.
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
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!
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)Can you please explain your solution?
Sort all cyclic shifts for both given strings. Then find for each shift number of greater or equal by two pointers
Can you please explain your 2 pointer approach? I think there are going to be multiple pointers at once
Exactly like this task
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
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
==.Sqrt messed up my yesterday coderforces also :( Now I use sqrtl everywhere. Now I will append (ll) in front of it every time.
BINARY SEARCH PLEASE!
sqrtl is not perfect either. Use binary search.
Lmao I did the same exact thing, but I was only doing virtual.
Just avoid the sqrt by squaring on both sides of the equation.
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?
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.
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)
Carefully review if it really holds that $$$f(S, i) = f(T, j)$$$ if and only if $$$\mathrm{sa}^{-1}[i\text{ for }S] \lt \mathrm{sa}^{-1}[j\text{ for }T]$$$.
Before reviewing it, I first pressed the upvoting button.
Yes, there are counterexamples.
Let $$$T=\texttt{"dcbaf"},\,S = \texttt{"afdcb"}$$$.
Here is my code:
In my concatenation, the
largeis $$$\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 \lt 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://mirror.codeforces.com/blog/entry/107776.
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.
Can anyone explain how hashing solution works for F?
I am not able to think how to compare strings lexicographically using it
Can someone explain for problem $$$G$$$ why we need to check only $$$log_{3/4}(1-L)$$$ times randomly according to the editorial?
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) $$$
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?
S = Subset of array which will be in answer. |S| $$$ \geq \lfloor \frac{n}{2} \rfloor + 1 $$$. For getting correct answer we want that both values which are chosen must belong to S. Its probability, p = $$$ \frac{|S|*(|S|-1)}{n*(n-1)} $$$.
$$$ |S|*(|S|-1) \geq (\lfloor \frac{n}{2} \rfloor+1)*(\lfloor \frac{n}{2} \rfloor) \geq (\frac{n}{2})^2-(0.5)^2$$$ (-0.5 term will come when n is odd) $$$ \geq \frac{n^2-1}{4} \geq \frac{n^2-n}{4}$$$
Substituting in p, we get p $$$ \geq \frac{1}{4} $$$
Thankyou