ICPCNews's blog

By ICPCNews, 3 months ago,

Hello, Codeforces!

The ICPC World Finals Dhaka will begin on November 10, 2022 at 11:00 (UTC+6). This is the culmination of the 2020-2021 ICPC season, and we have over 130 teams competing for the title of ICPC champion. Please join us on the live broadcast for the main event of the year in competitive programming; commentators will include ecnerwala, SecondThread, Egor, and more! There will also be a live mirror for you to solve the problems alongside the contestants!

MAIN RU AR ES PT ID ZH Split screen

Good luck to all teams competing!

• +518

 » 3 months ago, # |   +101 See you guys on stream!
•  » » 3 months ago, # ^ |   +30 Good luck, have fun to everyone competing, and good morning to everyone watching from home!
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +7 Sir, I had seen live cast of ICPC world final which was casting SecondThread & ecnerwala . I am a man in bangladesh. Bangladesh is host for arranging the icpc world final 2022 as first time. I am so proud for this reason. Thank you so much all the members of icpc officials. #icpcwfdhaka
 » 3 months ago, # |   +13 I've just registered on judge.icpc.global. Is it correct that only one of a team needs to create an account, and then all teammates will use it to submit (we are not in the same place)? If so, then the "Full name (optional)" during registration kinda confuses
 » 3 months ago, # |   +161 Is it rated?
•  » » 3 months ago, # ^ |   +23 It is the first time I found "is it rated" upvoted.
 » 3 months ago, # |   -98 Codeforces Language Picker -- chrome extension to fix codeforces language picker.Note: In 2022 Apple’s macOS, Monterey, has removed one of the longest and most prominent examples of using flags for languages (flags were used since 2001). Codeforces should do it too.
 » 3 months ago, # |   +59 Are Petr, tourist and Endagorion going to participate unofficially this year?
•  » » 3 months ago, # ^ |   +3 Hope tourist will come !
 » 3 months ago, # |   +28 I think the timeanddate link may not be set properly. It links to 11:00 UTC, not 11:00 UTC+6.
•  » » 3 months ago, # ^ |   0 Fixed, thanks!
 » 3 months ago, # |   +28 How can I participate the mirror . Why it said "There's no active contest for you (yet)." ?
•  » » 3 months ago, # ^ |   +18 Fixed now!
 » 3 months ago, # |   +3 Good Luck to every participant TEAM (◠‿◠)
 » 3 months ago, # |   0 LETS GO WATERLOO! LETS MAKE IT HAPPEN GUYS! — volcano
 » 3 months ago, # |   0 wow！ good wf stream ,ovo
 » 3 months ago, # |   +6 Is the mirror half hour later than offcial contest ?
 » 3 months ago, # |   0 Good luck to all participating teams
 » 3 months ago, # |   +57 When the problemset will be available?
•  » » 3 months ago, # ^ |   +27 Here is the problemset of ICPC WF 2021.
 » 3 months ago, # |   +69 Why the mirror is delayed ?
 » 3 months ago, # |   +10 Has the mirror started?
•  » » 3 months ago, # ^ |   -47 Mirrors are wave reflectors they can't start idiot
•  » » » 3 months ago, # ^ |   +20 OMG, you are so crazy
 » 3 months ago, # | ← Rev. 2 →   +13 It seems that the translation is dead.Also looking forward to seeing the statements very much.
•  » » 3 months ago, # ^ |   -20 OMG, you are so crazy
•  » » 3 months ago, # ^ |   +12 it's called "stream" https://www.merriam-webster.com/dictionary/translation the word "translation" has no meaning related to the streams
•  » » » 3 months ago, # ^ |   +8 Thank you. I was too lazy to find the appropriate word.
•  » » » » 3 months ago, # ^ |   +20 I was completely bamboozled what you mean xD
 » 3 months ago, # |   +13 How much is the mirror delayed?
•  » » 3 months ago, # ^ |   -41 who asked?
•  » » » 3 months ago, # ^ |   +24
 » 3 months ago, # |   0 When will the mirror be ok?
