### allllekssssa's blog

By allllekssssa, history, 4 years ago,

Hi,

GP of Serbia is organized today as regular Opencup round. Contest is prepared for ByteDance camp and first took part at May 3rd. Our ICPC team, RAF Penguins, chose some tasks from previous national competitions in Serbia. We would like to mention setters of the tasks:

Pajaraja : H

milisav: C, D

ivan100sic :B, G, J

dd__ : I

Ramsey: F, K, L

allllekssssa: A, E

Thanks for participation!

• +112

 » 4 years ago, # | ← Rev. 3 →   +39 How to solve G and J?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 The solution to $G$ is as follows. Note that the minimal period $a$ of the periodically repeating string $A$ must be a cyclic shift of the minimal period of the periodically repeating string $B.$ Also, note that $a$ must be the minimal period of the string $A + A,$ thus, it can be easily found by using prefix function. Now we need to find a multiset of strings from $S,$ such that $a$ is their concatenation's minimal period and their length is divisible by $|a|$. Let's build a directed graph on $n$ vertices $(n = |a|)$ numbered from $0$ to $n - 1.$ For each string $s$ from $S$ let's find all the positions $0 \leq pos \leq n - 1$ such that $s$ will be a substring of periodically repeating string $a$ and the position of its first symbol will be the same as some repeat's position $pos.$ For example, if $a = baababca$ and $s = ab,$ then $pos$ can be $2, 4,$ and $7.$ This part can be done using KMP algorithm with some heuristic optimizations. Then, for each $pos,$ add an edge in the graph from $pos$ to $(pos + |s|)$ $mod$ $n.$ Hence, we just need to find the length of the minimal cycle in this graph and since the graph's size is at most $500,$ it can be done by Floyd-Warshall's algorithm.
•  » » 4 years ago, # ^ |   +10 J is similar to ARC084 F, try to read its editorial.
•  » » » 4 years ago, # ^ |   0 Is there approach, based that count of bits of numbers lower than 62 (instead of 4000, in the problem above)?
 » 4 years ago, # |   +24 How to solve G and J?
 » 4 years ago, # |   0 What's the special case of I? (Seeing so many penalties I am assuming there is a corner case)
•  » » 4 years ago, # ^ |   0 No special cases, you just need $O(n^2)$ time and $O(n)$ memory.
•  » » » 4 years ago, # ^ |   0 How to solve I?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 When two marbles collide, just swap them. Fix 1st marble's position, then there are only O(1) candidates for the time when considered mod 2L so there are at most O(N) candidates overall. Then each marble's position can be at most two positions. I construct graph, where edge corresponds to that relation and OK iff in every connected component (number of nodes) <= (number of edges) holds.
•  » » » » » 4 years ago, # ^ |   0 Or every connected component is even in size
•  » » » 4 years ago, # ^ |   -10 I think memory was the key and our solution is $O(n^2 \log n)$ time
•  » » » » 4 years ago, # ^ |   +18 Well, my $O(n^2 \log n)$ with priority_queue didn't pass.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +13 Hmm not sure why wa.My idea was: we can consider the ball transparent and the array segment are concatenated and alternately mirrored. for the first ball there are 4 different time candidates to be on one of the n switches (other are modulo 2L time apart). So in total 4n candidates. So let's solve for each time candidate Next for each balls we find two possible locations it can be (to left or right) so we get a bipartite graph where left is ball right is switch position and degree of each of left side nodes is at most 2 so we greedily do matching. if any of the nodes are of degree 0, no matching next, check right side nodes. For 1 degree nodes, do matching (and recursively check if this matching made another right side of degree 1). If at some point we make degree of a right side nodes 0 we are done. otherwise all left and right side nodes have degree 2, so they are cycle. So matching is possible.
•  » » » » » 4 years ago, # ^ |   0 What happens if you replace the matching part with Kuhn?
 » 4 years ago, # |   +8 Problems $B$ and $E$ are simply wonderful!How to solve $E$? I believe we can construct the array $B$ with $k=12$ such that it is possible to create all values in the range $1-10^8$. If we have the array $B$, how to get the solution for an arbitrary target? Tried with a combination of backtracking and meet-in-the-middle but couldn't just get it to pass :-(
