### ko_osaga's blog

By ko_osaga, history, 10 months ago, ,

Hello!

International Olympiad in Informatics (IOI), the most prestigious programming contest in the world, is held in a beautiful city of Baku, Azerbaijan this year.

Wish the best luck to every contestant!

Day1: The contest had started on time, but the scoreboard is broken. It seems there is no mirror this year.

Day1 Contest Overview: Benq solved all Day1 problems in only 3.5 hours, congratulations! Full scorers for each tasks: 23(rect) / 170(shoes) / 6(split)

Day2 Contest Overview: The winner for Day2 is duality, but Benq still secures his consecutive IOI win. Congratulations! Full scorers for each tasks: 0(line) / 47(vision) / 2(walk)

Contest Results

1. Benq 547.09
2. 300iq 511.22
3. duality 494.33
4. TLE 491.46
5. FizzyDavid 482.39

Country Ranking

• 1 Russia 4G
• 2 China 3G1S
• 2 United States of America 3G1S
• 4 Republic of Korea 2G1S1B
• 4 Vietnam 2G1S1B

Congratulations to everyone who competed, and especially to our super awesome team gina0605 GyojunYoun onjo SebinKim !

• +195

 » 10 months ago, # |   +18 The scoreboard is no longer broken!
•  » » 10 months ago, # ^ |   +19 And Korea first place in 1hr! (GyojunYoun)
 » 10 months ago, # |   +16 It seems there is no mirror this year. How do you know that?Also, I see you downloaded the task statements, how did you do that? I can't find anything on the IOI site.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +25 He has access to the tasks because he is a leader for team Korea.
•  » » 10 months ago, # ^ |   +21 How do you know that? It's just a guess :p I see you downloaded the task statements, how did you do that? I downloaded it last night because I was helping the translation.
 » 10 months ago, # | ← Rev. 3 →   +112 Abridged statements:shoes: You are given $2N$ nonzero but possibly negative integers. You should minimally swap adjacent pairs to achieve: $|X_{2i}| = |X_{2i+1}|$ $X_{2i} < 0, X_{2i+1} > 0$ for all $0 \le i < N$. What is the minimum required swaps? It's guaranteed that it's possible. $N \le 100000$split: Given undirected connected graph $G$. find a tripartition of $V(G)$ of size $a, b, c$ respectively ($a, b, c$ given in input), where at least two of the partition is “connected” (it’s induced subgraph is connected). Return the tripartition or state that it's impossible. Note that it's partition, so $a+b+c=n$. $|V(G)| \le 100000$rect: You are given a map of $N \times M$ grid where each cell has integer height $0 \le H[i][j] \le 7000000$. A rectangle is a set of rectangular area $[x1, x2] \times [y1, y2]$ s.t $1 \le x_1 \le x_2 \le N-2, 1 \le y_1 \le y_2 \le M - 2$ (so should NOT contain cells in edges). A rectangle is valid if for each cell $(i, j)$ in rectangle, $min(H[x1-1][j], H[x2+1][j], H[i][y1-1], H[i][y2+1]) > H[i][j]$ holds. Count the number of possible rects. $N, M \le 2500$.
