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?

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | Radewoosh | 3464 |

3 | V--o_o--V | 3338 |

4 | Um_nik | 3307 |

5 | Petr | 3297 |

6 | ecnerwala | 3282 |

7 | LHiC | 3266 |

8 | wxhtxdy | 3264 |

9 | Vn_nV | 3182 |

10 | xyz111 | 3147 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 176 |

3 | neal | 158 |

3 | Ashishgup | 158 |

5 | Petr | 157 |

5 | PikMike | 157 |

7 | majk | 156 |

7 | rng_58 | 156 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

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?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/16/2019 14:23:24 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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(Qlog^{2}(N)) time andO(Q^{2}) memory?(orO(Qlog^{3}(N)) time andO(QlogQ) memory).What about problem A? On the analysis after the contest nobody explained how it should be solved.

That is fun, in Romania, we don’t even have analysis after the contest.

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

Will the 2d segment tree use

O(QlogQ) memory? We used 2D Fenwick Tree based on maps to make it haveO(QlogQ) memory.Coordinates compression and Fenwick trees in the nodes of Segment Tree as a standard approach.

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).

I tried doing this in the gym and apparently it's not nearly fast enough

I tried what RomaWhite wrote, and my solution got AC in 1 sec.

Well, I can't compete with you when it comes to writing constant-optimized code :)

Well, it's not hard =) Other AC submissions use some D&C approach, and it works much faster.

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 ofAandBis 3, 12, 13, 2 (big endian). I have no idea how to complete the solution though.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.

Thanks!

I created an interactive standings with unfrozen results. You can find it here: http://acmallukrainian.ho.ua/2018/3/standings.html

Is there any place for virtual participation? Seems a challenging set of problems.

Also is there a place where can find the problem statements?

Problem statements can be found here.

I'll be glad to help with publishing it in Gym. Do you know a person to contact about it?

freak93 klamathix eudanip, maybe they can help

Any update on this? I would love to write this contest as a training.

Here.

Thanks! It would be cool to add official results. Is any detailed standings table in HTML?

What about this? http://acmallukrainian.ho.ua/2018/3/standings.html

Thanks! I've uploaded it.

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

For those who understand Ukrainian, there are our comments on problems and their solutions here.

neal will be surprised.

Problem J

This 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').

I got AC on J after reading this. It will be better to modify the description of J.

Shit, maybe our team didn't advance to WF because of that

Magic of high-level preparation of SEERC. As always.

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.

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.

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.

I don't get your example. If we are in

Xand we haveY≠W(whereWis the next vertex fromXin our original path anddist(X,Y) +dist(Y,N) <dist(X,W) +dist(W,N)), then we should outputX, and it doesn't matter if we haveZor not. In other words, you don't cheat when you are in vertexY, you cheat when you start to go to vertexY(which means you are in vertexXand onlyXshould be printed).YorZcan't be printed in answer (no matter what), because they are not part of the original path.Let

denote shortest distance fromdist(A, B)AtoB.Let

denote the distance in the given path fromdist1(A, B)AtoB.Let

denote the weight of the edge fromW(A, B)AtoBfor rabbit.Currently we are at

X. Next vertex in the path isY. LetZ(!=Y) be some other vertex adjacent toX.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 is

W(X, Z) + dist(Z, N) < W(X, Y) + dist(Y, N)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.Any hints for G and H?

If I am not mistaken, for H, you could randomly partition the persons in two parts (

LandR) and satisfy every wish (x,y) with and . The expected value for that isM/ 4. If you get AC with that, notify me.I solved it like that during the contest, got AC on the first try

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 2

^{10}× 2^{10}, there are at most 2^{20}different matrix, which should be ok. If you see a matrix as a binary number, you can say to_number(M) =row_{0}(M) +row_{1}(M) + ... +row_{n}(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 .. 2

^{20}) 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 2

^{20}× 2^{20}, 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 2^{10}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 2

^{10}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 10

^{6}queries, and each query costs 2^{10}~ 10^{3}, 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 2

^{10}× 2^{10}with these queries, so maybe you could do something more lazy with memoization.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 isstrictly largerthan 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

morethan m/4 edges go from red to green vertices, ormorethan m/4 edges go the other way around.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).