### Sin's blog

By Sin, history, 3 months ago, ,

SEERC 2018 is finished now, and I’d like to know impressions of other contestants. Especially, what happend to the team with +40 on problem E? And how it was organized in Ukraine?

•
• +65
•

 » 3 months ago, # | ← Rev. 3 →   0 That was not a really productive contest for our team, but it was rather fun(we spent most of the time on the unsolved task K:).By the way, does anybody have a better solution than O(Qlog2(N)) time and O(Q2) memory?(or O(Qlog3(N)) time and O(QlogQ) memory).What about problem A? On the analysis after the contest nobody explained how it should be solved.
•  » » 3 months ago, # ^ |   0 That is fun, in Romania, we don’t even have analysis after the contest.
•  » » 3 months ago, # ^ |   +2 time and memory. You can count points inside rectangle with 2d Segment Tree. And to count rectangles that contain the point, count rectangles that don't contain the point. Like an inclusion-exclusion, with 4 simple ST and 4 2D ST
•  » » » 3 months ago, # ^ |   +3 Will the 2d segment tree use O(QlogQ) memory? We used 2D Fenwick Tree based on maps to make it have O(QlogQ) memory.
•  » » » » 3 months ago, # ^ |   0 Coordinates compression and Fenwick trees in the nodes of Segment Tree as a standard approach.
•  » » » 3 months ago, # ^ |   +10 Second part could be done using the same method. Add rectangle = add 1 to points (x1,y1), (x2,y2) and -1 to (x1,y2), (x2,y1). All coordinates are  ± 1 of correct ones :)Query point = find sum in rectangle (0,0,x,y).
•  » » » 3 months ago, # ^ |   0 I tried doing this in the gym and apparently it's not nearly fast enough
•  » » » » 3 months ago, # ^ |   0 I tried what RomaWhite wrote, and my solution got AC in 1 sec.
•  » » » » » 3 months ago, # ^ |   +18 Well, I can't compete with you when it comes to writing constant-optimized code :)
•  » » » » » » 3 months ago, # ^ |   0 Well, it's not hard =) Other AC submissions use some D&C approach, and it works much faster.
•  » » 3 months ago, # ^ |   0 My friend biza suggested an interesting idea for problem A: Try all bitmasks representing positions where a carry will happen during addition of two numbers. For example, if we have A + B = 4332 and the carry mask is 0110, the actual digit-wise sum of A and B is 3, 12, 13, 2 (big endian). I have no idea how to complete the solution though.
•  » » » 3 months ago, # ^ |   +10 Iterate over the lengths of palindromes.If it's equal, digits are independent and we can find a number of ways to create each digit and the answer is a product of those numbers. In such case, we can iterate over carry mask of lower 9 digits (but still 2^18 should be ok).If palindromes have different lengths, we know the largest digit of a longer palindrome -> we know its smallest digit -> we know the smallest digit of shorter palindrome -> mirror this digit in smaller palindrome and find next digit in larger one. We could restore all digits of both palindromes using such process. Also, we can iterate over carry mask of only higher 9 digits.
•  » » » » 3 months ago, # ^ |   0 Thanks!
 » 3 months ago, # |   +39 I created an interactive standings with unfrozen results. You can find it here: http://acmallukrainian.ho.ua/2018/3/standings.html
 » 3 months ago, # |   +13 Is there any place for virtual participation? Seems a challenging set of problems.