•  » » 10 months ago, # ^ |   0 What's the constraint of $N$ in problem shoes'?
•  » » » 10 months ago, # ^ |   +3 $N \le 100000$
•  » » » » 10 months ago, # ^ |   +11 Change "7M" to normal number, it's confusing.
•  » » » » » 10 months ago, # ^ |   0 done
•  » » » » 10 months ago, # ^ |   +65 Also, shoes are identical to this task, but IOI has higher limits (editorial tells how to solve higher limits anyway).
•  » » » » » 10 months ago, # ^ |   +59 This issue was raised in the GA meeting but was rejected. I don't like it too, but apparently, ISC didn't found the better task, so maybe it's better than yet another Nowruz.
•  » » » » » » 10 months ago, # ^ |   -47 Ask me next time, I have a couple of good tasks prepared.
•  » » » » » » » 10 months ago, # ^ |   +18 You can ask them in Call for Tasks
•  » » » » » » 10 months ago, # ^ |   +107 After reading this comment I want to downvote somebody, but I know that it isn't your fault. :/Good that there are some other comments which deserve downvotes xd
•  » » » » » » » » 10 months ago, # ^ |   -13 How can someone be too good for IOI?
•  » » » » » » » » 10 months ago, # ^ |   +77 The editorial mentions the following: If the leftmost person is in pair $a$, swap the other person in pair $a$ left, to the second position. Now the first two people are both in pair $a$, and we repeat the process on the remaining $n-1$ pairs of people recursively. Add "in case of tie pick leftmost", then you get 85 points. So until 85 points, it's an identical problem. I think your typical argument of "you are a soulless red coder but purples will agree" is nonsense. You are just avoiding criticism. “Pick leftmost" strategy is clearly doable if you studied hard enough to remember that CF one. I was blue 5 yrs ago, and I also hold contests for blue. Don't dismiss them, or us. Problems that are both easy enough and significantly more original than this one are incredibly rare. Agreed, but this is IOI, so they are usually one of the best problems in the world. Problems such as 2015 boxes, 2018 combo are easy enough but much more innovative.
•  » » » » » » » » » 10 months ago, # ^ |   -33 I haven't been involved in selecting the problems for this IOI in any way other than raising my country sign along with 70+ other people, so at least in this context "avoiding criticism" makes no sense to me -- I'm not the one being criticized when people dislike that this problem was used. I'm just trying to explain why I personally find the problem OK. Or more precisely: not great, not terrible.I don't understand the obsession with originality at all costs -- given that it's hardly possible nowadays, and it can only get worse. E.g., I also love the task Boxes, but I can easily show you older problems that are easier versions of it in the same sense in which the CF task was an easier version of the IOI task this year. There are literally hundreds of thousands of problems out there, and if you dig enough, you'll find something that uses the same idea -- especially if that idea is easier. Most of the easy IOI problems are similar to other problems that have appeared before. IMHO, on its own this should not be perceived as a bad thing.At the IMO it's common that problems 1 and 4 can be solved using standard techniques, and everybody expects that the well-prepared contestants will easily, quickly and consistently solve them, as they would have seen and solved ten similar problems before. The problems 1 and 4 are there to challenge the lower part of the field, not the crowd fighting for gold. The IOI needs to do the same. In order to be as fair as possible when handing out the medals in the end, the problem set cannot be top-heavy only. If you do that, you would have a clear winner and random noise in the middle of the ranklist. The problem set needs to have parts that discriminate well around each of the medal boundaries. If you are really lucky, someone will contribute an easy ad-hoc problem, but in past years that happened only rarely and going forward such problems will only be more rare. Most of the easy IOI problems will have to look like this one: be based on clever use and modification of standard techniques. This is precisely the type of problems for which everyone who (to use your words) "studied hard enough" will have already seen the technique and they just have to apply it to solve the problem. In my point of view, this is precisely what was going on in the Shoes problem. In particular, I'm convinced that the CF problem gave less advantage to people who solved it than e.g. any of the many problems in which you move stuff to the left of an array and use a Fenwick tree to keep track of it. That implementation is much closer to what they had to write here.
•  » » » » » » » » » 10 months ago, # ^ |   +84 I don't agree to your opinion about IMO. It's true that well-prepared contestants solve problems 1 and 4 easily, but I don't think it's because they have seen ten similar problems. At least, I always expected to see problems easily solved but with new or uncommon ideas.Nevertheless, it's hard to find an easy, interesting and new problem, so you may not be able to put one in IOI. Only in such a case should tasks like shoes (easy and interesting but not new) be used.But actually, in this year's IMO, problems 1 and 4 are very typical and everyone who studied hard enough must have already seen the technique and they just have to apply it to solve the problems. So, organizers, including leaders, probably think in the similar way.
•  » » » » » » » » » 10 months ago, # ^ | ← Rev. 3 →   -32 Re IMO, I think I have similar expectations as you but I use different words to describe them. I do expect those problems to be uncommon in the sense that I would not have seen that exact problem before, I just expect them to be standard in the sense that I would have seen and used the techniques that work on them before. Or, more precisely, what usually makes these problems easy to me is that the techniques you'll try intuitively will work, and gaining that intuition is precisely thanks to the practice we put in. E.g., you read 2018-4, you see that it's about chess knights, you remember problems about placing many knights onto a chessboard and related invariants, and you apply those to this problem.I guess another part of the problem is that originality is not binary -- problem isn't just "original" or "not original", it's (at least) somewhere on a real-valued scale and different people with different experience will necessarily place it on different places on that scale.I agree with everyone that problems that fall on the "more original" end of the spectrum for most people are the best. I would love to have such IOI and IMO problems every year, I just don't expect that we can realistically have that, and I'm saying that the second best is still not a tragedy if we don't.
•  » » » » » » » » » 10 months ago, # ^ |   +29 :) Haha you reminded me of this problem I wrote for an ACM contest that was identical to 2015 Boxes. It didn't cause big problems though, as that contest was only one week before IOI2015, and only one China team member had seen this problem beforehand
•  » » » » » » 10 months ago, # ^ |   +18 Seems like "another Nowruz" happened anyways.
•  » » » » » » » 10 months ago, # ^ |   +10 Today's task is way harder.
•  » » » » » » » 10 months ago, # ^ |   +39 I think it's OK because that problem has the correct solution. I believe the data was given as output-only because it was very tricky, and there is a benefit of giving input data with visualizers.
•  » » » » » 10 months ago, # ^ |   +163 Wow, ksun48's only CF task ever can make IOI???
•  » » » » » 10 months ago, # ^ |   +60
•  » » » » » » 10 months ago, # ^ |   +11 I didn't get 100 points lmao
•  » » » » » » » » 10 months ago, # ^ |   +9 While I agree that you have some valid points, "very arrogant and disrespectful" perfectly fits you, who namechecked all 13 people without 100 points.
•  » » » » » » » » » 10 months ago, # ^ |   +58 I'm going to assume that by "namechecked" you meant "named", as I did check the entire table from the mapping to CF handles, and I fail to see how analysing publicly available data is arrogant or disrespectful. I'm assuming number 40 yesterday also didn't come up from the thin air.However, I agree that it was not the right decision to implicitly name the 13 people I found as the backup for the data and I apologize for that if it caused any offence. Simple aggregation would have been enough, so I concede to your description in this instance.
•  » » » » » » » » » 10 months ago, # ^ |   +8 I was one of those 13 people, I dont feel offensed. Also something to consider is, its an older contest, I didnt even remember solving this problem. I didn't even remember it existed. It was 14 months ago
•  » » » » » » 10 months ago, # ^ |   0 Hey, i am it :)
•  » » » » » » 10 months ago, # ^ |   +3 39613311 didn't get 100 pts?
•  » » » » » 10 months ago, # ^ |   +2 To give more data to people who are not in the GA meeting, ISC also pointed out the fact that at least 3 of the ISC/HSC (I forgot who is the other one, sorry) solved the problem during the contest (in $O(N^2)$) and did not realize about it when reading the task.To me, the greedy intuition is "just another simple greedy intuition" that we can easily forget after solving the Codeforces task. Even if contestants do remember, there are still the additional steps to solve the problem. As demonstrated by eduardische above, some contestants did forget about the problem, or did not manage to solve the additional steps.
•  » » 10 months ago, # ^ |   +8 In problem "split", it isn't always possible is it? Do we have to determine whether it is possible as well?
•  » » » 10 months ago, # ^ |   +12 Consider a star. Also, consider this sentence: "Return the tripartition or state that it's impossible."
•  » » » » 10 months ago, # ^ |   +14 Oh, the sentence was not there when I commented, thank you for pointing out :)
•  » » » » » 10 months ago, # ^ |   0 Wow, you're right, sorry then :)
•  » » » » » 10 months ago, # ^ |   0 It was done by myself before your comment, so somehow you got the older revision? Thanks for the clarification anyway.
•  » » » » 10 months ago, # ^ |   +10 A "state that it's impossible" phrase isn't really a guarantee that the task really is impossible; it might be just a trick of the setters. But I agree, the star case is enough to show impossibility.
 » 10 months ago, # |   +39 Do you think that IOI is prestigier than ICPC?