•  » » 4 years ago, # ^ | ← Rev. 3 →   +18 In $E$ if you write numbers in base $7$, you need all powers of $7$ + numbers $2, 3 \cdots 6$ ($1$ is already included in the set and $0$ is not important). That is close to the answer (you have a few more numbers). But you can notice that $-1 = 6$ ($mod$ $7$), $-2 = 5$ and $-3 = 4$. So you do not need numbers $4, 5, 6$.
•  » » » 4 years ago, # ^ |   +8 That's very neat and elegant. Thanks, finally upsolved. Did anyone solve using a different idea?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +10 Using numbers $3^0, 3^1, \dots, 3^8$ and only addition and subtraction, you can create all numbers in range $\left[ -\frac{3^9-1}{2}, \frac{3^9-1}{2}\right]$ where $\frac{3^9 - 1}{2} = 9841$.Now, take $M = 9000$ and write the input number $A$ as $a \cdot 2M + b$, where $0 \le a \le M$, $-M \le b \le M$ (it's surely possible for all integers not exceeding $2M^2 > 10^8$). Both $a$ and $b$ can be written as the sum of $3^i$'s, each scaled by $+1$, $0$ or $-1$.Therefore, each $3^i$ in the expression $a \cdot 2M + b$ is scaled by one of these numbers: $2M + 1, 2M, 2M-1, 1, 0, -1, -(2M-1), -2M, -(2M+1)$. Add $2M-1, 2M, 2M+1$ to the set (now it has $12$ elements), and now we can write each number as $(\text{some powers}) + (2M-1)(\text{some powers}) + (2M)(\text{some powers}) + (2M+1)(\text{some powers})$, where each $3^i$ occurs at most once. We need to take some care to avoid unary operators, but it's rather straightforward, even though a bit messy.
•  » » » » » 4 years ago, # ^ |   0 Thank you for sharing your approach mnbvmar, it's similar to the author's solution explained above but with base $3$ and a meet-in-the-middle kinda twist since we don't have all the powers of $3$ to make $10^8$.
•  » » » » 4 years ago, # ^ |   -7 If I didn't make mistake, Um_nik team got AC with some randomization for choosing $12$ elements (I do not know details). During preparation process I noticed that you can make nearly all elements with random array $B$, and that was reason to put bigger constraints like $10^8$. Probably $10^{12}$ would be enough to prevent all such solution, but I decided for this constraints as it was task for high school regional contest in our country (also randomized solution wouldn't pass there as I put smaller time limit $0.3$ sec — Um_nik code works for $0.56$).
•  » » » » » 4 years ago, # ^ |   0 Yup this is the one. Very interested to know more about this solution. How to check efficiently with a randomized or predetermined set of elements whether we can make a target number or not? Perhaps if Um_nik would be kind enough to share their approach.
•  » » » » » 4 years ago, # ^ |   +8 For fixed set of $m$ numbers we can find all the numbers we can generate by subset dp: let's just store all the numbers we can generate for given mask in a set. To make transitions we will try all the possible last operations, ways to divide numbers into left and right operands, and what are the left and right operands (they have to be build from the corresponding numbers). This works in reasonable time for $m \le 6$ (we can give some bounds like $O(4^{m} m!)$ but it is smaller on practice so it is better to run the code and figure out the bound yourself).So let's choose two random sets of $m=6$ numbers, run this dp for them independently, and then try to construct all the numbers in the input from two halves: one from the first set and the other from the second set.This is actually the slowest part of the solution, I had to write two-pointers here.
•  » » » » » » 4 years ago, # ^ |   0 Thanks so much Um_nik. This is exactly what I tried, but proved to be too slow. Two questions: How did you attempt to construct the numbers from the two halves? Surely we can't run the DP on them again. Or was it more like take a number from the first half, take one from the second, and see if we can make the target using a single operation ($+, -, *$)? This is what I tried. How did you pick these random sets? I tried to find the solution using a predetermined set of numbers and dividing them into to halves which I tweaked manually. Most of the time it was unable to yield a solution so I gave up on that eventually. BTW, backtracking works pretty nicely for $m=6$ or $m=7$, no need for subset DP.
•  » » » » » » » 4 years ago, # ^ |   0 Yeah, we just take two numbers constructed as some expressions from the two halves and try $(+, -)$ in both orders. We didn't use $\cdot$ because we could get numbers up to $10^{18}$ and their product will overflow.We random sets at random :) just 12 random numbers from $[1, 1000]$. If we couldn't construct all the numbers from input, just try again with different random numbers. Not sure if that happened on tests though. I can't say that it works magic, sometimes we can construct 10000 out of 10000 random numbers, sometimes not even 50%.To speedup we have replaced sets with vectors (now you have to sort and unique manually).
•  » » » » » » » » 4 years ago, # ^ |   0 Thanks, I did exactly the same thing and looks like had a silly bug in the merge method where local variable was overriding the global one :-(Fixed the bug and got accepted in 0.6 seconds with backtracking. Didn't require anything fancy to merge the two halves, just std::map
 » 4 years ago, # |   +208 The quality of most problems of GP of Serbia is comparable with GP of Siberia.
 » 4 years ago, # |   +13 How to solve L?