•  » » 3 months ago, # ^ |   +15 Also is there a place where can find the problem statements?
•  » » » 3 months ago, # ^ |   +18 Problem statements can be found here.
•  » » 3 months ago, # ^ |   +22 I'll be glad to help with publishing it in Gym. Do you know a person to contact about it?
•  » » » 3 months ago, # ^ |   0 freak93 klamathix eudanip, maybe they can help
•  » » » » 3 months ago, # ^ |   +10 Any update on this? I would love to write this contest as a training.
•  » » » » » 3 months ago, # ^ |   +54 Here.
•  » » » » » » 3 months ago, # ^ |   0 Thanks! It would be cool to add official results. Is any detailed standings table in HTML?
•  » » » » » » » 3 months ago, # ^ |   +12 What about this? http://acmallukrainian.ho.ua/2018/3/standings.html
•  » » » » » » » » 3 months ago, # ^ |   +14 Thanks! I've uploaded it.
 » 3 months ago, # | ← Rev. 2 →   +15 Team which got 40 penalty attempts solved it with some kind of segment tree and it wasn't fast enough, so they optimized it. Computers switched off two times during the contest so our team lost ten minutes of computer time. In my opinion all problems were nice, except of problem J. It is too straightforward and required only careful coding
 » 3 months ago, # |   +29 For those who understand Ukrainian, there are our comments on problems and their solutions here.
 » 3 months ago, # | ← Rev. 2 →   +33 Time Limit: 0.3 seconds (C/C++) Time Limit: 0.2 seconds (C/C++) Time Limit: 0.1 seconds (C/C++) Time Limit: 0.4 seconds (C/C++) Time Limit: 0.5 seconds (C/C++) Time Limit: 0.4 seconds (C/C++) Time Limit: 1.5 seconds (C/C++) Time Limit: 0.4 seconds (C/C++) Time Limit: 0.1 seconds (C/C++) Time Limit: 0.4 seconds (C/C++) Time Limit: 2 seconds (C/C++) 
 » 3 months ago, # |   +19 Problem JThis line in the problem — "The rabbit is considered to cheat ONLY if he changes the direction of the path and the new path that he will take is strictly faster than the original one (otherwise, there is no point to cheat)" is wrong.The phrase 'original one' is quite ambiguous. It doesn't mean the original path, but means the next vertex in the original path (then the rabbit can cheat, i.e, take the shortest path to 'n').
•  » » 3 months ago, # ^ |   +11 I got AC on J after reading this. It will be better to modify the description of J.
•  » » 3 months ago, # ^ |   +26 Shit, maybe our team didn't advance to WF because of that
•  » » » 3 months ago, # ^ |   +1 Magic of high-level preparation of SEERC. As always.
•  » » » 3 months ago, # ^ |   +8 Mmm, very nice... Just compare our submissions in the middle of contest 45114699 and correct one 45114786. The statement is really horrible as for me.
•  » » 3 months ago, # ^ |   +20 I disagree here. Put yourself in place of that rabbit and turtle. If you are standing in vertex X and your next vertex is Y and if you want to cheat in vertex X but the fastest way from X is to go to Y, then it's not really cheating (not for turtle), because turtle can't understand by your move if you're starting to cheat or not.
•  » » » 3 months ago, # ^ |   0 Take this scenario -There is a vertex Z (!= Y), such that the shortest distance from X to 'n' is through Z and is equal to D. Also, the distance of X-Y + shortest distance from Y to 'n' = D. The distance from X to 'n' in the original path is greater than D. This distance is strictly less than the distance of the 'original one' (original path). But we aren't considering this path (from Z) because we can cheat on Y. This is not mentioned in the statement. For you, 'original one' is implying direction, but for most of the others, it is implying the original path. That is why I am saying that statement is ambiguous.
•  » » » » 3 months ago, # ^ |   0 I don't get your example. If we are in X and we have Y ≠ W (where W is the next vertex from X in our original path and dist(X, Y) + dist(Y, N) < dist(X, W) + dist(W, N)), then we should output X, and it doesn't matter if we have Z or not. In other words, you don't cheat when you are in vertex Y, you cheat when you start to go to vertex Y (which means you are in vertex X and only X should be printed).Y or Z can't be printed in answer (no matter what), because they are not part of the original path.
•  » » » » » 3 months ago, # ^ |   0 Let dist(A, B) denote shortest distance from A to B.Let dist1(A, B) denote the distance in the given path from A to B.Let W(A, B) denote the weight of the edge from A to B for rabbit. Currently we are at X. Next vertex in the path is Y. Let Z (!= Y) be some other vertex adjacent to X.According to the statement in the problem, the below equation should be true for us to cheat on X (ignoring the condition for turtle for now)W(X, Z) + dist(Z, N) < W(X, Y) + dist1(Y, N)But the equation they wanted isW(X, Z) + dist(Z, N) < W(X, Y) + dist(Y, N)
•  » » » » » » 3 months ago, # ^ | ← Rev. 4 →   0 Well, okay, now I get your example. Maybe you're right, but I remember in the contest I used the "final moment when the rabbit will finish if he doesn't cheat" to check if I can cheat from current vertex.
 » 2 months ago, # | ← Rev. 2 →   0 Any hints for G and H?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +24 If I am not mistaken, for H, you could randomly partition the persons in two parts (L and R) and satisfy every wish (x, y) with and . The expected value for that is M / 4. If you get AC with that, notify me.