•  » » 3 months ago, # ^ |   -11 It's always ok, but you need to register first.
 » 3 months ago, # |   0 Where can I get the problems?
•  » » 3 months ago, # ^ |   0 https://judge.icpc.global/team/problems, remember to register and login.
 » 3 months ago, # |   +10 Will there be mirror scoreboard?
 » 3 months ago, # |   +28 This problem is same as problem H: https://atcoder.jp/contests/abc167/tasks/abc167_f?lang=en
•  » » 3 months ago, # ^ |   0 Haha, I prepared it in 2017, and I'm sure there are earlier versions. Btw tests on Atcoder are weak.
•  » » » 3 months ago, # ^ |   +10 Isn't that equivalent to L: swap space from ICPC World Finals 2016? Looks exactly the same modulo a different story
•  » » » » 3 months ago, # ^ |   0 Yes, they are similar. A 'sort with correct comparator' problem. Also similar to this e-maxx article (in Russian). And I also prepared this and this which are similar too. A lot of clones exist.
•  » » » 3 months ago, # ^ |   0 a slightly harder version from PTZ-2009
 » 3 months ago, # |   -35 Впервые за много лет у России ни одного золота, мда
 » 3 months ago, # |   0 Why do they live split screen while frozen time ? the result of submissions may be leaked on contestant's screen.
•  » » 3 months ago, # ^ |   +10 I think they intend to do so.
 » 3 months ago, # | ← Rev. 2 →   +108 Results which I reversed engineered from split screen. Feel free to comment if there are any errors. Scoreboard
 » 3 months ago, # |   +8 Good Luck For Everyone:)
 » 3 months ago, # |   -33 why do i keep geting internal server error you fucking bitches
 » 3 months ago, # |   0 Is the contest over?
 » 3 months ago, # | ← Rev. 3 →   +11 Who is owner of zibada.guru/finals? Is it zibada?Could you help change 3rd member of "University of Engineering and Technology — VNU" on the website from SeehtEntity to Negativez2? This is the first Vietnamese team to (maybe, based on results shared here) ever win a medal, so I just hope their members are correct.
•  » » 3 months ago, # ^ |   +15 fixed :)
•  » » » 3 months ago, # ^ |   0 Thank you! And thanks for the great website!
 » 3 months ago, # |   +3 Problem G already was in XXII Open All-Siberian Programming Contest (2021), which also was a GP of Siberia
•  » » 3 months ago, # ^ |   +3 Okay, it's a bit harder with up to 100 colors though, we don't have time to check each color separately.
•  » » » 3 months ago, # ^ |   +18 Well,here we need to create 100 different units and assign them to the colors instead of two, but I guess you know the solution anyway.The point is, my prior knowledge of this problem reduced the time I needed to solve G to one (1) minute.
•  » » » 3 months ago, # ^ |   0 You only need log100 checks
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Hi Tutis how able to check in log100? I try a random solution like for each color contains same bit i (0 <= i < 6) than mark as 1, else mark 0. Don't know why it was passed G.
•  » » » » » 2 months ago, # ^ |   +1 You can solve for each colour bit independently and then AND the answers I think, idk what u are doing.
•  » » 3 months ago, # ^ | ← Rev. 2 →   -31 I tried to use bitsets with a size of $O(r_q c_q k)$ during the mirror. I knew I would fail
 » 3 months ago, # | ← Rev. 3 →   +226 Managed to solve problem D during the mirror contest. That was too insane :)
•  » » 3 months ago, # ^ |   0 wow, strong!
 » 3 months ago, # | ← Rev. 2 →   +42 Apparently NQ passes in B. We wasted 2h writing $O(N^2 + Q \log N)$ ;_;