•  » » 4 years ago, # ^ |   +16 Let's ignore modulo. Let $steps[i][j][l]$ ($i \leq 18; j,l \leq 9$) be the minimum number of steps to come from $j \cdot 10^i + l$ to some $x$ such that $x \geq (j+1) \cdot 10^i$ and $where[i][j][l]$ be this $x$. Ignore states where $j=l=0$. For $i=1$ just simulate. To calculate these values for some greater $i$ you just need to know these values for $i-1$ (you perform $10$ such "jumps" for each state).With these precalculations, you can move from any value to something not less than modulo in no more than $\log_{10}(mod) \cdot 10$ jumps. The problem is when for example you have to do $10^{18}$ steps and $mod=10^9$. To optimize it you can notice that each time after jumping over modulo you will go through some number which is less than $10$ (so you'll find a period quickly). Knowing the period you can skip several cycles and then just simulate till the end.Worth mentioning: to simulate the process you should always try to make the biggest jump possible so that you won't run out of moves and won't exceed modulo too much. Also, notice that if $j$ would be greater than $9$ in the above definitions, then the simulation would go exactly the same if we replace $j$ with the greatest digit in $j$.
 » 4 years ago, # |   +50 Thanks for interesting memory limit challenges! Really love this stuff!
•  » » 4 years ago, # ^ |   +8 Which problem are you talking about?
•  » » » 4 years ago, # ^ |   +10 I and K. In I it's impossible to memorize all edges. In K I had to write solution with $O(n \sqrt{n\log{n}})$ complexity instead of $O(n \log^2{n})$ because of the small memory limit.
•  » » » » 4 years ago, # ^ |   +8 Huh? Did you implement a two-dimensional segment tree instead of binarysearching the prefix?
•  » » » » » 4 years ago, # ^ |   0 Yep, now I see what you are talking about :)
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +28 Bad luck, Polish mafia is protecting us ;)
•  » » » » » » 4 years ago, # ^ |   0 Everybody sometimes overkills something
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 What solution in K do you have in mind? We had $O(n\log^2 n)$ time, $O(n)$ memory and it fits within 8MB (with ML=128MB).
•  » » » » 4 years ago, # ^ |   +3 Thanks for your interesting solutions! Really love this stuff!
 » 4 years ago, # |   -6 Fact that F got less accepts than very messy ifology in D or rather tedious L means that people are really terrible at geometry, cause this was implementable in <10 minutes and hard to make a bug in.Here is my clean code that got accepted right after compiling it: https://ideone.com/KkyBzb (look at main only)
