TEST CASES BOI 2023 - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hello everyone, I participated in BOI 2023 and I am very disappointed about the competition. In day one's first problem(Car Race) some N*log(N)*log(N) solutions with small memory optimizations passed for 100%, while others got only 58% despite the fact that N could reach 10^6. The second task of day 1(Weights) had a subtask for O(Q*depth) with depth smaller than 30 that was supposed to get someone 24 points (for the other subtasks a faster solution was needed and someone had to adjust the way he stored numbers as they could reach values up to 2^depth which could turn out to be really large). However, naive solutions for ONLY the third subtask with __int128 could earn 91 points. Moreover, many solutions for the problem passed the last subtask(the no further constraints one) but they lost points from the first one. How is this even possible? Last but not least, in the last task of day 2 (Aliens), O(N^2) solutions that required N^2 memory passed K=1 and N <= 10^5. How were all these problems not prevented from the Scientific Committee and from those who tested the problems? Were the testcases never checked and solutions for subtask never tested? All these problems are the ones that make students refrain from participating in Olympiads and I hope that Problem Seters will be more careful in the future.

Комментарии (32)

Написать комментарий?

welleyth

13 месяцев назад, # |

+22

I am the author of Car Race and Super tree. Ask me anything.

→ Ответить

stefdasca

13 месяцев назад, # ^ |

+11

When will you publish the tasks, together with the test cases and the solutions?

I know you're not the only one responsible for this, but maybe you have an answer to this question.

+14

Hi, I personally have plans on hosting the mirror on eolymp in the following days. After the mirror I think everything will be published

TimDee

-7

Why

+25

I tried to do my best with these problems...

NemanjaSo2005

What is the model solution for Car Race?

Initially, model solution for Car Race was small-to-large in O(Nlog^2N). However, I saw that this problem could be solved in linear time. I used an idea of compressing the tree.

Let's look at vertexes on the same depth, obviously other cars will not bother us
Let's consider these vertexes important. Any other vertex could be important if it has more than one important son.
It could be seen, that we do not really need non-important vertexes — let's remove them.
Let's run the dfs simulation of the game. How many vertexes would it travers? Let $$$|D_i|$$$ be the number of the vertexes on the level $$$i$$$. Thus, we can say that on the next level there are at most $$$\frac{|D_i|}{2}$$$ vertexes. Thus, we can upper bound the number of vertexes we traverse by $$$|D_i| + \frac{|D_i|}{2} + \frac{|D_i|}{4} + ... = 2 \cdot |D_i|$$$.

As we can see, this is linear time from the number of vertexes. Thus, the total time complexity would be $$$\mathcal{O}(N)$$$, to be more precise it is somewhat $$$3 \cdot N$$$.

valeriu

+42

Hello. The Nlog^2 solution you described is not Nlog^2, but Nlog if you would calculate complexity correctly. Maybe this should relieve some of the pain :)

Yes, I thought the same when I could not find a countertest for the small-to-large solution some days before the contets. I found out that here the size of the set in the subtree depends not on the size, but on the depth. I am not really sure how to calculate this complexity now, but I am sure that it is much less than $$$\mathcal{O}(N\log^2)$$$. Thus, the only thing I could do is find the test where it gives ML...

Although, I would agree that there were some dependencies problems during the contest as the last subtask passed and pre-last did not. I had a talk with organisers some days before the contest and got informed that it is impossible to set dependencies on cms. Thus, I saw no other way than adding similar tests to different subtasks, but it would significantly slow down the system during the contest, as it would have to test more tests for a single submission.

← Rev. 2 →

+23

Brief appendix on the complexity of small to large when dealing with depths

Mamedov

12 месяцев назад, # ^ |

← Rev. 4 →

Don't know the exact version of CMS that's been used during the Olympiad, but in general CMS supports sort of subtask dependency. It is possible to include same test in any subtask using regex in the scoring section based on the codenames of the tests. You don't need to create the same test several times. ~~But I'm not sure whether~~ Now I am pretty sure it runs a particular test only once if it's included in many subtasks this way. Just checked the evaluation of one such task.

