The first round of the IIOT (International Informatics Olympiads in Teams) is starting tomorrow, November 14th 2022! The open contest will be 3 hours USACO-style, starting from 17:30 CET, and ending 27 hours after that. In the meanwhile, you can enjoy our teaser below and try to guess the next eight problems from the hints :)
This contest, of a lower difficulty level than the IOI, is intended for teams of 4 contestants from the same high school (check this post for further details). However, everyone is welcome to participate to the open contests!
If you want to participate, you must:
- Visit the contest website: https://mirror.squadre.olinfo.it/
- Click the link "register", fill out the form and then click on the register button and then "back to login"
- You can now log in with the same username and password you used to sign up
- If the login is successful you will be ready to participate, just wait for the contest to start! (and maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
- When the contest starts, you will see a red button. Click it when you want to start your 3 hour time window!
- The ranking for each contest will be available at https://mirror.squadre.olinfo.it/ranking/ after the start of each contest
- The tasks will also be available for training in https://training.olinfo.it/#/tasks/ few days after the contests
- Good luck and have fun!
We hope that you will join us or encourage your students to do so!
Tommaso Dossi (on behalf of the Italian IIOT organizers)
I don't see the teaser, how would we know which number police is this time?
Police 8 solution: Treap of DSU of FFTs of CHT of LIS
wise mystical teaser has come!
All hail the wise mystical tree! (Sumtree)
All hail thank god subtask 2 wasn't included in subtask 3
Sorry if I broke cms
Since contest is over, can someone share implementation of monopoly problem please?
How is it over? it still has a couple more hours to go
I thought it was over back then. Sorry
what happened with sumtree?
It's just a virtual tree problem?
Based
I meant what happened with the scoring, my nlogn code got wrong answer in the last subtasks during the contest so my team ended our time frame with 70 points on it, but a few hours later it got updated to 100
Was going to ask this. Many teams' scores suddenly changed. Maybe there was something wrong with tests?
Wait nlogn? I only came up with $$$O(2^5n\log{n})$$$
Well yes I also have the 2^5 coefficient, but it's pretty much a constant
Can you explain how you solved the problem please?
centroid decomposition crying in the background
centroid decomposition is also a good approach
small to large crying in the background
Could you share your code using small to large?
I don't know if I have the correct code saved, because of the re-evaluation, but I can share the solution.
You can make a DS with the functionality of:
Adding/removing a number with some weight
Finding the total weight of the numbers that are not coprime to some number
These 2 operations (removing is the same as adding negative weight) can be done in
~2^5 + log(num)with the inclusion-exclusion principle, because we're only interested in the distinct prime factors of the number (use sieve forlog(num)) and there is a maximum of 5 of those (2*3*5*7*11*13barely passes3e4)Instead of adding the values of the path between two non-coprime numbers, let's add the values of the paths from the root to each of them — this can be done by querying and adding each node to the DS with the weight of the path from the root to it. now our only job is to remove the 2 excess paths from the root to the lca (lowest common ancestor) and add the value of the lca.
So we only need to count for each node in how many pairs it is the lca, which can be done by simply querying each subtree of it in the DS and then adding it to the DS, and in the end querying + adding the node itself.
Now the small-to-large part: The only catch is that re-adding and re-removing the subtrees each time is costly (
O(N^2)), so instead we won't "clean" the largest subtree after recursively calling it (we'll make sure to call it last) and using the partially filled DS to skip doing the querying + adding for that subtree. —O(nlog(n))Note: when I don't specify the weight when adding/removing I mean +/- 1 (same as counting non-coprime numbers)
If you have questions about any specific part I would be more than happy to explain in more detail or send parts of the code, like sharing the code of the DS.
So we only need to count for each node in how many pairs it is the lca, which can be done by simply querying each subtree of it in the DS and then adding it to the DS, and in the end querying + adding the node itself.
could you explain this part in more detail please?
We calculated the sum, but it's wrong because for every pair we also add the path from the lca to the root twice (except for the lca, which we added once, but it's an easy fix as well). So we need to correct it by subtracting for each node the sum of the path from the root to it, times the amount of pairs with that node as their lca, times 2.
Now we have a new problem, counting pairs with a specific lca. for some lca, all pairs will be from different subtrees of it, so we can add the subtrees one by one, and for each subtree before adding finding the sum of the DS.cnt() for all nodes in that subtree. Here's a general code of this query+add operation for clarity:
As a little implementation detail, note that for
add_subyou can add adifparameter which you'd set as 1 for adding and -1 for removingSo for each subtree we would add
cnt_sub(subroot,lca)to the result and then calladd_sub(subroot,lca). and in the end we can also addDS.count(value[lca])to the result for pairs where one of them is the lca itself.Later we will need to call
add_sub(lca,parent,dif=-1)when backtracking the recursive call, so the small-to-large optimization is not doing that for the largest subtree, instead using it as the first subtree wherecnt_sub()is still 0I wonder if there is an $$$O(n(2^5+\log{n}))$$$ solution hmmm