Tanzir5's blog

By Tanzir5, history, 21 month(s) ago, Could not find any post for today's open cup. Let's discuss the problems here. How to solve F and G? Comments (76)
 » For the second time in recent opencups, I wasted half of the contest trying to solve a problem with 100 OKs without any success. How to solve I?
•  » » Recursively find smallest suffix.
•  » » Sort suffixes of the string (suffix array), iterate them in increasing order. The answer for suffix starting at position $i$ is $j-i$, where $j$ is the minimum position encountered so far that is larger than $i$.
•  » » » But how to find the smallest suffix on segment? We when we cut the string in two halves the order of suffixes in the right half may change.
•  » » » » The recursive segments are formed such that the order of suffixes is the same as in whole string.Proof: Let $s_k\ldots s_r$ be the smallest suffix of $[l, r]$. Now in $[l, k - 1]$, consider two positions $i$ and $j$, with $i < j$. If the comparision of suffixes at $i$ and $j$ ends before index $k$, clearly they follow the same order as in the whole string. Else, the suffix starting at $j$ must be smaller (as required) as the suffix starting at $k$ is the smallest. In the right half, nothing has changed so the order is preserved there as well.
•  » »
•  » » Is it well-known? Neither of us knew Lyndon word decomposition and it took 2hour to come up with the cool stack-based solution that is much harder than intended. On the other hand I don't think it's reasonable to believe 100 teams knew it.
•  » » » Curious to know your solution. We solved it using just suffix array and set. For any suffix_starting_at_i, we tried to find the smallest suffix_starting_at_j, where j > i and suffix_starting_at_j < suffix_starting_at_i. for ith suffix ans should be j — i.
 » 21 month(s) ago, # | ← Rev. 2 →   F:if $sum(Arr) \leq C$ it's trivial else:it can be easily proved that the answer is at least $C - max(Arr)$ consider the following greedy algorithm iterate over the array decreasingly if $Arr[i] \leq Cur_C$ then $Cur_C := Cur_C - Arr[i]$, it's easy to prove that at the end $Cur_C$ will be less than all elements not used in the array.Now let's call the elements used set $L$ and the elements not used set $R$. I want to add $i - j$ to $Cur_C$ such that $Cur_C + i - j \leq C$ and $i-j$ is maximum and $i$ is the sum of a subset of $L$ and $j$ is the sum of subset of $R$.you can just consider all sums less than a certain $X$ for both sets that $X$ for me was $10^5$ but I think it should work if it's equal $2 * (C-Cur_C)$.
•  » » Well I think the correct bound is somewhere near $N \times C^{0.5}$ (consider standard deviation). I'm surprised that $10^5$ passes, but anyway with bitset I think you can do as much as 5000000.The intended solution is some fancy 1998 paper. It is inspiring though.
•  » » » No, I think the correct bound for his solution is much worse. I think some tests where this value is $O(nW)$ may be constructed (but I am too lazy to think about them).
•  » » » The bound is $w_{\text{max}} \sqrt{N}$, and union bound is pretty loose, so its not so surprising.
•  » » » Which paper are you referring to?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   Probably this one: Linear Time Algorithms for Knapsack Problems with Bounded Weights. The paper derives an $O(n \max(a_i))$ algorithm for the subset sum problem. Luckily I read that paper some time ago, so we used this approach during the contest.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   I solved F purely using cutoffs.At first I have sorted $a$ in non-increasing order. Using a recursive function solve(prefix, sum) I try to add the element if it makes sense (with the current answer) and not using it after.I can't prove it works fast, but the runtime is just 7ms (absolutely nothing). Maybe the tests were weak. Code of the functionp = suffix sum of a void rec(int i, int curr) { if (curr > c || ans == c) return; chmax(ans, curr); if (i == n) return; if (curr + p[i] <= ans) return; rec(i + 1, curr + a[i]); if (curr + p[i + 1] > ans) rec(i + 1, curr); } UPD: the tests are weak
•  » » » I guess I have a really really high upper bound first of all it's obvious like my solution that the answer will become at least $N - max(Arr)$ in $N$ operations then each $N$ operations either the answer will increase or the recursion will terminate so you will make at most $N ^ 2$ operations this is a really really high upper bound thou as I don't take into account other factors.
•  » » » » I guess it's not that easy. When I call the function, I make a "promise" that the answer will increase, which is not true all the time.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   Your solution will call rec at least $2^{98}$ times in this test: n = 99 + 98 c = 99 * 99 a =  * 98 +  * 99
•  » » » » It is indeed. Nice test.
•  » » What about this case: n = 9998 + 9999 c = 9999 * 9999 a =  * 9998 +  * 9999 Your solution will greedily take all $10000$, but the only optimal solution is taking all $9999$, so on the second step you need to run a knapsack up to $9999 \cdot 9999$ ~ $1e8$.
 » How to solve Problem Q(Easy Puzzle) ? And the problem J(Program Optimization) can solved with Cartesian tree ? Because my solution for J with segment tree gived TLE ,because we have a constant when two position updates and it will be 2*log2(n) .