•  » » 3 months ago, # ^ |   +29 Our nq solution TLEed, and we were not able to speed up our code.
•  » » » 3 months ago, # ^ |   +11 Yeah, TL seems stupid. A lot of teams report TL -> AC with $O(NQ)$
•  » » 3 months ago, # ^ |   +31 Yeah, we spent lots of time trying to end up with that time complexity and failed -- got so sad hearing that NQ passes.
•  » » 3 months ago, # ^ |   +10 We tried to time out $O(NQ)$, but unfortunately it looks like some optimized ones slipped by. Sorry! $O(N+QlogN)$ is possible, but we figured the problem was already extremely difficult; the graph was kept small so $O(N^2+QlogN)$ could pass.
•  » » » 3 months ago, # ^ |   +19 Thanks for the answer. However, I'll just claim that I highly dislike the problems in which you have no idea whether your proposed complexity will pass or not (one might say that's a part of CP tho). In case that you wanted to time out NQ and wanted to allow poly(N) + QlogN, can you kindly tell us what was the reasoning between not setting Q higher (1e6 order)? Thanks.
•  » » » » 3 months ago, # ^ |   +10 Note that I do not speak for the other judges, but yes, I also strongly prefer the challenge to be in finding the asymptotically correct solution, not optimizing constant factors on an easier algorithm.All else being equal, there are good reasons to try to keep problem time limits low — feedback is faster and there's less pressure on the judge system (especially in the worst case where somebody submits an almost-correct solution 40 times). But, as it turned out, all else was not equal; in hindsight, I would have been in favour of a higher Q and higher time limit.
•  » » » 3 months ago, # ^ |   +31 I looked at the constraints, thought "nq looks like it should pass", did not optimize anything and got AC with my first submit ¯\_(ツ)_/¯If you wanted to time out nq at least make the constraints so that it looks like it shouldn't pass. I was convinced I wrote intended solution instead of thinking I cheated my way through with some optimized bruteforce
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 We had to implement LCA with RMQ to squeeze $O(N^2 \log N + NQ)$ to pass, another 50 lines worth of code.And honestly I'm surprised that $O(NQ)$ is not intended, as NQ = 4e8, and the time constraint is 5 second. We have seen problems with more tight (time constraint)/(intended complexity) than 5s/4e8 operator
•  » » » 3 months ago, # ^ |   +11 Have you thought about just precalculating all possible lcas in O(n^2) :p?
•  » » » » 3 months ago, # ^ |   0 Somehow I completely forget that it's possible to compute LCA with arbitrary tree root in the same complexity as computing the LCA with tree rooted at fixed vertex (by doing some additional casework). Feel like a dumbass after the contest.
•  » » » » » 3 months ago, # ^ |   +11 Hm, maybe we have a bit different solution then, but I did not need to move the root around. Actually the only reason I had lca as to compute a meeting point of 3 vertices and that is $lca[a][b] \oplus lca[b][c] \oplus lca[c][a]$ (with an arbitrary root)
 » 3 months ago, # |   +29 Seems like the biggest predictor for success this contest was having Westin as your hotel, haha
 » 3 months ago, # |   0 how do we know the final ranking
•  » » 3 months ago, # ^ |   0 why scoreboard still frozen?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   0 They updated it now, thx
 » 3 months ago, # |   0 How to solve K?
 » 3 months ago, # |   0 Wow, exciting extra Problem: onsite&reallife tech problem~!
 » 3 months ago, # |   +57 Congratulations to fantasy!
•  » » 3 months ago, # ^ |   +46 And matthew99 and jerry, lol. Waiting for antontrygubO_o and TLE to beat this MIT result next year... oh wait
•  » » » 3 months ago, # ^ |   +43 I bet jiangly next year :)D
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 jiangly will probably win final, and his legend will continue by p_b_p_b and 137_345_2814!
 » 3 months ago, # |   +10 In the stream someone mentioned that some teams used Python :) And used successfully. The system at ICPC has different time limits for different languages? And will it be possible to check the solution of the teams later?