•  » » 4 years ago, # ^ |   0 I find the fact that the answer is on one of the axises (what is the right way to say this?) is pretty hard to prove.
•  » » » 4 years ago, # ^ |   +18 It was rather obvious to me. Maybe you got some different proof, so I will tell mine. Let's join center of rotation with the unique furthest vertex (since that one determines the radius). Then if you replace that center of rotation with the closer intersection with two segments joining midpoints of opposite sides of rectangle then the resulting disk will be strictly contained in the original one.
•  » » » » 4 years ago, # ^ |   +23 Same proof, different attitude.
•  » » 4 years ago, # ^ |   +10 Also L is pretty easy to write: https://ideone.com/NkhclYSo its more of a taste issue.
•  » » 4 years ago, # ^ |   +10 Maybe another reason could be the fact that the tests on the paper were very weak in general throughout this contest, and this problem in particular (which had some not-so-easy concepts like circles and rotations around a point) was particularly hard to reason about, especially due to the fact that it had no explanations and no figures whatsoever.Ok, you were lucky and your code got accepted on the first try. My code, for example, gives out answer 3 instead of 2 on the sample. I understand that maybe at higher conding skills this may not happen, but at this point, with my solution not passing the sample, I am literally clueless as to what are the next steps, without a clear explaination of the sample test case or a figure at least. I predict at least one hour of debugging on paper with a lot of poorly drawn circles and cartesian coordinate systems awaits me.
•  » » » 4 years ago, # ^ |   0 I see, that makes sense. However you can always try reading the code in such cases, I reckon it's not a bad idea when the things happening in the problem are complicated, but the code itself is simple. Or maybe your solution is unnecessarily complicated, you can try reading my code in that case.
•  » » » » 4 years ago, # ^ |   +16 I guess that reading the code could work, although for me it has the potential of becoming quite frustrating and "hard to detach from" during a contest. I have read your code, and it seems to be the same idea. However, you were brave enough to use doubles in your code, which I almost always try to avoid, because I know very little about floating point precision. Most of the times it ends up being easier to make mistakes. However, it usually happens that, if I don't do that and I get WAs, at some point I find myself just adapting epsilons and mass-submitting. By the way, why does your solution handle well multiple events at the same time? (or, more specifically, at times where floating point precision might fail to compare them correctly)
•  » » » » » 4 years ago, # ^ |   -9 I can't imagine writing this solution in integers. Maybe fractions would somehow work (if that's what you had in mind), but that would be unnecessary complication in my opinion (at least for someone who is more or less aware how doubles work), cause I don't think this problem is vulnerable on precision errors.In order to compare correctly events at the same time I shift them by +-eps depending on order I want them to be considered in. That is, if I have some flag F1 that is active on interval [-inf, x] and some flag F2 that is active on interval [x, inf] for the same value of x, I put event "remove F1 at x+eps" and "add F2 at x-eps". (Maybe I worded it a bit awkwardly, but in general you can always add c*eps to points where c is their "priority" — the lower c the earlier you want to consider it in case of equal x values)
•  » » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 I did too: https://ideone.com/RPXYbK.BTW, I don't understand why author make $A, B$ even while we can multiply all coordinates by $2$. It somehow suggests solution. First time, I guess center :)
•  » » » » » » » 4 years ago, # ^ |   0 Exactly, I had exactly the same thought that making A and B even was a bit weird xD
•  » » » » » » 4 years ago, # ^ |   +211 I can't imagine writing this solution in floating-point arithmetic. Maybe long doubles would somehow work (if the test data is weak), but that would be unnecessary assumption in my opinion (at least for someone who is more or less aware how doubles work), cause I don't think this problem is safe against precision errors.Input: 2 1953946 5000000 5000000 10000000 1 3388677 9868131 1380923 Your output: 1 Correct output: 0 
•  » » » » » » » 4 years ago, # ^ |   +26 Nice! That I guess was the well deserved and much needed blow to my overconfidence in that topic :). Sorry bicsi :P. To defend myself a little bit, I can say that if I change the epsilon to 1e-15 then it gives 0 and it still gives AC on Yandex, but of course I can see why it is not very convincing at this point :P. It seems I was lucky that tests were not prepared by you or mnbvmar. Let me analyze that test and possible precision errors and see what conclusions I will get to.
•  » » » » » » » 4 years ago, # ^ |   +29
 » 4 years ago, # |   +20 How to solve D cleanly, without a dozen cases in the code or the proof? I can't see it, but maybe I'm missing something.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 I believe people from November MW know why we put that name for the task :)Generally official solution has a lot of cases too.