•  » » J: Since the input is a permutation it can be solved in O(n + q). Mex from an interval is the minimum element outside this interval (Add $n$ to the beginning of the array). So you can keep the the minimum among prefix and suffix.Update can be done in O(1) since you should only update consecutive elements (at most two values from the prefix and suffix change).Query can be answered in O(1) checking both prefix and suffix outside the interval.Code
•  » » » Thanks mnaeraxr! I understasnd .
 » How so solve D?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   $p_0 = (1, 2, 0, 3)$$p_1 = (3, 0, 1, 2)$$p_2 = (0, 1, 3, 2)$The value of substring $s_l, ... , s_r$ is the product of permutations $p_{s_l} \cdots p_{s_r}$. You can calculate number of substrings with value $q$ for each $q$ with a simple dp with $24n$ states. Then for each query $t$ you calculate value of $t$ and print answer for this permutation.
•  » » » Thank you. Very beautiful idea!
•  » » » How do we prove that for two strings with the same value, there exists a sequence of operations which transforms one to the other?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 12 →   UPD Fixed the duplicated text problem and incorrect motiavation for equality $(stst^2)^3 = e$.After some reductions ($1$ is expresisble through $0$ and $2$), we arrive on the following group presentation: $\langle s^2 = e, t^3 = e, (st)^4 = e \rangle$. Then, consider a reduced word over $s$ and $t$ in the sense that it does not contain $s^2$ and $t^3$ substrings. It looks like $t^p \cdot (st^{a_1}) \cdot (st^{a_2}) \cdot \ldots \cdot (st^{a_b}) \cdot s^q$, where $b$ is the number of $st^{a_i}$ "blocks" ($b$ may be equal to zero), and $1 \leqslant a_i \leqslant 2$ for all $i$ from $1$ to $b$. The vallue $p$ corresponds to the prefix of $t$'s before any block, hence $0 \leqslant p \leqslant 2$, and, similarly, $0 \leqslant q \leqslant 1$.Suppose that there are two consequitive blocks with $a$'s equal to $1$. Then, we can use the equality $(st)^2 = (t^2 s)^2$ (follows from $(st)^4 = e$) and make the number of blocks smaller by "merging" the $t$'s at the beginning to the end of the previous block or the starting prefix of $t$'s and merging $s$ on the end to the beginning of the next block or the ending suffix of $s$'s (said merges can trigger numerous collapses because of $s^2$ and $t^3$ substrings, but then the number of blocks will decrease even more). Similarly, if there are two consequtive blocks with $a$'s equal to $2$, then we can use the equality $(st^2)^2 = (ts)^2$ (follows from $(ts)^4 = s (st)^4 s = ss = e$) and make the number of blocks smaller again.Hence, in the shortest possible word for any given element of the group, blocks $st$ and $st^2$ in the middle alternate. How many blocks can there be? Let's notice (see the end of the comment for how to come up with such equalities) that $(stst^2)^3 = ((t^2s)^3 (st^2))^3 = ((t^2s)^2 t)^3 = (t^{-1} (st^2 s) t)^3 = t^2 (st^2s)^3 t = e$, because $(st^2s)^3 = (st^2s) \cdot (st^2s) \cdot (st^2s) = st^6s = ss = e$. Similarly, $(st^2st)^3 = e$ (here we just used that $(ab)^n = e \Rightarrow (ba)^n = (a^{-1} ab a)^n = a^{-1} (ab)^n a = a^{-1} a = e$).Hence, if there are at least $3$ blocks, we can replace them with no more than $2$ blocks by applying $(stst^2)^3 = e$. For example, $stst^2st = (stst^2st)^{-1} = t^2stst^2s$ and there are only two blocks after dealing with $t^2$ to the left and $s$ to the right. Hence, there are only $3$ possibilities for $p$, $2$ possibilities for $q$ and $5$ possibilities for middle blocks: $a = \varnothing, a = (1), a = (2), a = (1, 2), a = (2, 1)$. Therefore the resulting group has size at most $30$. But we know already that $S_4$ with $24$ elements is good enough, hence the group is indeeed $S_4$ (because otherwise it contains $S_4$ as a proper subgroup and would therefore have at least $48$ elements).If you are wondering why we ended up with $30$ elements instead of $24$: that's because the elements with $a = (1, 2)$ and $a = (2, 1)$ are actually equal. For example, $t^2 (st^2 st) = (st st^2)$, because both are $e$ when multiplied by $tst^2s$ from the right: the right-hand side for trivial reasons and the left-hand side because $(t^2s)^4 = e$.This whole argument may look like magic (especially $(stst^2)^3 = e$ part), but recall that we already have an educated guess of how the resulting group will look like! If we assume that it is indeed $S_4$, with $s$ being a transposition and $t$ being a $3$-cycle, then $stst^2$ is a (different) $3$-cycle. Hence, $(stst^2)^3$ should be equal to $e$ (if it is not, our guess is not correct). Hence, we can instantly judge which equalities are worth trying to prove and which are not.
•  » » » » » Holy cow...
•  » » » » » Some text is duplicated
•  » » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   Thanks. Should be fixed now.
•  » » To explain number of accepts, I think this was well known for some people. I think this is very tricky and very hard to come up with, but very similar problem already appeared a few years ago.
•  » » » How to come up with these specific permutations?
•  » » » » We generated all possible permutations and checked for some set of three permutations that fulfill those requirements:Code
•  » » » » 21 month(s) ago, # ^ | ← Rev. 4 →   Just pen and paper and trial and error with a bit of insight. 22 should be identity, so its permutation should be some number of swaps. 000=012=id, so 0 should be some number of 3-cycles. And $1=0^{-1}2^{-1}$. That already greatly reduces a search space to just a few cases that you can try after assuming that they act on a small set, 4 should be a good guess (where you basically have two cases — that there is 1 swap in 2 and that there are 2 swaps). I used 5, but now I see that all my permutations fix fourth element xD.It is clear that if for two words I get different permutations then they are not equivalent, but I don't know why if they give the same permutation then they are equivalent.
•  » » » » » Or you mean the opposite? When they are same you know they are equivalent. But if they are not, how do you prove that they are not equivalent? Or in other way, how do you know that two different permutations are not equivalent?
•  » » » » » » I am pretty sure I didn't mean the opposite. Changing characters according to rules doesn't change the permutation, so equivalent words -> equal permutations.
•  » » » » » » » Yes. I think we both said the same thing from different perspective. Two equivalent words would generate same permutation. But how does one know that two non equivalent words won't generate same permutation.
•  » » » » » » » » No idea ¯\_(ツ)_/¯
•  » » » » » Other than what you mention, thinking in hindsight about this problem, there are several gaps on my reasoning. To use Cayley Theorem we need to prove before finding elements, that group generated by $0$, $1$ and $2$ is finite (otherwise chances are that no subgroup of permutations exists). I just looked for 3 permutations that satisfy constraints given in the problem, but I needed to add some requirements that looked somehow artificial (but were necessary): All $i$ should be distinct from the identity. All pairs of $i$ were different. $1^2 \neq 0$ (we already know that $1^4 = 0$) Otherwise, I'd easily hit a "solution" where all elements are $0$ (the identity).How can I justify that those additional constraints are actually required for this to work.
•  » » » Problem K here has the same idea I guess.
 » How to solve J and L?