•  » » 3 months ago, # ^ |   +8 The time limit is the same for all languages; there's no guarantee that a Python solution exists that can run in time. But Python was a good fit for problem C (which was very mathy), so there were a lot of Python submissions for that one.
 » 3 months ago, # | ← Rev. 4 →   0 For problem C, don't we just need to ensure that (q^n-(q-p)^n)/p divides m? Getting a WA verdict on the judge... Edit: OK it seems that using t=(p^n-q^n)/(p-q) gives WA in python but using t=(p^n-q^n)//(p-q) gives AC... Why? (p^n-q^n) is divisible by (p-q) so it shouldn't have been a problem. I tried typecasting it to int too
 » 3 months ago, # | ← Rev. 8 →   +49 Why are there pictures of the other 11 medal teams on stage, but not any of us on the official ICPC news page?Did they not take any because I didn't immediately look at the camera? Or is it due to the masks? If so that's really sad :(EDIT: they have a picture up now :)
 » 3 months ago, # |   +13 Will there be an editorial released for the problemset?
•  » » 3 months ago, # ^ |   +44 Here are brief solutions to the problems I know: A: Crystal CrosswindLet's say that $f(x, y) = 1$ if there is a molecule there, otherwise $0$. Each wind direction $w$ essentially tells us that in some points $f(x, y) = 1$, $f(x - w_x, y - w_y) = 0$, and for all other pair of points that differ by vector $w$ we know that $f(x - w_x, y - w_y)\geq f(x, y)$. Therefore, in the end we have a graph (it may have $10^7$ edges, but we can store it in a compressed way). If for each valid inequality we add an edge $(x, y)\to(x + w_x, y + w_y)$, then we can propagate all guaranteed ones through the reverse edges and all guaranteed zeroes through the forward ones. Every unspecified cell in the end can be replaced by either zero or one. B: Dungeon CrawlerLet's root the graph by the vertex $s$. Then almost every edge must be passed through at least two times. More specifically, if we end in the vertex $f$, then all edges of the simple path between $s$ and $f$ must be traversed an odd number of times (some of them 1, some of them 3, depending on the lca and stuff), and all other edges must be traversed an even number of times (turns out, they can all be traversed exactly 2 times).We can group all queries by $s_i$ and handle all of the queries with fixed $s_i$ one after another, so that we don't need to reroot the tree. We can probably do something smart in $O(q\log{n} + n^2)$, but our team didn't need to.I have a feeling that this problem has a lot in common with this last year problem. C: Fair DivisionAfter every round, the profits are proportional to $(1, 1 - f, (1 - f)^2, \ldots, (1 - f)^{n-1})$, therefore, in the end they must be proportional to the same. If $1-f = p/q$, then we need to find such $p$ and $q$ that the value of $p^{n-1} + p^{n-2}q + \ldots + q^{n-1}$ divides $m$.Since $n\geq 6$, we don't need to try a lot of values, and all values can be computed in a naive way, without fancy geometric progression formulas. D: Guardians of the GalleryAs my teammate said, "generate all points, all rays through vertices, all perpendiculars, run something on them, the problem is finished".He was not very happy. G: Mosaic BrowsingFor each color $i$, create a unique complex number $w_i$ with $|w_i| = 1$. For the motif we create a polynomial from $\mathbb{C}[x, y]$ where "color" $0$ corresponds to the coefficient $0$, and color $i$ corresponds to coefficient $w_i$. For the mosaic we create a similar polynomial, but all the coefficients are reversed (so that $(i, j)$ corresponds to the coefficient of $x^{n-1-i}y^{m-1-j}$), and color $i$ corresponds to $w_i^{-1}$. Then when we multiply these polynomials (2d fft), we are interested in the coefficients equal to the number of nonzero colors in the motif (all other coefficients have absolute value strictly less). H: Prehistoric ProgramsSort all strings with nonnegative total balance in the decreasing order of minbalance. Then rotate all other strings by $180^{\circ}$, and do the same with them and concatenate them from the end. Why this works? Exercise for the reader. I: Spider WalkAdd bridges from the farthest from the center to the closest. Initially, the answers are like $\ldots, 3, 2, 1, 0, 1, 2, 3, \ldots$. Every time we add a bridge between $i$ and $i + 1$, let's say the answers for them were respectively $x$ and $y$. Then now the answers at most $y$ and $x$, and some of them are even less: while any two adjacent values differ by $2$, decrease the maximum of them by $1$. It is straightforward why these operations take sense. It is still not very difficult to prove that these operations are sufficient.So now the solution is: find $x$ and $y$. If they are equal, do nothing. Otherwise, let $y = x + 1$. If the new value before $y$ (which was before $x$ earlier) is $y - 2$, decrease $y$ by $1$. Then look at the maximal chain of type $(x + 2, x + 3, \ldots)$ after $x$ (earlier after $y$) and reduce it all by $1$. This can be done via segment tree. K: Take On MemeCalculate for every node the set of all points that can result in this node.Claim. For a set $S$, we don't need to consider any point inside the convex hull of $S$.After this we just calculate some Minkowski sums and then take convex hulls of their unions. The total size of all the convex hulls on each layer is about the size for the previous layer plus the size of the previous layer. Indeed, if $D$ is the set of all directions of sides of the children polygons $P_1$, \ldots, $P_k$, then the directions of any sum $\pm P_1 \pm P_2 \pm \ldots$ is also $D$. Then, when we take the convex hull of the union, probably we add at most $k$ new directions, idk. L: Where Am I?Run the naive iteration in $O(n^2m^2)$. If you don't allocate vectors every time and reuse the same memory, it will work fast enough.Author's solution also uses the fact that there only $k\leq 100$ markers, so each sequence of markers-non-markers can be encoded with a sequence of $k$ indices of markers.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -13 UPD: It will not pass time limitAlternative solution for problem $G$ with $z-function$ $(z-algorithm)$.Let's mosaic has $n$ rows and $m$ columns, and motif $n1$ rows, $m1$ columns. Let's make one-dimension array $a$ of size $n*m$ from mosaic concatenating it's rows and $c$ one-dimension array of size $n1*m$ from motif concatenating it's rows extended with $m-m1$ $0$. Now we need to find where $c$ is a substring of $a$ assuming $0$ can be any symbol — we can do it using slightly modified z-function.the only change will be in $while$ condition.s[z[i]] == s[i + z[i]] to s[z[i]] == 0 || s[z[i]] == s[i + z[i]]the full while (you can compare it to e-maxx code, which i took to modify):while (i + z[i] < n && (s[z[i]] == 0 || s[z[i]] == s[i + z[i]])) ++z[i];I have made some tests and it works. Correct me please, if it is wrong.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 It will work correct, but complexity will be $O((n \times m)^2)$
•  » » » » 3 months ago, # ^ |   0 It is very interesting solution, bro)
•  » » » 3 months ago, # ^ | ← Rev. 6 →   +26 For problem D, the guard first moves between the starting point and the vertices of the polygon and then heads to a location where half of the target can be seen.In the first part, it needs to check whether the segment connecting two points is fully inside the polygon (Airport Construction helps), and find the shortest path from the starting point to each of the vertices.In the second part, if the starting point or the vertices of the polygon can see the target, no more moves are needed from that point. Otherwise, it needs to straightly move to the closest point on the boundary of the target region, which consists of $O(n)$ segments. Some of the segments are on the boundary of the polygon and it is no need to consider such segments, and each of the others is on the ray from the target heading to a vertex of the polygon, which may be considered as connecting the target and the farthest intersection between each edge and the ray that can see the target. Checking whether a point can see the target is straightforward based on checking the segment inside the polygon. Don't forget to check whether the "straightly move" is fully inside the polygon.The total complexity is $O(n^3)$, $O(n^3\log{n})$, or even $O(n^4)$, based on the complexity of checking whether each of the $O(n^2)$ segments is fully inside the polygon. The precision issue is just metaphysical. I have used long double for calculation, tried several values of $\epsilon$ (precision tolerance), and somehow made it pass.
•  » » » » 3 months ago, # ^ |   0 I think the visibility part is actually quite a bit easier than airport construction because it only asks for left or right visible (which means some of the weird edge cases there never occur). One can also prove that it suffices to check left/right visible for movement as well, so the whole "line segment in polygon" part is pretty straightforward
•  » » » 3 months ago, # ^ | ← Rev. 6 →   +5 For problem K, based on the strange(?) constraints, it turns out that the conclusion that the maximum size of the convex hull in $[-D, D]$ is $O(D^{2/3})$ helps in my analysis.For each non-leaf tree node $u$, denoting the number of children of $u$ by $a_u$ and the number of leaves in the subtree of $u$ by $b_u$, we have $1 \le a_u \le 100$ and $\sum a_u \le n$, and $\sum b_u \le 10 \cdot n$ since the height of the tree is no more than $10$.The range of coordinates in the convex hull of $u$ is $[-1\,000 \cdot b_u, 1\,000 \cdot b_u]$, then the "cost" of calculating some Minkowski sums and then take convex hulls of their unions for a non-leaf tree node $u$ is about $a_u \log_2{a_u} (1\,000 \cdot b_u)^{2/3}$.A rough estimate of the maximum total "cost" is about $6.644 \times 10^8$ when $n=10\,000$ and $100$ of $a_u$ reach $100$ and the corresponding $b_u$ reach $1\,000$. Since the variables about the structure of the tree and the size of the convex hull on each tree node can hardly reach the maximum generally, I think even the order is overestimated.I wonder if it is possible to analyze the total "cost" in a more precise way or without the range of the coordinates.
•  » » » » 3 months ago, # ^ |   +8 I wrote K (which is a bit of a mess, I know), and I agree that analyzing the actual worst-case "cost" seems to be very hard. My original solution actually involved one angle sweep for the entire tree (rather than for individual Minkowski sums). The best I could prove was some limit with a 4^(tree height) factor, but in practice the number of updates was nowhere close. Trying to bound the solution based on the integer lattice isn't great either, since the real convex hulls don't come anywhere close to maximal (cough vanity link cough). I think the bounds we chose made it possible to convince yourself that the worst case wasn't going to get TLE, but in practice it probably required a bit of a leap of faith.I don't think anyone's mentioned the "simple" solution yet that Errichto covers in the official solution video. Since you can greedily find minimal/maximal solutions along any given projection line, you can recursively trace the convex hull of all possible final solutions. I think none of the teams found this solution, and we also didn't discover it until late in the process (when we were discussing how to defeat heuristic loop-over-the-angle solutions, and then realized that this was one heuristic solution that was actually correct). Amusingly, the O(convex hull size * tree size) runtime of this solution does NOT depend on the degree or height limits in the problem. It's a little slower than the Minkowski-sum approach, but still runs fast enough (and further hard-to-analyze optimizations based on bounding distances are also possible).We thought there was a possibility somebody might stumble on the "simple" solution early and then, as sometimes happens, there would be a follow-the-leader effect and a bunch of teams would find it.
•  » » » » » 3 months ago, # ^ |   +3 Second solution is very cool, super easy to implement. I believe it is made easier if we add to the convex hull only the vertex in the direction pointing outwards (ignoring the one in the opposite direction even if it is not within the current convex hull). Not sure if that was emphasized.For the first solution I believe that Kamil described that in such a naive way that its actual complexity is $O(NHK^2 \cdot \log)$ instead of $O(NHK \cdot \log)$ as claimed, but it can be easily improved to even $O(NH \log K \cdot \log)$ (basically deeming the degree constraint useless)
•  » » » » » » 3 months ago, # ^ |   0 You're right, I don't think that was spelled out. The greedy algorithm naturally spits out maxima/minima, but you really just need the maxima that points outside the current convex hull (as long as you initially recurse on, say, [L,R] and [R,L] to get both sides of the hull). So you're just divide-and-conquering, you don't need to maintain the hull as you go.
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   +8 Thanks for your great work! The "simple" solution looks pretty good, and I will check the official solution video for more information.Some of my friends tried Minkowski sums during the mirror contest without complexity analysis or they just somehow belived that works fast. So I think it is acutually a hard but interesting work to analyze the complexity in many strict ways :)
•  » » » 3 months ago, # ^ |   +16 J: Splitstream$O(N*Q)$ solution works.First, run topo sort to find the length of each sequence.Then for each query, move up its parent(s) until one reaches 1st sequence.Given that our answer is $k^{th}$ index of $x^{th}$ sequence, based on how it was created and the type of operation split/merge, we can find to which input sequence and index it belongs.Keep repeating it until one reaches sequence 1. We know that sequence 1 is the identity sequence.
•  » » » 3 months ago, # ^ |   0 For problem H, what does "rotate all other strings by 180 degrees" mean exactly?
•  » » » » 3 months ago, # ^ |   0 Reverse and then replace ( by ) and vice versa
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 we did naive iteration (with vectors) for L. Now that I think about this, you could precompute the time needed to move $(dx, dy)$. This gives a simple $O(nmklogk)$ solution if you use sorting and $O(nmk)$ if you use bucketing.
•  » » » 2 months ago, # ^ |   0 Does have any discussion regarding to solution for problem E?
 » 3 months ago, # | ← Rev. 3 →   +74 (one small rant, sorry) [1.20hr debugging time, 3WA]Am I the only one who assumed that 1, 2, ..., n is the topological order in problem J? Like it's written that the numbers form a consecutive sequence (yeah, I understand that it means that it's a permutation of 1 to N but come on). [from the statement: The overall input is identified by 1, and the remaining input/output identifiers form a consecutive sequence beginning at 2]Of course, it is topological in all 3 samples. So annoying.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The overall input is identified by 1, and the remaining input/output identifiers form a consecutive sequence beginning at 2.Idk why, but I assumed that this means 1,2,..., n is topological order.We have 8 WAs on the scoreboard. My teammate coded it along with topological ordering. During debugging, the first thing I did was remove this part. After fixing other bugs, once we were certain that the code could not have any other bugs. We submitted with assert, only to find this isn't true. Then we rewrote this part, only to get an AC at 3:30 hrs.