•  » » » 4 years ago, # ^ |   0 Problem about JAGs can be solved without any case analysis, btw
•  » » » 4 years ago, # ^ |   +8 Ah, was it that there was some shite task with concatenating many short strings with JAG in its name which contained a lot of cases and here it contains a lot of cases as well, hence the connection xD?
•  » » » » 4 years ago, # ^ |   0 Yeah that was our connection xD Anyway 300iq mentioned now that there is some other solution.
 » 4 years ago, # |   +11 How to solve B?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +26 Just do 2D sparse table — $dp[x][y][z]$ is the MST taking the rectangle with corners $(x, y)$ and $(x + 2^{z} - 1, y + 2^{z} - 1)$. The restriction from the statement allows you to use $O(1)$ sparse table values answering a query, having $O(R \cdot C \cdot log(R) \cdot N) + O(Q \cdot N)$
•  » » » 4 years ago, # ^ |   +5 Can you please elaborate on how to merge values of MST taking smaller rectangles to get values of MST taking larger rectangles?
•  » » » » 4 years ago, # ^ |   +18 Well, you just take $4$ rectangles with twice smaller sizes that constitute our rectangle and just do it naively in $O(n)$ with DSU :)
•  » » » 4 years ago, # ^ |   0 I manage to fit normal 2D-RMQ $O(R\cdot C\cdot log(R)\cdot log(C))$ in both memory and timelimit :)
 » 4 years ago, # |   +13 How to solve A?
•  » » 4 years ago, # ^ |   +8 Answer always exists. Let's make recursive function $rec(n, k, x, y)$ that gives construction for parametres described in the task where position of the first element is $y$. There are two options:$k \geq n$ — then we put one element at position $y$ and call $rec(n-1, k - n + 1, x, y + x)$$k < n$ — then we put one element at position $y$, $k$ elements at position $y + x$ and rest $n - k - 1$ elements at position $y + x - 1$ and stop with recursion (our $k$ will be $0$).Note that second case will happen before $n$ becomes $0$.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 Thank you so much, I got it.
•  » » 4 years ago, # ^ |   +8 Another solution — answer always exists even if we just divide all numbers in 4 groups — a 1s, b 2s, c (x + 1)s and then d numbers which are all at distance x from each other and from numbers from first 3 groups (i. e. 2x + 1, 3x + 1, ...). Also you will find answer very quickly despite seemingly cubic complexity
•  » » » 4 years ago, # ^ |   0 haha yeah, you are right. Thank you.
 » 4 years ago, # |   +66 Any real reason to have 64/128 mb memory limits in 2020?
•  » » 4 years ago, # ^ | ← Rev. 3 →   -7 Most of the tasks are not from 2020 :) I agree that we should make better memory limits for the problems, but we had convention of taking all data/constraints/limits from original setters and testers — we rewrote only needed stuffs before Baytdance round and fixed some bugs after noticing it during camp. Time limits are usually twice bigger than official solution in C++ (just for $B$ we put $5$ sec and official works for $2.9$ sec).
•  » » » 4 years ago, # ^ |   +20 Errichto, please explain these guys how to set proper TLs
•  » » » 4 years ago, # ^ |   +37 You know that apparently there are some other programming languages besides C++?
•  » » » » 4 years ago, # ^ |   +8 Ok, maybe I didn't explain well about time limits. All time limits (except problem $B$ that I have described already) are $2 \cdot original limits$ rounded up, decided by snarknews as we put original TLs at the beginning.I was setter for $3-4$ platforms, and all of them had different time limit for Python and Java codes (usually twice bigger). Simply we couldn't know that is not case here, as we are using Java only for university GUI projects and we got corresponding logins for e-judge and Yandex both $<24h$ before contests.
 » 4 years ago, # |   +26 Is there a link to the problems that is (and is allowed to be) open to the world? I was just curious what the problems were.