•  » » 10 months ago, # ^ |   +17 Obviously
•  » » » 10 months ago, # ^ |   +51 Somewhy I think opposite :)
 » 10 months ago, # |   +30 The tasks for #ioi2019 first competition day:http://jonathanirvin.gs/files/ioi2019/
 » 10 months ago, # |   +18
 » 10 months ago, # |   +30 Problem split reminds me this theorem (Can be spoiler): Link to arXiv
 » 10 months ago, # |   +80 Can someone verify? Solution for problem splitWithout loss of generality, we can assume that a <= b <= c, and we want to find connected components of size a and b, then all the remaining vertices go to the third part.Let's solve the tree subtask first. Root in the centroid. Let's consider centroid's sons and sizes of their components ($a_1$, $a_2$, ..., $a_k$) respectively. Each of those does not exceed $n/2$. Clearly, if none of those components has size >= a, it's impossible to find the desired partition. Otherwise, we can just take that component, find first partition there, and find the second partition in the rest of the graph (there are definitely enough vertices there).Back to the general case. We can pick any spanning tree and solve the problem as if it was a tree problem. If we failed to find a solution, it means that every component has size smaller than a. We will now consider connections between the components and build a new graph consisting of those $k$ vertices, where each node has some weight $a_i$, and connections to other components according to the previously ignored non-tree edges. We aim to find a connected part of size at least a in the new graph, and break the DFS as soon as we manage that (!).If we fail, then it must have been impossible to find the desired tripartition. Otherwise, we can take that component, find a vertices there and other part of the graph will definitely have a connected component of size at least b. Why? The overhead in finding part $a$ is at most $a-1$, because otherwise we would have stopped the DFS earlier. Since all the components are connected through the centroid and $a <= b <= c$, it means that there are at least $b$ nodes in the rest of the graph.Thus, we get a very implementable solution. Shoutout for problem setter!
•  » » 10 months ago, # ^ |   0 That's exactly the same as what I did :)
 » 10 months ago, # | ← Rev. 3 →   +38 Task split is in my opinion completely amazing, easily best problem of the year so far! SpoilerTaking c to be the biggest and having required 2a+b<=n as a consequence which is needed in the process of the solution just plays out in such a satisfying way!