•  » » » 3 months ago, # ^ |   0 Yeah, I literally read my code 10 times and was so convinced that there can be nothing wrong. Even when my teammates, after a long debugging, told me that might be the problems, I first refused to believe as I don't know, they are consecutive. Of course, any stress tests that I have written aligned with my understanding of the task.[My opinion only, as this is my first and last WF]: It's such a shame that literally places 8-30 or similar are majorly influenced by how much time you spent debugging J regarding this awfully written piece of description + deciding whether to go or not with O(QN) in B. A competition this prestigious should not be decided on this vague and semi-random behaviour -- why don't you just put that in the samples? Insane.
•  » » 3 months ago, # ^ |   +24 As I definitely agree that it is rather an ass move from organizers, you could have dealt with this issue better too from a strategical point of view I think. This is a 5 mins coding problem that many teams did not have problems with. If you are losing your mind over debugging it, it likely means you fell in some trap that will be hard to realize for you. In such case it is the best to just let your teammate code it from the scratch, because he will likely not fall in the same trap (it is important to NOT let him know anything about this problem)
•  » » » 3 months ago, # ^ |   0 Yes, I fully agree that we should have handled it better. However, regarding the it is important to NOT let him know anything about this problem, what my first thought after getting a WA on a problem that I'm convinced it should pass is to ask my teammates to sanity-check my idea and take a look at my code for some silly mistakes.I guess, given the difficulty of the problem, that probably the best way to deal with it is to ask to reimplement from zero. Thanks for the advice.
•  » » » » 3 months ago, # ^ |   0 "what my first thought after getting a WA on a problem that I'm convinced it should pass is to ask my teammates to sanity-check my idea and take a look at my code for some silly mistakes." — that makes some sense as well. However you have 2 teammates, so if you want to ask sb for sanity-checking you can use help of one and leave second one "uninfected" :D
 » 3 months ago, # |   +31 Love the redemption story of matthew99!
