### Noam527's blog

By Noam527, history, 4 weeks ago, ,

Is it allowed now to discuss the APIO? According to the schedule, the official competition is done by now... but also according to the schedule, the open contest is in about a week.

Edit: It seems like discussions should be kept until after the open contest ends. So, don't scroll down if you want to avoid any kind of spoiler to the open contest (and yes, let's stop discussing until then).

Edit2: Should be good now.

• +40

 » 4 weeks ago, # |   +8 I was told that "we should not discuss openly about results and problems of APIO 2019, until 9:00 AM (UTC+9) of May 20th." from a responsible of APIO 2019 Tokyo venue. So I think we can discuss (at least about results), but not confident.
 » 4 weeks ago, # |   +8 Seoul site result is almost a meme. Best score is 253(GyojunYoun), and 4th ~13th are all tied to score 203. I expect 0G/13S/0B.
•  » » 4 weeks ago, # ^ |   0 Seems like 203 is pretty common result. Here we had two people with 203, and I've also heard of another 8 people with 203.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, it's common, very very common. :)Congratulation for the perfect score, by the way!
•  » » » » 4 weeks ago, # ^ |   0 How did you know?
•  » » » » » 4 weeks ago, # ^ |   0 I can see unofficial results :)
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 So... you know the unofficial results, and you said that both 253-point scorer and 203-point scorer in Seoul is expected to get silver medal. So, it means, I got two informations, right? $G_{border} \geq 254$ $203 \leq S_{border} \leq 253$
•  » » » » » » » 4 weeks ago, # ^ |   0 Maybe it's even wrong, because it's unofficial anyway, and I didn't check it rigorously. I hope Korea can get gold.
•  » » » 4 weeks ago, # ^ |   +8 what is the distribution of 203 points btw?
 » 4 weeks ago, # |   +2 Result of Vietnam: user202729_ scored 243, minhtung04042001 scored 233, and 5 others got 203.I guest all people with 203 will get silver medals. (Actually no medal, but certificates saying that they are silver medalists).
 » 4 weeks ago, # | ← Rev. 5 →   +11 Okay, so here is the known result of Japan: Results in Japan1st rank: Masataka Yoneda (E869120), 100+100+60=260 points 2nd rank: Hirotaka Yoneda (square1001), 100+27+100=227 points 3rd rank: Tomohito Hosii, 100+43+80=223 points 4th-8th (or probably 9th or 10th or more): 100+43+60=203 points I know one candidate who did not tell the score and it is not very unlikely to exceed 203 points, but including this, only four exceeds 203 points, and I personally expect that even this person got 203 points.My first guess of medal borderline was 243/203/something, but since there could many participants than usual because of ties, it is possible that even I may get gold medal :) P.S. I solved two problems (A and C) in 66 minutes :)
 » 4 weeks ago, # | ← Rev. 3 →   +8 SpoilerI found this solution for problem C but I couldn't implement it until the end of the contest.Let's assume we are given a common $[L,R]$ for all second queries. We have to find time ranges that in are sequence $[L,R]$ is consist of ones. Let's call $T_1$ is the first time that our sequence $[L,R]$ does consist of ones and $E_1$ is the first time after $T_1$ that our sequence $[L,R]$ does not consist of just ones. And call $(T_2,T_3...)$ and $(E_2,E_3...)$ like $T_1$ and $E_1$. So the answer is $E_1 - T_1 + E_2 - T_2 + E_3 - T_3.....$Now we have to find a more general solution. Let's toggle position $x$ and $s_x$ become $0$ : It means this time should be the time $E$ for some ranges. You can easily find which ranges. And update the answer for those ranges. (This could be done with treap inside segment tree). Let's toggle position $x$ and $s_x$ become $1$ : It means this time should be the time $T$ for some ranges. You can easily find which ranges. And update the answer for those ranges. (This could be done with treap inside segment tree).My solution was like that. Is there any wrong point which I couldn't see?