•  » » » 2 months ago, # ^ |   +8 I solved it like that during the contest, got AC on the first try
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 UPD: just realized this is very much wrong, skip it.I have this idea for G, I haven't tested it though and I'm not sure it'll pass (the complexity is quite large), it's based on meet in the middle.So, you can preprocess the value for each matrix of size at most 210 × 210, there are at most 220 different matrix, which should be ok. If you see a matrix as a binary number, you can say to_number(M) = row0(M) + row1(M) + ... + rown(M), where + is the concatenetion as if they were lists. And, in a similar way, you can take the four submatrices out of a number (I think this is more tricky, but should be doable in around 20 steps).Now, to precalculate val(to_number(M)), you'll go through every number x in [0 .. 220) in order, and you split the matrix represented by x in the four submatrices, we can check that the given numbers of the submatrices must be smaller than x, then, their value is already stored.Now that we have this, we build a 4-ary tree, where each node is a matrix, and it's four children are the submatrices. Then, if you need to represent the matrix of size 220 × 220, you'll have a complete 4-ary tree with depth equal to 10, and each leaf will have a number which represents the matrix of size 210 that's there (for which you already have the value calculated).Now, for each query, you traverse the tree, and in each step you only go through 2 of the 4 children, because of how the queries are, so you'll end up in 210 leafs and need to change their value, when you go up, you update each node's value. In here you'd need to check if some submatrix becomes all white or all black.Now, since we have 106 queries, and each query costs 210 ~ 103, this is really slow (and huge on memory consumption), so maybe there's a better solution out there. Or a better setting of the values.As an observation, when you represent each matrix, you actaully have that rotate or negate a matrix doesn't change it's value, so, you could save some memory on the first step and have a larger amount of preprocessed matrices.As a second observation, I don't think you can build every matrix of size 210 × 210 with these queries, so maybe you could do something more lazy with memoization.
•  » » 2 months ago, # ^ |   +13 A constructive algorithm for H: let's first solve a problem where you're given an undirected (multi)graph with m edges, and you're to color the vertices of the graph in two colors (say, red and green) so that the number of edges joining the vertices of different colors is strictly larger than m/2.How to do it? First take any two connected vertices, and color them complementarily. Then color the vertices one by one; when deciding on a color of a single vertex, we count the number of its red- and green-colored neighbors (possibly counting some multiple times in case of multiedges) and use the color that occurred fewer times. We can easily prove that this process gives us strictly more than m/2 "good" edges.Back to our problem: temporarily make the graph undirected (by simply purging the directions from the edges), take the coloring from the subproblem above, and restore the original directions to the edges. Notice now that either more than m/4 edges go from red to green vertices, or more than m/4 edges go the other way around.
 » 2 months ago, # |   +24 Problem G: Matrix Queries is exactly same as JOI SP 2013: Collecting Images is Fun. I believe this is not a coincidence. That's sad.. and funny too.I uploaded a translated version here, some months ago. You can find the editorial in JOI Site (In Japanese).