•  » » 3 months ago, # ^ |   +27 From whining to winning
 » 3 months ago, # |   +5 It's nice to see other names of universities at the top of the scoreboard! (I'm talking about EU universities)
 » 3 months ago, # | ← Rev. 2 →   +21 I think that D is super similar to luggage problem from WF 2007. Back then Warsaw team solved it and won finals by doing so. You would think that the level of competitors increases, so someone should be able to solve D today! But yeah, it is not fun, just pain (and that is said by a fan of geo)
•  » » 3 months ago, # ^ |   0 Totally agree (we didn't have time for D tho)
 » 3 months ago, # |   +8 Participated in the mirror with e3c8f1a924 and yyandy, with 6 problems passed and 872 mins of penalties. F is not so hard as it is on the scoreboard for me, and I'm not smart enough to come up with the FFT idea of G. One of my teammates struck in the edge case of B, and sadly didn't solve until the mirror ends.By the way the same question with Radewoosh: will there be a mirror scoreboard?
 » 3 months ago, # |   +43 Hi there! Please, leave your feedback about the live broadcast here. Thanks for watching!
•  » » 3 months ago, # ^ |   0 we need better camera quality
 » 3 months ago, # |   +5 MIT team rocks.
 » 3 months ago, # |   +55 Congratulations Champion MIT
 » 3 months ago, # |   +9 B站加1分
 » 3 months ago, # | ← Rev. 2 →   +63 Also, the typo in G was quite badly handled. It is a very important thing to note for contestants and the only way it was communicated was through an announcement in the system which was present from the very beginning. It was quite easy to miss it as at the beginning you frantically read all the problems etc., you may not even note it is there and later on you can simply forget about it even if you've seen it was there. I know that this affected me when writing mirror (as I was possibly considering bitsets solution which would be out of the question for raised limits) and I know it affected Warsaw team even more (apparently our top participant wasted 40 minutes because of this). It should have been both 1) said quite loudly before the start of the contest that there is a typo in constraints in one of the problems, 2) corrected using pen on already printed statements. System announcement is just far too easy to miss for such a crucial mistake by organizers.
