### PikMike's blog

By PikMike, history, 12 days ago, translation, ,

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

Tutorial

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

Tutorial

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

Tutorial

1202D - Print a 1337-string...

Idea: Roms

Tutorial
Solution (Roms)

1202E - You Are Given Some Strings...

Idea: Roms

Tutorial

1202F - You Are Given Some Letters...

Tutorial
Solution (PikMike)

• +187

 » 12 days ago, # |   0 U good bro?
 » 11 days ago, # |   +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)
•  » » 11 days ago, # ^ |   +25 Nope, check this "DDDAAA". width is 4, but we cannot reduce.
•  » » » 11 days ago, # ^ |   +5 Oh, Thanks!
 » 11 days ago, # | ← Rev. 2 →   +93 it's impressive how hard were the problems during the contest, but what simple and elegant solution they have.
•  » » 10 days ago, # ^ |   +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.
•  » » 8 days ago, # ^ |   -8 Except problem C
 » 11 days ago, # |   0 How do we use a suffix array for problem E?
•  » » 11 days ago, # ^ |   +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)$.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   -7 Hello, I am new to suffix arrays can you please explain in more detail?
 » 11 days ago, # | ← 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.
•  » » 10 days ago, # ^ |   +3 Can you please elaborate more. What do you mean by "then it exists at all end positions in its subtree"
•  » » » 10 days ago, # ^ |   +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.
•  » » 9 days ago, # ^ | ← 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?
•  » » » 9 days ago, # ^ |   -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.
•  » » » » 9 days ago, # ^ |   0 Ok. Thanks!
 » 11 days ago, # | ← 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
•  » » 11 days ago, # ^ | ← 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$.
•  » » » 11 days ago, # ^ | ← 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$
•  » » » » 11 days ago, # ^ | ← 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 ...
•  » » 11 days ago, # ^ |   +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
•  » » 11 days ago, # ^ |   +3 in fact bfs can run faster
•  » » » 11 days ago, # ^ |   +6 This problem taught me that:When you think of a brute-force solution, write it down, maybe it can pass...
•  » » » » 11 days ago, # ^ | ← 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 CodeHere is the result I got $\to$ Link to ResultDid I get it wrong? Please point it out :D
•  » » » » 11 days ago, # ^ | ← 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)
•  » » » » » 11 days ago, # ^ |   0 I cannot get your point. Can you please explain further?
•  » » » » » » 11 days ago, # ^ |   0 we call an algorithm is O(n^2) if there is one FOR in a FORO(n^3) if a for in a for and all in a for
•  » » 10 days ago, # ^ |   +8 There are several questions while you are solving the problem using exgcd. 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. 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) 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.
 » 11 days ago, # |   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.com/contest/1202/submission/58480361
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Maybe hash table failed you this time
•  » » » 11 days ago, # ^ |   0 qwq, how to make it fast? Or just give up and study some real data structures?
•  » » » » 11 days ago, # ^ |   +8 You can try to make different contribution maps for each length — this maps can't be large at the same time.
•  » » » » » 11 days ago, # ^ |   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.
•  » » » » » » 10 days ago, # ^ |   +5 https://codeforces.com/contest/1202/submission/58518083Was able to get AC using hashing. Used different maps for different lengths. 2854 ms is not good though...
 » 11 days ago, # | ← 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)
•  » » 11 days ago, # ^ |   +13 Can somebody write a proof as to why does this work everytime?
•  » » » 11 days ago, # ^ |   +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
 » 11 days ago, # |   0 In problem C we can also use data structures to maintain the minimum/maximum value.
•  » » 10 days ago, # ^ |   -11 It is obvious. You shouldn't mention it!
 » 10 days ago, # |   0 In B the answer for digits $a$ and $b$ with $x$ and $y$ fixed depends only on $b - a \mod 10$.And I fail to see how what they do "saves nerves and time" over BFS. :)
 » 10 days ago, # |   0 Can somebody pls explain how floyd warshall algorithm is used to solve B ?
•  » » 6 days ago, # ^ |   +1 Look at my submission 58631999. For every x-y-counter we need to calculate the shortest path between any pair of digits.
•  » » » 6 days ago, # ^ |   0 Thanks :)
 » 10 days ago, # | ← 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$?
•  » » 10 days ago, # ^ |   +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.
•  » » » 9 days ago, # ^ | ← 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.
•  » » » » 7 days ago, # ^ |   +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.
•  » » » » » 7 days ago, # ^ |   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$.
•  » » 10 days ago, # ^ |   +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.
•  » » » 9 days ago, # ^ |   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!
•  » » » » 9 days ago, # ^ |   0 I think it's just $O(C)$ — similar to building a segment tree.
•  » » » » » 9 days ago, # ^ |   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.
•  » » » » » » 9 days ago, # ^ |   +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/kloEB0I'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$).
 » 10 days ago, # |   0 IN Problem D：why I input： 1 4 the model solution prints: 133737Is there a problem with the model solution?
•  » » 10 days ago, # ^ |   0 Sorry，I was wrong！
 » 10 days ago, # | ← 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)$ SpoilerThis can be accomplished by indexing the shortest counter distances (as well as the digit-pairs in $s$) not by the start/end digits $a$ and $b$, but by their "lexical distance" $(b - a) \mod 10$, reducing 2 dimensions to 1.
 » 10 days ago, # |   0 very clean and easy to understand editorial, thanks. Also interesting problems
 » 9 days ago, # |   0 why this code for E is TLE ? https://codeforces.com/contest/1202/submission/58561929
 » 7 days ago, # | ← Rev. 2 →   +8 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.
 » 6 days ago, # |   0 Hey Can Anyone explain me how after inserting D in string for first sample input minimum area become 8.I Think that it will become 3*3 grid.So The Minimum area will be 9.Pls Help Me
 » 3 days ago, # |   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 ?