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 (animesh_f), 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?

Coin DenominationsCalculate 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

Exact WalksNotice 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 10

^{6}or is 10^{4}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://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.