mychecksdead

I really wonder, why O(NKlogN) doesnt pass bitsize<20 subtask on super trees, I mean isnt it only 4e8 operations?

It is ok if to look on TL, but I think it would give ML, as you support K Segment Trees and each of them has Nodes -> NK memory, which could be a bit too much.

I am sorry, just checked — I have a solution O(NKlog) that passes 6th subtask (bitsize < 20).

Thats little weird then, idk what would be the case for this kind of situtation in olympiads. It would be unfair to other participants to their solutions to be rejudged, idk maybe just unlucky day. But it would be a little better if they give me gold, since I had only 6 points difference on front but 30 on behind. Little unfair contest, I can say maybe,also there were 4 seg tree tasks...

Full solution for super-tree does not require any data structures except of vectors and arrays.

Oh my wrong, but shouldn't I get points on subtask 6? (I didnt, I have only 34)

I think all results should be final after the contest end. If you did not get score for some subtasks it is just your poor implementation skills. That is the sad truth. I had the same experience after CEOI 2023.

If you think that this is a mistake of the judge — you can somehow appeal the decision of the judge... (never had such an experience)

Yea, yea it was my skill issue

Also what was the intended, I still dont know, thanks.

Intended solution:

Calculate the array $$$f$$$.
Calculate power and superpower
For each update start a dfs in the vertex $$$v$$$. If you did not update the value in this vertex — do not update the remaining subtree. Otherwise, update value $$$f$$$ in the vertex, update power and superpower and run dfs into sons.

This works in O(NlogA) and has about 60 lines of code.

Oh, really.....

If you are interested, I could tell a little story.

When I just came up with this statement I came up with segment tree beats solution. I implemented it. That was 350 line cancer that worked in O(NlogAlogN), but it worked. Then I faced a question — can I do it faster? Can I get rid of that logN? At that time I understood that I do not really need segment tree and I could easily access the node instead of accessing it after going down in a seg tree. After that, I increased A to 2^60 and N to 1e6.

That is the story.

I think 2^60 was unnecessary.

erray

I had a similar solution used same number of operations with euler tour and DSU's. I was pretty sure that this idea would be faster in practice so I didn't even bother to try your solution, but that idea failed miserably. We had a sweet debate with a guy behind through clarifications on how mean the TLE is, although they were pretty insistent on saying it was irrelevant to the problem. I'm pretty sure my code would pass with +0.5 TLE. Sad thing is, I think same applies for problem C too.

← Rev. 3 →

I thinked that organizers would've noticed it with the number of clarifications I've sent, but amount of indifference they've shown to the minuscule amount of swearing I did through my 60 submissions shows that they probably didn't even examined my codes.

That's quite nice. I was wondering how to find the numbers to update in O(1) because first thing I did was Euler tour to make tree into an array. Then I did segment tree beats.

Your solution is much nicer and easier to implement.

franfill

+16

Fun fact: during the competition I coded an $$$O(N\ logA\ logN)$$$ solution that got me 100 points (I believe due to weak testcases)

Oh... I heard that if you submit to some problems in the first 1 hour, it gets -1 second in time LOL. Also if your country is Turkey you get auto +1 second in Supertrees ajsdahsdjksfldsjdklfgfksjl and if your name is Cengiz you get auto +37 seconds in every problem. (I passed NKlog^2N in C, and he got TLE with Nlog^2N.)

Essa2006

+43

Well, there are some mistakes and weak test cases but we can’t hide the fact that in general it was an amazing olympiad and we gained a lot from it, hopefully year by year it will get better.

As a participant I really enjoyed trying to solve the problems and meeting with other students that are interested in informatics.

Tbh looking at all onsite olympiads I've been at (including IOI2023) this year's BOI seems the best one, i absolutely loved and enjoyed the event, ~~not as much as the tasks though~~

~~P.s. task were actually pretty decent, it's just my personal skill issue :D~~

wxhtzdy

+29

same

Блог пользователя KALARRY