•  » » 4 weeks ago, # ^ |   0 Looks correct. I got 100 with it.
•  » » » 4 weeks ago, # ^ |   0 Oh, Thanks !. At least my idea seems right. It's made me happy :D
 » 4 weeks ago, # |   -8 Why is q1 so mathy though :(.
 » 4 weeks ago, # |   +21 This thread will spoil the contest for participants of APIO Open, it's better not to discuss, or to hide solutions and warn not to read the future participants.
•  » » 4 weeks ago, # ^ |   0 Sure, thanks for the information.
•  » » » 4 weeks ago, # ^ |   0 Could you, please, update your post with it to make sure everyone sees the answer and avoids discussions.
 » 4 weeks ago, # |   +8 Top 3 in Kazakhstan: Batrr 300 BThero.03 243 windazz 203
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).
 » 3 weeks ago, # |   +34 Problems were pretty standard, almost trivial ideawise. Quite sad cause APIO had high problem quality. (I wanted to do call for tasks, but was too busy :( )Can anyone solve B in $O(m^{1+\epsilon})$ time for $\epsilon > 0$, possibly using very complicated data structures?
•  » » 3 weeks ago, # ^ |   +16 As far as I know, zero problems was received from call for tasks :)I'm not problem setter, so this information may be outdated, totally wrong, or something else.
•  » » » 3 weeks ago, # ^ |   +35 Afaik only B was from call for tasks.
•  » » 3 weeks ago, # ^ |   +11 The ideas were not difficult to figure, and I also think the solutions relied heavily on constant factor... overall, didn't really like the problems.
•  » » 3 weeks ago, # ^ |   +13 I also think problems are pretty standard and boring. Maybe somehow they only received some data structure problems. some narcissismI got all the problems accepted in less than 2 hours. I believe I spent <10min on thinking and ~20mins are spent on constant optimizations. The time limits are pretty tight indeed.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Wow, I admire your skill in constant time optimizations! Actually, I've solved problem A and C in 66 minutes total. And I spent only another 9 minutes to get solution of problem B. And rested 25 minutes. Then, for another 100 minutes, I considered about existence of solution of which faster than $O(n^{1.5} \times \alpha(n))$ because I thought it is risky to implement, but my thinking failed. After that, I implemented + debugged my code and it took 40 minutes. I used remaining 60 minutes completely on constant optimization of it. However, I only got 27 points on problem B. I'm really bad at constant optimization...
•  » » » » 3 weeks ago, # ^ |   0 Is there anyone who spent 1hr for squeezing segment-tree based approach on A? Funny that I did, and succeeded XD
•  » » » » » 3 weeks ago, # ^ |   0 Why did you need a segment tree on A? I think the common solution is finding period and sweepline.
•  » » » » » » 3 weeks ago, # ^ |   0 I plotted (x mod T, y) in a plane and calculated the area of union of rectangles. After contest I found out I was stupid, as usual.
•  » » » » » 3 weeks ago, # ^ |   0 I tried, but after several hours I only got to 30 points :/
•  » » » » 3 weeks ago, # ^ |   0 I've met the same problem: solving A and C, spending loads of time on the O(n sqrt(n) alpha(n)) algorithm of B and getting only 27 points eventually.By the way, will the contestants' source codes be made public?
 » 3 weeks ago, # |   +6 Some whining about resultsMy score is 100 60 100...I've implemented sqrt decomposition in O(Qsqrt(Q)alpha), but got 60 with TL :( Asking for help to find a problem in the solutionMaybe someone can help me to find the exact reason why is my code working slow? ^^Here it is: https://pastebin.com/risLgsfs