•  » » 3 months ago, # ^ |   +30 My team was also ruined with 75 minutes and 5 penalties due to this typo in G.It's my lack of attention, but as you said, I wish it was more easily noticed(like the announcement during the codeforces contest).
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 We also didn't see the announcement but due to bad reasoning I somehow hardcoded $i+j*1010$ which made our solution work. (Idk if it's correct still)
•  » » 3 months ago, # ^ |   +66 We even did not see the announcement during the contest. My first submission used long double and got Time Limit Exceeded. Then I simply changed to double and passed. I was also wondering at that time how could long double not pass the time limit with arrays of length $2.5 \times 10^5$ and only knew that there was an announcement about this after the contest.A fun fact: In SWERC 2020-2021, the statement of problem G (yeah, again problem G) had a wrong range of input data. They wrote something like $10^5$ but the test cases contained something like $10^6$. We opened that problem very early and kept getting Runtime Error and the whole contest for us was ruined. Before this World Finals, I changed all codes in my contest library to using vector instead of global static array and thus luckily avoided the issue this time.
 » 2 months ago, # |   +15 Hi! The judge isn't working. Someone know another judge with the WF Dhaka problems?
•  » » 2 months ago, # ^ |   +10 Bumping this with hope.
•  » » » 2 months ago, # ^ |   0 Bumping this with hope.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +15 Hi, I just saw this and made some inquiries. Kattis didn't run the WF this year, but I think they have the data and hopefully they'll mirror it soon. Also, the judge data should be posted on the ICPC page within a few days. Sorry for the vagueness; it was an unusual year. I'll make sure the data ends up somewhere.EDIT: The judge data is up on the ICPC site. It's not as good as a mirror, but it's better than nothing.
•  » » » 2 months ago, # ^ |   +10 Thx!
•  » » 2 months ago, # ^ |   +73 I have uploaded all the tasks and official standings to QOJ. You can upsolve the problems or start virtual contest here.Please note that since the official contest archive does not contain any checkers, I have implemented the unofficial ones. Please contact me if there are any bugs in the checker.
 » 2 months ago, # | ← Rev. 3 →   -11 _
•  » » 2 months ago, # ^ |   0 hihihiha