•  » » 10 months ago, # ^ |   -54 Even though I solved the task, I have no idea what you're saying here...
 » 10 months ago, # | ← Rev. 2 →   +29 split, 25x over-complicated and fixedLemma: assume the graph is biconnected and let $x, y$ be such that $x + y = n$. Then there exists a partition of the graph into two connected subgraphs of sizes $x$ and $y$.Proof: find any st-ordering of the vertices of the graph, which can be done in $O(m+n)$ or $O(m \log n)$ time. Then, take its prefix of length $x$ and suffix of length $y$ as the subgraphs. From the definition of an st-ordering, it's easy to see that they are connected. (end)Lemma 2: assume the graph is biconnected, but now the vertices have positive weights not exceeding $w$. Then, if $x, y$ are such that $w + x + y \ge n$, then there exists a partition of the graph into two connected subgraphs of total weights at least $x$ and $y$.Proof: find any st-ordering as above. Find the shortest prefix of the ordering with weight $\ge x$. Its weight will be less than $w + x$, so the corresponding suffix has weight $\ge y$. (end)Now, let's $a \le b \le c$. Consider the block-cut tree of the graph (slightly modified so that each vertex of the original graph is in this tree; if the vertex $v$ is not an articulation point, it'll be a leaf connected to the corresponding biconnected component). Find the weighted centroid of such tree (the vertex after whose removal no subtree will contain more than $n / 2$ original vertices of the graph). If this centroid is a biconnected component $X$ and one of the subtrees of the block-cut tree contains $\ge a$ original vertices, take that subtree to set $A$ and its complement to set $B$. Obviously, $|A| \ge a$, and $B$ is connected and $|B| \ge \frac{n}{2} \ge b$. If this centroid is a biconnected component $X$ and all the subtrees contain $< a$ original vertices, create a weighted graph contracted to $X$ where each vertex $v \in X$ has its weight equal to the size of the component containing $v$ after removing all the edges in $X$. Each weight is $< a$, and $2a + b \ge n$, so we can apply the algorithm from Lemma 2 on $X$ to find two connected sets of vertices $A$, $B$ with total weights $\ge a$, $\ge b$. We can then expand the graph back, taking whole connected components to each set. If this centroid is an articulation point and all the components created after its removal have size $•  » » 10 months ago, # ^ | ← Rev. 2 → +28 Well, I come up with the same idea about biconnected components, but it was looking very complicated, so I gave up and started merging shitty solutions to get 64 (°ー°〃) •  » » » 10 months ago, # ^ | 0 For split, it seems to have numerous heuristics that is almost impossible to break.. I believe 64 points worked by trying all DFS spanning trees in each root. •  » » » » 10 months ago, # ^ | +24 I thought the same, but somehow organizers made tests really strong, kudos for that. I thought it would be impossible to break heuristics and this task will have like fifty solutions for 100pts, but only five of them would be legit solutions. It's great to see I was mistaken in that prediction. •  » » » » 10 months ago, # ^ | +17 No, it doesn't work. My solution is much harder (・へ・) •  » » » » 10 months ago, # ^ | 0 I tried every root and only got 40. •  » » 10 months ago, # ^ | +60 Sorry, can you please post your sketch of proof? I've been thinking about it for a while and it seems to me that there may be a counterexample. Consider a = b = c = n/3. Let's construct the graph like this: there is a clique of size 2*a-2. The other a+2 vertices we add as single edges attaching to distinct nodes in the clique. In this case we have a solution (consider one added vertex and a-1 vertices from the clique, times two), but if I understood your solution correctly, neither of your statements hold. The biggest biconnected component is of size less than a+b, and after we remove any articulation point we get components of sizes N-2 and 1. Sorry, I don't post comments often so I don't know how to use math mode. •  » » » 10 months ago, # ^ | ← Rev. 3 → 0 Oh shoot, you're right! I think I know how to fix this, but it's even more complicated and starts looking like "the model solution, only with extra steps". I'll try to edit my post in a moment. Thanks!Edit: done, hopefully. I had a false statement in my proof that went like: "if after removing any articulation point$v$, there exists a connected component of size$\ge \frac{2n}{3}$, then there exists a biconnected component of size$\ge \frac{2n}{3}$". It's false, obviously. Silly me...  » 10 months ago, # | ← Rev. 7 → +9 I want to share my idea for rect and split. (I haven't tried to implement yet, so please correct me if I'm wrong).Rect: HintFirst considering the condition: (*) forall i, j: min(H[x1 − 1][j], H[x2 + 1][j]) > H[i][j]. In order for (*) to be true, we see that (x1 − 1, j) must be the first position such that H[x1 − 1][j] >= H[x2 + 1][j] if we move (x2 + 1, j) up or (x2 + 1, j) must be the first position such that H[x2 + 1][j] > H[x1 − 1][j] if we move (x1 − 1, j) down. From that observation, we can conclude that the number of states (x1, x2, j) satisfying the (*) condition is about O(2 * N * M).So we can prepare all (x1, x2, j) states as well as (y1, y2, i) states.After that, we can calculate the number of (x1, x2, y1, y2) states satisfying the problem condition with sweep line and a segment tree in O(N * M * log2(N * M)).Split: HintWLOG, assume that a <= b <= c. It's obvious that we always want to pick connected components with size a and b. Considering a spanning tree T from our initial graph G. We find the centroid node in T, called x. After removing x from T, we have m connected components V[1], V[2], ..., V[m]. We repeatedly perform the following operations: If exists i (1 <= i <= |V|) such that |V[i]| <= a, we pick V[i] then stop. Try to find an edge (u, v) such that u in V[i], v in V[j] and i != j. If found satisfied (u, v) go to the 3rd operation, else we stop. We merge two components V[i] and V[j] and then go to the 1st operation. Suppose that we cannot pick any components with size >= a (stopped at the 2nd operation), which means that we must use x (the centroid node) to create a component with size = a. However, if we use x, in the remaining components, we cannot find any components with size >= b >= a. In other case, if we found a component V[i] with size >= a, we can use V[i] to create a components with size = a. Now, all we have to do is to prove |G / V[i]| >= b because we know that G / V[i] is a connected component. Considering two cases: V[i] is not created by merging two components V[x], V[y]. V[i] is created by merging two components V[x], V[y]. With case 1, we know that V[i] <= a -> |G / V[i]| = n − a >= n − a − c = b.With case 2, we know that |V[i]| = |V[x]| + |V[y]| -> |V[i]| < 2 * a -> |G / V[i]| > n − 2 * a >= n − a − c = b. •  » » 10 months ago, # ^ | +10 I don't see how preparing (x1, x2, j) states easily helps you to solve the whole problem. Can you explain a bit more? •  » » » 10 months ago, # ^ | ← Rev. 7 → +9 Well, after preparing all (x1, x2, j) and (y1, y2, i) states, you can merge two adjacent states together, for example (x1, x2, j) with (x1, x2, j + 1) or (x1, x2, j − 1).So we can deduce to the new problem:Given P rectangles of type 1: [(a1, b1), (c1, d1)] and Q rectangles of type 2: [(a2, b2), (c2, d2)]. Count number of pair rectangles x of type 1 and y of type 2 such that a1(x) <= a2(y) <= c2(y) <= c1(x) and b2(y) <= b1(x) <= d1(x) <= d2(y).You can fix the segment [b1(x), d1(x)] and sweep line those segments [b2(y), d2(y)]. So all you need to do is to calculate the number of rectangles y such that a1(x) <= a2(y) <= c2(y) <= c1(x).It seem that this kind of problem can only be solved in O(P * log2(N) * log2(M)). However, you can see that for every pair rectangles y1, y2 of type 2 that have overlapped area, there are only two cases: a2(y1) <= a2(y2) <= c2(y2) <= c2(y1). a2(y2) <= a2(y1) <= c2(y1) <= c2(y2). With that observation, you can reduce the complexity to O(P * log2(Q)). •  » » » » 10 months ago, # ^ | ← Rev. 2 → 0 I got to all your points above, but I fail to see how that last observation reduces the complexity to$O(P\log Q)$. Can you elaborate? •  » » » » » 10 months ago, # ^ | ← Rev. 4 → +3 You can sort all pair [a2(y), c2(y)]. For a query, you want to calculate the number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c2(y) <= c1(x).To answer a query, first, you can calculate the number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c1(x). So all you need to do is to calculate he number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c1(x) < c2(y) (*) to subtract the result with this.You see that all the rectangles of type 2 satisfying the (*) condition have overlapped area, so there are only two cases as I mentioned in the comment above. Or if we call S as the subset of rectangles of type 2 satisfying the (*) condition, it is true that: a2(S[i]) <= a2(S[i + 1]) (0 <= i < |S| − 1). c2(S[i]) >= c2(S[i + 1]) (0 <= i < |S| − 1). You can find S[0] position and S[|S| − 1] position on the segment tree by storing something like (does this segment contain an element equal to 1, if it does what is the maximum c2 value of an element equal to 1). UPD: I just realized that my above solution is wrong. So I'm very glad to hear another solution if possible.  » 10 months ago, # | +6 For the purpose of medal allocation, after day 1 the official number of contestants is 327. (This number cannot go down after day 2, and most likely it should not change.) •  » » 10 months ago, # ^ | 0 Isn't it 331? •  » » » 10 months ago, # ^ | ← Rev. 3 → 0 No, 327 is the number we were told at the meeting after day 1. AFAIK, four of the contestants who were shown in the online results are contestants who were registered for the IOI but did not take part in day 1. The most likely reason is that they are not here and they won't take part in day 2 either, but I don't know for sure whether this is the case. (And in the past there were some cases when some contestants only took part in day 2 for various reasons.)  » 10 months ago, # | ← Rev. 2 → 0 There was an accepted appeal that still is being worked on that may or may not result in the score change, so at this point results of Day 1 are not final. •  » » 10 months ago, # ^ | 0 Can you tell what appeal is about? •  » » » 10 months ago, # ^ | +8 According to ISC, some contestant or contestants were not able to submit during the final moments of the contest due to CMS slowness. If any of that submission would've gotten a bigger score, it may be submitted manually and the score would be updated. My understanding is that there are backups of workstations at the time of contest end, so any changes made during the analysis shouldn't be a factor. •  » » » » 10 months ago, # ^ | ← Rev. 4 → 0 Im not 100% sure if i managed to change it in time, but i might have an ac code for shoes on the machine at the time when the contest ended. Is there some chance that someone can check that? I will provide details if it's possible.Edit: i guess that i have to do that with my team leaders and it too late for that now, plus im not sure if the appeal is valis and its "only" 15 points so it doesn't matter that much. •  » » » » » 10 months ago, # ^ | ← Rev. 2 → +8 Yes, officially it's the case that your team leader has to submit an appeal. Before dinner we were told to submit these appeals if we have them and didn't submit them before, and there was no strict deadline on this. Get in touch with your leader, you have nothing to lose by doing so. Ideally, send them the exact name and location of the file you want rejudged.(Edit: I would recommend that your leader should send the details to the ISC by email ASAP and to formally file an appeal on paper later, if required.) •  » » » » » 10 months ago, # ^ | 0 There just was an e-mail distributed amongst GA that if students were affected by the issue at the end of the contest, and haven't yet submitted an appeal, that the deadline is tomorrow noon (in ~13h from now). So definitely contact your leaders! You'll need exact path and filename on your machine to be evaluated. •  » » » » » » 10 months ago, # ^ | +3 I did that, thanks! Now i can just hope :) •  » » 10 months ago, # ^ | 0 Is it about the solution for p3?  » 10 months ago, # | -39 ...is held in a beautiful city of Baku, Azerbaijan this year.Sorry for the offtopic, but maybe you should have written " a beautiful city of Azerbaijan, Baku " ?) •  » » 10 months ago, # ^ | +31 it is correct both ways, in the post's way it is denoting (city, country) pair as one unit  » 10 months ago, # | +19 Benq is so strong. •  » » 10 months ago, # ^ | +43 I don't know who are you talking about, but 300iq will smash him tomorrow. •  » » » 10 months ago, # ^ | +31 grabs popcorn •  » » » 10 months ago, # ^ | ← Rev. 2 → +38 *at the icpc finals •  » » » 10 months ago, # ^ | +64 Well, he got bigger score indeed. By 0.13 xd •  » » » » 10 months ago, # ^ | +175 ٩(๑òωó๑)۶  » 10 months ago, # | 0 Anybody knows how to solve walk problem?  » 10 months ago, # | +10 It seems sad that line problem can be solved in a fully provable way (what problem highly suggested, right?), but nobody solved it and it boiled down to basically pushing through some garbage heuristics. However I don't know how to solve it as well, so I am not to blame contestants, but just stating fact that it's sad :P. •  » » 10 months ago, # ^ | +10 Well I don't think that problem highly suggested it. I didn't thought that it is possible to solve in provable way lol. Maybe n+3 is just a parameter they used for test generation •  » » » 10 months ago, # ^ | +23 There's a relatively easy$n+3$solution. •  » » » » 10 months ago, # ^ | +10 Yeah I know now, but during the contest it was not clear for me that it is solvable for any test case in n+3 •  » » » » » 10 months ago, # ^ | +10 Ok, but in general: why would a problemsetter set a problem that cannot be fully solved (I mean the one that doesn't have 100pts solution)? •  » » » » » » 10 months ago, # ^ | ← Rev. 2 → +58 What about nowruz? I thought that it is the problem of the same type. •  » » » » » » » 10 months ago, # ^ | -51 We don't talk about this problem. •  » » » » » » » » 10 months ago, # ^ | +38 I mean I thought that line is the same type as nowruz. •  » » » » » » 10 months ago, # ^ | ← Rev. 2 → +20 BOI 2019 Flash 100 points in this task is the theoretical maximum if you have infinite time. Nobody knows the 90+ solution as far as I know. •  » » » » » » 10 months ago, # ^ | +15 Huh, because 90% of output-only are not meant to be solved in a provable way? Fact that solution for given instances with <=n+3 exists is significantly different than fact that any instance you can imagine has solution with <=n+3 segments. A priori it is possible that tests were generated by creating some broken line with <=n+3 segments and marking some points on them what makes it very easy to create test like that which would then be hard to solve (similar to as it is easy to generate a graph with hamilton cycle, but it is hard to find it afterwards).So, my conclusion is that contestants could definitely suspect that some general provable algorithm exists, but can't be sure about it. •  » » » » 10 months ago, # ^ | 0 How to solve in n+3 segments? •  » » » » » 9 months ago, # ^ | ← Rev. 2 → +5 SpoilerWe decompose the point set into three sets: Increasing sequence where$x_i < x_j \iff y_i < y_j$Decreasing sequence where$x_i < x_j \iff y_i > y_j$Windows set, where spiral strategy "always works with some modification". We talk about this later. If this is possible, then we can connect from (0, 0) to increasing set, then decreasing, and windows set with only 3 extra segments. (There are technical details, but you can figure it out)This is possible, and the proof is constructive. We use induction on size$n$. If$n \le 1$, trivial. Otherwise, we consider the "bounding box" which is the minimal axis-parallel box that encloses the set. There is at least 2, and at most 4 distinct point that lies in the edge of bounding box. Now we divide cases: Two distinct points. They are in the opposite vertices of windows. Add both to increasing / decreasing sequence and remove. Three distinct points. One of them form the vertices of windows. Add that one to increasing / decreasing sequence and remove. Four distinct points. We capture all four of them as a "windows", and add them in windows set. And we remove all four of them. Since the bounding boxes are always shrinking toward the center, it's clear that the increasing / decreasing sequences are valid, and it's not hard to connect them optimally.Now we consider how to connect the vertices in windows set. Again we can see the windows are shrinking toward the center. It seems they can be simply connected by spiral strategy, but in fact, it's NOT. Instead, you start from the smallest windows. Cover all four vertices by some cycle and proceed to the next windows. In the next windows, you can either turn in CW direction or CCW direction. Set the direction appropriately to cover the point that lies in the windows segment you encountered. This strategy never creates wasteful segments. Implementation is in my github. •  » » 10 months ago, # ^ | +16 AFAIK it's solvable for every instance in$N+3$. I'm aware of the basic idea, but that's all :(Giving a normal problem as an output only has several pros and cons. For the good thing, the contestants were given visualizers, so they can easily spot what's going on (very helpful for a tricky problem like this), plus the scoring system can help break ties. For the bad thing, it gives room for ad-hoc test analysis and garbage heuristic which isn't science at all. And due to some bad past practices on OO tasks, contestants might consider the search for$N+3$solution as a "risky strategy". In general, I think the contestants got what they deserve, but some might consider the "naive spiral strategy" as garbage and should not get more than 10 points. I don't have a very strong opinion about that... •  » » » 10 months ago, # ^ | 0 How many points did spiral give? Indeed seemed garbage to me (however on random test I guess it should be ok), but I didn't try it •  » » » » 10 months ago, # ^ | -23 About 50 points. People over 90 points did something provable, I think. •  » » » » » 10 months ago, # ^ | +34 Lol I have 90+eps and I just used some greedy. •  » » » » » » 10 months ago, # ^ | +131 •  » » » » » 10 months ago, # ^ | +14 My solution(try going in the same direction as previous one by, for example, if the last line was going up, going to a point above the last point; try to keep yourself in the middle by taking the point with the median x coordinate out of all the candidates if you're going up or down and taking the point with the median y coordinate out of all candidates if you're going left or right; it's n^2 log n but TL is 5 hours) gets between 2 and 6 points on all tests which are structured like diagonal lines(i think tests 2 and 7 were crosses, test 5 looked like this: and test 4 was a diagonal line) and more than 9 points on all other tests. The union of my solution and my teammate's solution(decompose the input into a small amount of monotone sequences and handle each of them separately) seems to get 88 points.  » 10 months ago, # | ← Rev. 2 → 0 Did anyone solve vision with prefix xor over columns/rows and addition of H + W bits? •  » » 10 months ago, # ^ | 0 I did that in the contest. •  » » » 10 months ago, # ^ | +8 I think the easiest solution is to do prefix xor on diagonals and check if$dist >= K$and check$>=K+1$•  » » » » 10 months ago, # ^ | 0 Can you write how to do that exactly? •  » » » » » 10 months ago, # ^ | +8 I think$|r_1-r_2|+|c_1-c_2| = max(|r_1+c_1-r_2-c_2|,|r_1-c_1-r_2+c_2|)$. If you do prefix xor for diagonals$(i+j)$and$(i-j)$when you will have some consecutive number of ones (let's say$a$and$b$). We need to check that$max(a, b) = K$. That means$max(a,b)>=K$is true and$>=K+1$is false. To check if$a>=C$try anding$(i)'th$and$(i+C)'th$element.  » 10 months ago, # | +23 Can anyone verify my solution to walk? SpoilerNaive solution (24 points?) makes vertices for all intersection. We do some optimizations by only building only the following intersections: If a horizontal segment intersects$s$or$g$we make vertices. Make vertices for the endpoint of each horizontal segments. When the horizontal segment ends, we make an "escape route vertices", where we make vertices for two horizontal segments, vertically adjacent to that endpoint. Then we run Dijkstra on that graph. •  » » 10 months ago, # ^ | ← Rev. 3 → +10 Nah, that won't work.You will not detect the intersection marked with dot.(Edited after ~300iq pointed out my previous counterexample was wrong). •  » » » 10 months ago, # ^ | +11 I think it will detect it, cuz this intersection is adjacent to the right vertex of the upper segment. •  » » » » 10 months ago, # ^ | 0 Whoops, sorry, thanks. However I still think it doesn't work and I will update the picture in a second. •  » » » 10 months ago, # ^ | ← Rev. 2 → -10 You don't need to detect intersection? Green is that "escape" edge. •  » » » » 10 months ago, # ^ | ← Rev. 3 → +10 Where does the green line come from? You can't just add it in. •  » » » » » 10 months ago, # ^ | ← Rev. 2 → 0 When the horizontal segment ends, we make an "escape route vertices", where we make vertices for two horizontal segments, vertically adjacent to that endpoint. You are making escape edges too. •  » » » » » » 10 months ago, # ^ | 0 Escape edges have to be along an existing vertical pole; otherwise, we allow some invalid solutions. •  » » » » » » » 10 months ago, # ^ | ← Rev. 2 → 0 I think that we need to add some escape edges without existing pole, if they are correct. Without it this solutions is completely incorrect.But I am not sure if what I am saying makes sense. •  » » » » » » » » 10 months ago, # ^ | 0 It's true you sometimes can, but it doesn't work in general. I think if you can show that you're only moving left->right, then you're allowed to, but it actually could be wrong for this case. •  » » » » » » » » » 10 months ago, # ^ | 0 For instance, consider ______ | | | | |-| | | S T Adding an escape edge upwards from S to the top bar would illegally shorten the path. •  » » 10 months ago, # ^ | +15 This doesn't work (as described by Swistakk), but here's a modification which I'm pretty sure does:For each horizontal segment, insert vertices: At each endpoint At the closest intersections to the left and right of s, if it passes over s At the closest intersections to the left and right of t, if it passes over t Also, insert vertices at the intersections on poles directly above and below all the ones we listed. This gives$\le 18 M$vertices, and then we run Dijkstra. •  » » » 10 months ago, # ^ | ← Rev. 2 → 0 I solved it in contest using the exact same way. I didn't prove the correctness, though.  » 10 months ago, # | +66 tmwilliamlin168's insane comeback was probably the best thing to watch in day2, change my mind. Too bad he had a awful day1 :( •  » » 10 months ago, # ^ | ← Rev. 3 → +65 Nope, you got it wrong. tmwilliamlin168 performed horribly in day 1 intentionally just to make this ultra-awesome comeback in day 2. No one can ever match the geniosity. Ever. tmwilliamlin168 orz •  » » » 10 months ago, # ^ | +33 Can someone explain what orz means, I've seen it a hundred times in codeforces. •  » » » » 10 months ago, # ^ | +36 orz is a person bowing down on the ground. If you look carefully and squint your eyes you can see it. The "z" is the legs, the "r" is the body, and the "o" is the head •  » » » » » 10 months ago, # ^ | 0 One thing to note is that whenever "orz" is used on me, it is always sarcastic. •  » » » » » » 10 months ago, # ^ | +5 One thing to note is that when ultra-awesome genius pr0s respond to compliments, it is always sarcastically. •  » » » » » » 10 months ago, # ^ | +8 You are such a great person because of your humility!  » 10 months ago, # | +14 IOI 2019 preliminary results are available on IOI Stats. •  » » 10 months ago, # ^ | 0 Top 5 are all Chinese, such strong country. •  » » » 10 months ago, # ^ | +5 300iq is not chinese. •  » » » » 10 months ago, # ^ | +24 read this •  » » » » 10 months ago, # ^ | +3 It was a joke as redocyz replied, but I guess my since of humour is bad.  » 10 months ago, # | +8 Is country rank based off of sum? Or lexicographical order of medals? I guess the latter is a tad bit more favorable to Korea ;) Anyway, congratulations to your team on a great performance! •  » » 10 months ago, # ^ | +28 Thank you, and congratulations for team USA! I think the former is better, but we (our government?) always considered country rank based on medals. Even in 2015, where we were the absolute 1st place in score order, we used medal based rank :)  » 10 months ago, # | -29 Why did sunset perform so poorly, taking only 49th place, who knows?  » 10 months ago, # | +16 To leaders: how many appeals were there and how close is this preliminary result to a possible outcome? •  » » 10 months ago, # ^ | 0 I have not heard about any changes to the results during the meetings or some private conversations with other leaders. In other words, I have no reason to believe that any major changes will be made to the scoreboard.Of course, I could be wrong... •  » » 10 months ago, # ^ | ← Rev. 2 → 0 (I am the USA deputy leader.) There are between 5 and 10 appeals, maybe one or two still under review. In general, the vast majority of appeals are rejected. •  » » 10 months ago, # ^ | 0 My understanding is that several instances of accepted appeal for first day are still in progress.  » 10 months ago, # | +184 I stumbled upon a post by Olimpiada Informatyczna. As my Polish is very basic I gladly used the Facebook translator. But what does the following sentence mean? I spent the evening mostly with the Russians, the Russians, the Russians, the Russians, the Russians, the Russians and the Better check the original! Spędziłem wieczór głównie z Gruzinami, Bułgarami, Estończykami, Rosjanami, Ukraińcami i Białorusinami, szlifując mój rosyjski. Not cool, Facebook! •  » » 10 months ago, # ^ | +3 It's not FB's fault, it's the algorithm's fault! (Classic excuse when something goes wrong.)Or it must be those Russian hackers FB and similar media worried about so much. •  » » 10 months ago, # ^ | 0 'I spent the evening mostly with the Georgians, Bulgarians, Estonians, Russians, Ukrainians and Belarusians practicing my Russian.' The blog made by Polish leaders is amazing! Though they haven't written that in English :( •  » » 10 months ago, # ^ | +13 If we will have some international audience, we might consider translating our posts. •  » » » 10 months ago, # ^ | +13 •  » » » » 10 months ago, # ^ | +42 <3  » 10 months ago, # | +20 The GA have voted to approve IOI 2019 results and medal allocation.There have been several changes of scores from preliminary results as results of appeals but none have resulted in changes in medal allocations. •  » » 10 months ago, # ^ | 0 Can you add cf accounts in ioi stats? •  » » » 10 months ago, # ^ | +13 Yes, will do in a couple of days. •  » » » » 10 months ago, # ^ | 0 Done. More information.  » 10 months ago, # | +340 •  » » 10 months ago, # ^ | +275  » 10 months ago, # | +44 Tests when?  » 10 months ago, # | +17 Does anyone have solutions and\or test data for the problems? •  » » 10 months ago, # ^ | +9 They will be published soon (TM) on the official website here: https://ioi2019.az/en-content-27.html  » 10 months ago, # | 0 How to solve problem walk? At least for 57 points •  » » 10 months ago, # ^ | +15 The first 2 subtasks are trivial (just run dijkstra). For subtask 3, you will only go right since you should never visit the same building twice. We can write a DP solution, where dp[i][j] = min cost to get to building i at height j. We can use a set to do this efficiently.Subtask 4 seems harder than subtask 3 since the heights are not equal, but... •  » » » 10 months ago, # ^ | +6 That's because in subtask 4 (go from first building to last) you also only need to move to the right. •  » » » » 10 months ago, # ^ | +5 Not just that, you can also assume that all heights are equal in subtask 4. •  » » » 10 months ago, # ^ | 0 How do you make that dp with set in less memory and time? Because there can be many intersections •  » » » » 10 months ago, # ^ | ← Rev. 7 → +10 Use set of$(j, dp[i][j] - x_i)$don't store value if$dp[i][j]=dp[i][k] + |j - k|$for some$k\neq j\$.
•  » » » » » 10 months ago, # ^ |   0 What if you have to store many values still?
•  » » » » » » 10 months ago, # ^ |   +8 Use sweeping line, many values do not change.
 » 10 months ago, # |   +209 You can submit all problems except Rectangles here: https://oj.uz/problems/source/420It seems someone forgot to make rect.zip` public on the folder here..
•  » » 10 months ago, # ^ |   +26 Which sheepfuckers are downvoting this? Finally a place to submit.
•  » » 10 months ago, # ^ |   +63 Now all problems (including the practice contest) are ready! https://oj.uz/problems/source/420
•  » » » 10 months ago, # ^ |   0 nice
 » 9 months ago, # |   0 Can somebody explain the solution for task vision, I got up to 66 points, but I couldn't think of anything better, also I couldn't find any editorial on the internet.
•  » » 9 months ago, # ^ |   0 Look at my comment.
•  » » 9 months ago, # ^ |   0 Official live streams of both contest day contains analysis of all the problems: Day 1, Day 2