•  » »
 » We spend a lot of time on J and 90% of that time was before realizing that elements of array are in fact distinct. It is a very bad practice to put such crucial information in input section only. Please write it either before this section or make it bold or at least use a word "permutation" which is easier to spot.
•  » » I am sorry. Next time I will put them in the statement with bold fonts.
 » Graphs in problem E could be remembered from an incredibly painful problem It's no wonder that in that case its authors decided to give ABSOLUTELY TRASH SAMPLES and it is very hard to get answers for some meaningful cases in bruteforced way, so participants were basically left to submit their answers blindly in a problem where there are a ton of weird formulas and corner cases.
•  » » 20 months ago, # ^ | ← Rev. 2 →   Some small cases (in case this is useful for someone): Spoiler1 1 1 -> 0 2 2 1 -> 0 3 3 1 -> 0 4 4 1 -> 0 5 5 1 -> 60 6 6 1 -> 540 7 7 1 -> 6300 8 8 1 -> 80640 9 9 1 -> 1088640 10 10 1 -> 15422400 11 11 1 -> 229521600 12 12 1 -> 592511979 13 13 1 -> 156697187 14 14 1 -> 344914432 15 15 1 -> 359613562 16 16 1 -> 425606191 17 17 1 -> 512123764 18 18 1 -> 616189691 19 19 1 -> 158211109 20 20 1 -> 962944897 21 21 1 -> 513231905 22 22 1 -> 102324521 23 23 1 -> 226769461 24 24 1 -> 566206183 25 25 1 -> 358816403 26 26 1 -> 489196957 27 27 1 -> 876055909 28 28 1 -> 985173136 29 29 1 -> 791893044 30 30 1 -> 690300360 1 2 2 -> 0 2 3 2 -> 0 3 4 2 -> 0 4 5 2 -> 0 5 6 2 -> 0 6 7 2 -> 0 7 8 2 -> 0 8 9 2 -> 0 9 10 2 -> 90720 10 11 2 -> 2721600 11 12 2 -> 69854400 12 13 2 -> 796255993 13 14 2 -> 702655678 14 15 2 -> 496068260 15 16 2 -> 21791734 16 17 2 -> 984532396 17 18 2 -> 382394489 18 19 2 -> 862720752 19 20 2 -> 913611516 20 21 2 -> 759141792 21 22 2 -> 887313313 22 23 2 -> 970432554 23 24 2 -> 456258681 24 25 2 -> 648826809 25 26 2 -> 18288183 26 27 2 -> 685751383 27 28 2 -> 866437147 28 29 2 -> 630027108 29 30 2 -> 760347251 30 31 2 -> 16072278 1 3 3 -> 0 2 4 3 -> 0 3 5 3 -> 0 4 6 3 -> 0 5 7 3 -> 0 6 8 3 -> 0 7 9 3 -> 0 8 10 3 -> 0 9 11 3 -> 0 10 12 3 -> 0 11 13 3 -> 0 12 14 3 -> 0 13 15 3 -> 0 14 16 3 -> 0 15 17 3 -> 377884570 16 18 3 -> 533330007 17 19 3 -> 984432494 18 20 3 -> 667987232 19 21 3 -> 838083387 20 22 3 -> 974454655 21 23 3 -> 591001656 22 24 3 -> 765783512 23 25 3 -> 271763550 24 26 3 -> 612976847 25 27 3 -> 699605662 26 28 3 -> 712402977 27 29 3 -> 896014750 28 30 3 -> 302774408 29 31 3 -> 889714663 30 32 3 -> 374354978 1 4 4 -> 0 2 5 4 -> 0 3 6 4 -> 0 4 7 4 -> 0 5 8 4 -> 0 6 9 4 -> 0 7 10 4 -> 0 8 11 4 -> 0 9 12 4 -> 0 10 13 4 -> 0 11 14 4 -> 0 12 15 4 -> 0 13 16 4 -> 0 14 17 4 -> 0 15 18 4 -> 0 16 19 4 -> 0 17 20 4 -> 0 18 21 4 -> 0 19 22 4 -> 0 20 23 4 -> 0 21 24 4 -> 0 22 25 4 -> 201980476 23 26 4 -> 873305499 24 27 4 -> 710632815 25 28 4 -> 946031135 26 29 4 -> 470486935 27 30 4 -> 298572085 28 31 4 -> 270532941 29 32 4 -> 834786964 30 33 4 -> 232895273
 » I thought every opencups were gonna be annoounced on un_nik's telegram group :( Missed this one cuz of it.
 » G is extremely well known. Appeared in WF 2006 and Croatian OI 2012. But here it has weights, so when changing your code remember to correctly plug in the number.
