Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### awoo's blog

By awoo, history, 2 years 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

 » 2 years ago, # |   0 U good bro?
 » 2 years 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)
•  » » 2 years ago, # ^ |   +25 Nope, check this "DDDAAA". width is 4, but we cannot reduce.
•  » » » 2 years ago, # ^ |   +5 Oh, Thanks!
 » 2 years ago, # | ← Rev. 2 →   +93 it's impressive how hard were the problems during the contest, but what simple and elegant solution they have.
•  » » 2 years 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.
•  » » 2 years ago, # ^ |   -8 Except problem C
 » 2 years ago, # |   0 How do we use a suffix array for problem E?
•  » » 2 years 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)$.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   -7 Hello, I am new to suffix arrays can you please explain in more detail?
 » 2 years 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.
•  » » 2 years ago, # ^ |   +3 Can you please elaborate more. What do you mean by "then it exists at all end positions in its subtree"
•  » » » 2 years 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.
•  » » 2 years 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?
•  » » » 2 years 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.
•  » » » » 2 years ago, # ^ |   0 Ok. Thanks!
 » 2 years 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
•  » » 2 years 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$.
•  » » » 2 years 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$
•  » » » » 2 years 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 ...
•  » » 2 years 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
•  » » 2 years ago, # ^ |   +3 in fact bfs can run faster
•  » » » 2 years ago, # ^ |   +6 This problem taught me that:When you think of a brute-force solution, write it down, maybe it can pass...
•  » » » » 2 years 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
•  » » » » 2 years 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)
•  » » » » » 2 years ago, # ^ |   0 I cannot get your point. Can you please explain further?
•  » » » » » » 2 years 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
•  » » 2 years 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.
 » 2 years 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe hash table failed you this time
•  » » » 2 years ago, # ^ |   0 qwq, how to make it fast? Or just give up and study some real data structures?
•  » » » » 2 years ago, # ^ |   +8 You can try to make different contribution maps for each length — this maps can't be large at the same time.
•  » » » » » 2 years 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.
•  » » » » » » 2 years 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...
•  » » » » » » 20 months ago, # ^ |   0 Here's a sqrt hashing solution that fits in under 60% of the time limit: 68428902The main improvements over your version are to iterate over every distinct length that occurs in $S$ and find matches of that length within $T$. When you get a match, you can add the appropriate count to both the start and the end of the substring.This makes the hashing much more cache-friendly and avoids having to hash each substring twice (your solution hashes each once at the start and once at the end). It also removes the need for the hash table entirely.Considering that this is still over half the time limit, I think it's fair to say that the time limit on this problem was quite strict for sqrt solutions.
 » 2 years 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)
•  » » 2 years ago, # ^ |   +13 Can somebody write a proof as to why does this work everytime?
•  » » » 2 years 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
 » 2 years ago, # |   0 In problem C we can also use data structures to maintain the minimum/maximum value.
•  » » 2 years ago, # ^ |   -11 It is obvious. You shouldn't mention it!
 » 2 years 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. :)
 » 2 years ago, # |   0 Can somebody pls explain how floyd warshall algorithm is used to solve B ?
•  » » 2 years ago, # ^ |   +1 Look at my submission 58631999. For every x-y-counter we need to calculate the shortest path between any pair of digits.
•  » » » 2 years ago, # ^ |   0 Thanks :)
 » 2 years 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$?
•  » » 2 years 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.
•  » » » 2 years 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.
•  » » » » 2 years 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.
•  » » » » » 2 years 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$.
•  » » 2 years 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.
•  » » » 2 years 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!
•  » » » » 2 years ago, # ^ |   0 I think it's just $O(C)$ — similar to building a segment tree.
•  » » » » » 2 years 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.
•  » » » » » » 2 years 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$).
 » 2 years ago, # |   0 IN Problem D：why I input： 1 4 the model solution prints: 133737Is there a problem with the model solution?
•  » » 2 years ago, # ^ |   0 Sorry，I was wrong！
 » 2 years 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.
 » 2 years ago, # |   0 very clean and easy to understand editorial, thanks. Also interesting problems
 » 2 years ago, # |   0 why this code for E is TLE ? https://codeforces.com/contest/1202/submission/58561929
 » 2 years ago, # | ← Rev. 2 →   +16 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.
 » 2 years 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
 » 2 years 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 ?
•  » » 2 years ago, # ^ |   0 i dont know if they are minimal but they are shorter than your examples: 5: 13377377: 1337337
 » 23 months ago, # |   0 1202B can be done in O(n+A^3). Though this improvement is irrelevant with given bounds, I think it's still worth noting.Filling u..v and x..y is identical if v-u=y-x (mod A). Hence we only need track how many of each kind difference exist in string (for example, 8..4 and 1..7 both count as difference 6). Edge weight 1 SSSP can be done in simple linear BFS, so the inner loop will only take O(A).
 » 22 months ago, # |   0 Hi, for problem E I have implement the idea in the editorial (the MAG idea with only basic string structures), my submission is here: 65325941. But I get TLE still. Any ideas what I'm doing wrong here? Thanks.
 » 18 months ago, # |   0 Could anyone please help me with problem A's explanation? Why this solution works? I am struggling with the concept of lexicographical smaller here.
•  » » 17 months ago, # ^ |   0 bro, i will try to explain..we are doing the shifting,if we move the first 1 in the respresentation of y to the fisrt, 1 in x from that position,then the result will be lexiographically smaller than x itself,here shifting of 1 is towards left,i.e.,to the right in the reverse which makes it lexiographically smaller,no other position matter because we are considering the first 1 in y only.
 » 16 months ago, # | ← Rev. 2 →   0 In problem F: Let's find at least one such pair cnta and cntb such that cnta+cntb=x What is x here? Thanks in advance.
 » 12 months ago, # |   0 Problem B is a quite elegant dp Problem. Honestly, Editorial's method seems tough, so here's my simple Floyd dp solution , where basically we just calculated dp[x][y][i][j] i.e. for each fixed counter (x-y), the min. digits needed to go from digit i to digit j. My solution is just another implementation of this.
 » 10 months ago, # |   0 Hello, I did not get the solution of problem A. How lexicographically smallest string is found here ?How here only one position is considered?
 » 7 months ago, # |   0 Can Someone Explain the A problem — You are given two binary strings