Hello Codeforces community!
I would like to announce Algoge Round 4. The contest will be held on Sunday 10th May at 15:00 UTC.
Algoge is site created by students of the Faculty of Computer Science during quarantine days in Serbia, based on the DMOJ platform. As there are no onsite contests these days, we decided to organize $$$5$$$ online rounds mainly for participants from Balkan. In the first three rounds, the tasks were only available on Serbian. Easier tasks were prepared by us and harder ones were taken from Moscow Workshop competitions. We had between 50 and 150 participants per round.
This is the first round fully created by us. For that purpose we decide to translate the tasks into English (Serbian version will be available too) and invite all of you to compete. Round will have $$$5$$$ or $$$6$$$ tasks and lasts $$$3$$$ hours. Tasks will be slightly harder than usual CF Div 2 round.
All task are prepared by ICPC team RAF Penguins: Pajaraja, milisav and allllekssssa.
Also I would like to thank DuX and all other students from my faculty for maintenance the platform.
As some labels on the site are in Serbian, everything that you need to know for doing contest is the following:
After registration on the site you need this link for the round (currently round is in upcoming part). In the moment when round starts you can join — there is no extra registration for the round. English statements will be in a visible place.
See you on Sunday!
UPD 1: Scoring for the round: $$$30 - 50 - 70 - 80 - 120 - 140$$$
English versions of statements will be at the top of each problem. As I didn't mention before, scoring system is same as AtCoder system with full feedback, only you are getting $$$10$$$ minutes for wrong submission.
UPD 1: Contest starts in $$$30$$$ minutes.
Let the best win ;)
I'm glad that there is an English version as well.
i couldn't find it. where?
There will be English versions only for the tasks of round 4. All other tasks are on Serbian and currently there are no plan to translate them.
Is it rated? allllekssssa
Yes it is rated. I believe this is your chance to become red :)
Thank you for believing in me. I’ve been following you on Codeforces since you made that epic contest about GukiZ
Oh yeah, I remember that... epic
Can you add the time zone like (+7 +7.5 + 8) for easier seeing the date & time ? :(
In the editorial for the problem Triangle Sort, how do you show that the parity of the number of inversions remains the same when you perform the operation?
After each swap parity of inversions is changed — our operation = two swaps, so parity stay same after one operation. To prove that parity is changed after each swap you can do next:
Suppose you should swap $$$a_l$$$ and $$$a_r$$$, and let's say that in interval ($$$l, r$$$) there is exactly $$$k_1$$$ elements smaller than $$$a_l$$$ and $$$k_2$$$ elements bigger than $$$a_r$$$, also suppose $$$a_l < a_r$$$. Before swap you have $$$(*)$$$ $$$k_1 + k_2$$$ inversions in the interval. Now you have $$$(r -l -1 - k_1) + (r -l - 1 - k_2)$$$ + 1 (last one is for inversion $$$a_l$$$ and $$$a_r$$$. So, now at total you have $$$(**)$$$ $$$2 \cdot (r - l -1)$$$ — $$$k_1 - k_2 + 1$$$ inversions. $$$(*)$$$ and $$$(**)$$$ are different parity. On similar way you can show for $$$a_l > a_r$$$.
Thanks for the explanation, it is clear now.
Is there a way to see other submissions! I got frustrated by a wrong answer in a further testcase and have no idea what was wrong! watching others' submissions will be helpful!
You have problem with overflow, change $$$dma$$$ vectors to long long and code will pass.
About other users submissions — people from platform decided that is bad way for learning. Better way "read editorial and than try to implement alone" (not my decision). Here is problem that editorials are on Serbian — but from other side I am glad to help you at any way and question.
Oh thank you so much for checking my solution! Indeed it works with long long! But why is that? how is the value is supposed to exceed 10⁵? it is within the range of int! Can you please help in which case I get an overflow?
The thing that result can be $$$long long$$$, and you have something like $$$dma \cdot (dma -1) / 2 $$$. $$$dma$$$ is $$$int$$$ and whole result can be $$$long long$$$. That is overflow — you should cast before multiplication.