The International Olympiad in Informatics is one such event that we all look forward to, not only as players but also as spectators. An annual competition that began in 1989 in Bulgaria, the IOI has risen from its humble beginnings to become one of the largest worldwide competitions for school students that tests their skills in programming and problem-solving.
CodeChef is conducting the next replay of the Indian IOI Training Camp. This contest is the second among the three replays that we plan to conduct. There will be three challenging problems and a five-hours to solve them.
The authors of the round are:
- Kushagra Juneja (kushagra1729), Praveen Dhinwa (PraveenDhinwa), Sreejata Bhattacharya (AnonymousBunny) and Zi Song Yeoh (zscoder)
The testers panel consists of:
- Rajat De (rajat1603), Sampriti Panda (sampriti), Sidhant Bansal (sidhant), Arjun Arul (arjunarul), Swapnil Gupta (born2rule), Sreejata Bhattacharya (AnonymousBunny), Animesh Fatehpuria (animeshf), and Arjun P (Superty)
How to participate? It’s simple, just register at CodeChef if you haven’t done so already, and check out the details below! We hope that you will find the contest very interesting. We wish that you will enjoy the round as much as we enjoyed preparing this round.
Start Date: Saturday, 21st July, 2018 at 19:00 HRS (IST)
You may check your timezone here.
Contest Link: www.codechef.com/IOITC182
Good luck!
Cheers,
Team CodeChef
Will you provide editorials? Did you publish the previous editorials(Day 1)?
You can see here
How to solve problems Coin Denominations and Exact Walks?
Calculate the DP for up to like 10^6. You can prove that there exists an optimal solution where you use less than 100 coins for each type except for one type, so we can do something similar to linear interpolation.
https://www.codechef.com/viewsolution/19294575
Notice that if there is a walk of length l from u to v, there is also a walk of length l+2 from u to v. In order to make G' as "disconnected" as possible, we will only assign 1 or 2 to a[i].
We will try to choose a node u such that no other nodes in G' can reach u. If any 2 neighbors of u are also neighbors, then they form a triangle and isolating u is impossible. Otherwise, we set a[v] to 2 for all neighbors of u and 1 to the rest of the nodes.
https://www.codechef.com/viewsolution/19296047
How can you prove that (Coin Denominations)?
Let coin i be a coin with the smallest w[i]/i. If there are >=i occurrences of the coin of value j, we can exchange i coins of value j with j coins of value i without increasing the total cost.
Aha, now I get it. So do we really need to calculate DP to 106 or is 104 enough? And I am also wondering if you can use __int128 at Codeforces and IOI?
I don't really know the maximum DP that we have to calculate. The maximum sum of all coins except for the main coin is around 99*(100*101/2) ~ 5e5, so setting the upper bound to something like 6e5 will definitely work.
__int128 for IOI: https://mirror.codeforces.com/blog/entry/60623
__int128 doesn't seem to compile on CF.
Although I kind of overkilled this problem since __int128 isn't actually required, just check some other solutions.
Thank you very much.