•  » » It wasn't known to me :) How to solve it?
•  » » » You can do something similar to bitonic path, so instead of going back and forth just find two paths. Preprocess with Floyd Warshall. Let $DP[x][y]$ = (minimum distance to make forward path end at $x$, and backward path starts at $y$). You move either end of path ($DP[x][z], DP[z][y]$), or you swap two paths ($DP[y][x]$). This represents all possible paths (sorry I don't remember why, but I guess it's not too hard to prove). Anyway, in this state graph, you can use Dijkstra to find the shortest path to the desired state.
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   Why can I swap two paths?Edit: There is another explanation in https://codeforces.com/blog/entry/77187?#comment-619429, combining with yours I guess I have the whole picture now. Thanks for the explanation!
•  » » It seems that I have missed the problems you have mentioned perfectly -- In my OI career, I almost have upsolved all COCI problems, until 2010, while the 2006 task is too old for me. :( Little shame to bring such classical problem back to the table.
 » I am a teaching assistant in an "Introduction to Combinatorics" course on my university and something like a month ago when I was preparing a class about matchings and flows I gave my students a mathematical version of today's problem A, where you need to prove that such tiling is possible if and only if there is no triangle pointed upwards with side k such that there are more than k unit forbidden triangles in it. Too bad mine solution was rather not constructive, through Hall's condition, so we didn't manage to get it accepted today (however Radewoosh already upsolved it with some naive heuristics searching for matching).If anybody wants to read my proof of that fact, you can find it on the last page here: https://www.mimuw.edu.pl/~nayar/wdk_2020/wdk_2020_cwiczenia_6_rozwiazania.pdf (and exact statement here: https://www.mimuw.edu.pl/~nayar/wdk_2020/wdk_2020_cwiczenia_6_zadania.pdf)
•  » » I heard that it is from some IMO shortlist.
•  » » » Ah yeah, I forgot to mention that if I'm not mistaken it's from shortlist :D. Should have checked that during the contest...
•  » » »
•  » » » » Lol, I even have third post in this topic xD. Sadly it sounds pretty obscure xD No wonder it is shorter xD
 » K, anyone?
•  » » K is yet another boring tree dp problem. If $x = 0$ this is just counting matchings in the tree. Let's generalize for nonzero $x$.First of all, let's subtract $x$ from all $d_i, a_i, b_i$. Now we have an edge of weight $x$ between any two vertices, including loops.Now let's cover the tree with cycles (of length 1 or 2) and paths without using edges of weight $x$. After that we need to merge some paths so that they all become cycles, using edges of weight $x$. If we have $k$ paths we will multiply current value by $\pm x^k$. The sign depends on how we connect paths, so we need to count the number of ways to get both signs. It's easy to see that if $k \geq 2$, then those numbers are equal and we don't add anything to the answer. So we actually need to cover the tree by at most one path and some cycles. This is easily done with dp with a few cases.
•  » » » BTW, this problem seems much easier than I, but I haven't read it during contest. :(
•  » » » It again amazes me how you absolutely discard whole insight specific to some problem to sum it up as "another boring tree dp". It's not the freaking tree dp where the hardness lies.
•  » » » » What’s hard otherwise?
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   Well to me it's not obvious you should do this... for example, why should it be easily solvable if you put complete graph of edges between all vertices. Who will tell me it's going to cancel for k >= 2? Plus, there are other ways of computing a determinant, such as doing some row/column operations.
•  » » » » » » Hmm, I just putted $x=0$, and the direction became crystal clear. All member of our team had created problem about this thing ;)
•  » » » » » Well, each one of us thought about this problem for some nontrivial time and we got no idea. Only after competition I got an idea that terms for $k \ge 2$ cancel out and felt pretty proud for observing this and then solution followed rather quickly. There are tons of ways you can approach problems with determinants (operations on rows to make it prettier, doing Laplace expansion, using some little known formulas e.g. even this looks fairly relevant: https://codeforces.com/blog/entry/74131, etc. etc. etc.). And, as stupid as it sounds, I didn't realize that case $x=0$ can be thought about as cycle covers on a tree since I imagined it as matchings in a bipartite graph... (it is sometime the better way, but definitely not here though and that was not the hard part)I think that people who can't properly judge where the difficulty lies in various problems will have troubles in becoming good teachers (since how do you focus on explaining the hard part if you don't know what the hard part is?).
•  » » » » » » I'll be very grateful if aid somehow become my teacher. The pain would be worth.
 » G: If I draw path from s to t I want to wonder how path from t to s may look like. What I've drawn is kind of a general shape of it (some horizontal blue segments may consist of one vertex). I want to go from $s$ and kind of simultaneously build two paths, one black and one blue.On the beginning I use Floyd-Warshall what allows me to make bigger jumps (that's surprisingly important). I want to have $dp[a][b]$ which means the lowest cost such that I already built some partial solution which contains path from $s$ to $a$ and from $b$ to $s$. I want to have two types of transitions. Look at four colored vertices (in red, green and yellow) and call them $a, b, c, d$ from left. I want to have transition from red pair $(a, b)$ to green pair $(a, c)$ and it has cost $dis[b][c]$. I want to have a transition from green pair $(a, c)$ to yellow pair $(c, d)$ with cost $dis[c][d] + dis[d][a] - p_a$. Some special case if that blue horizontal segment is one vertex may be needed. I compute these dp values in Dijkstra fashion.
 » How to solve H?