•  » » 3 weeks ago, # ^ |   +8 I think std::set is a bad idea.. I know it's linear time, but still. I implemented everything on array, maintaining it sorted by merging original edge set with an updated edge set ($O(B\log B + M)$). I didn't saw anyone who skipped this optimization and pass.Also for me, optimal bucket size was 800.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   -7 Thank you, it made it really better! Ok, now it works faster, but just 73...
•  » » » » 3 weeks ago, # ^ |   +3 My code. It's quite ugly, sorry about that.
•  » » 3 weeks ago, # ^ |   +2 I think you can change your 'microdsu' to a dfs.
•  » » » 3 weeks ago, # ^ |   -8 dfs and bfs are not working good because of the vectors that i need to use to create graph
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 You can use linked list to store edges. That worked fine for me.Also, you can just open a array of n*sqrt(n) and use it as 'vector's to store edges.
•  » » » » » 3 weeks ago, # ^ |   -8 Thank you, now it works faster, but i can't get 100 :( (check reply to the koo_saga comment)
 » 3 weeks ago, # |   +5 Where can i see standings?
•  » » 3 weeks ago, # ^ |   +3
 » 3 weeks ago, # |   +8 I'm too old to take part in APIO now but I'm really curious as to what's the solution for B... no one I know managed to solve it. Can someone who has solved it give me a rough outline of the solution? Thanks :)
•  » » 3 weeks ago, # ^ |   0 It is a standard square root decomposition problem. Brief Outline: Divide the queries into $\sqrt{Q}$ buckets. For each bucket, note that at most $\sqrt{Q}$ edges have weights unchanged within the bucket. Sort all the queries by decreasing weight in the bucket, and maintain a DSU while adding edges that are not modified within the bucket one by one. For edges with weight modified in the bucket, we iterate through all of them and then add them to the DSU if they are usable, then remove them after we are done with a query (so $\sqrt{Q}$ additions and removals per query). This can be implemented with DSU with rollbacks.
•  » » » 3 weeks ago, # ^ |   +4 "DSU with rollbacks" — How is this implemented, with still $O(\alpha(n))$? (Providing some vague idea is fine)
•  » » » » 3 weeks ago, # ^ |   +6 Use dfs instead of dsu here.
•  » » » » 3 weeks ago, # ^ |   +3 Create a stack to record what you merged, then for every "undo" operation you can just look at the top of the stack and undo the changes (by reassigning values in the dsu array) and then pop from the stack. It's at most $O(\log n)$ since you still merge small to large (but don't do path compression).
•  » » » » » 3 weeks ago, # ^ |   0 I understand — I guess this would not fit in the time constraint for this specific problem though.
•  » » » » » » 3 weeks ago, # ^ |   +8 My solution using this method passed, though with some slight optimizations (I kept getting 71 at the beginning).
•  » » » » 3 weeks ago, # ^ |   +3 You don't need to use "dsu with rollback". In each block, you can add edges that covers the whole block from big to small using dsu. And to answer each query, just simply connect the extra edges on this query and run dfs. (When connect these edges you can just regard a connected component as a single vertex with weight.)Using "dsu with rollback" will bring a log.
•  » » » » » 3 weeks ago, # ^ |   +3 The same as TLE.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Ya I didn't realize this before TLE pointed it out, since that was the first thing that came to mind. Thanks.
 » 3 weeks ago, # |   +6 when will they be available for practice?
 » 3 weeks ago, # |   +18 How many points have gold medals?
•  » » 3 weeks ago, # ^ |   +12 There is a discussion regarding the (unofficial) result/cutoff in this thread.
•  » » » 3 weeks ago, # ^ |   0 Thanks！
 » 3 weeks ago, # |   +7 https://apio2019.ru/results/official-contest/ shows 104 medalists with 201 official contestants. Either I am not good at math or the APIO 2019 committee has clearly violated the regulations they provided themselves.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 I believe this is the solution for cut-off the team leaders selected:Get temporary standings according to top 6 people for each country, get medal cutoffs, include all participants that are tied, and give medals according to cutoffs calculated before, standings will contain more than 6 people for some countries
 » 7 days ago, # |   0 Hi! any news for testdatas? niyaznigmatul PavelKunyavskiy
•  » » 7 days ago, # ^ |   +10 Did you mean pashka? I'm not a judge here :)
•  » » » 7 days ago, # ^ |   0 Thanks for the correction :)