•  » »
 » Problem B can actually be done in $O(N^2)$ with more usage of the structure of the problem:Consider a balanced string with $a$ $1$s and $b$ $0$s ($a+b=n$). Now, call the "score" of a substring the sum of the values of each of its characters, where each $1$ has value $b$ and each $0$ has value $-a$.The total score of the string is $0$, so the substrings of any length $L$ also have an average score of $0$. Furthermore, two substrings of length $L$ are within $1$ of each other iff their score is within $b-(-a)=n$. (Note that all substrings of length $L$ have the same remainder mod $n$).This implies that a string is balanced iff every substring has a score strictly between $-n$ and $n$. Therefore, the scores of all prefixes must lie within an interval of size $n-1$. Note that for a given interval, the string we produce is uniquely determined (as there is only one feasible value for each prefix).Now, consider all strings that are produced as the interval ranges from $[0, n-1]$ (the lex max balanced string) to $[-(n-1), 0]$ (the lex min balanced string). If a prefix initially has score $K$, then when we change the interval from $[K-n+1, K]$ to $[K-n, K-1]$, we must change the prefix so that its score becomes $K-1$, without changing any neighboring prefix scores. This is achieved by switching $10$ to $01$ at the location of the prefix.Finally, we can compute the number of solutions for strings with $a$ $1$s in $O(N)$ by maintaining the number of mis-matched characters as we sweep from the highest to lowest interval. Each prefix is updated only once, so only $2N$ characters are updated total.Code
•  » » C is simple idea with cases work: $digitroot(A) \equiv sumdigit(A)$ modulo $B - 1$.