### PraveenDhinwa's blog

By PraveenDhinwa, history, 6 months ago, ,

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:

The testers panel consists of:

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.

Good luck!

Cheers,

Team CodeChef

•
• +42
•

 » 6 months ago, # |   0 Will you provide editorials? Did you publish the previous editorials(Day 1)?
•  » » 6 months ago, # ^ |   +1 You can see here
 » 6 months ago, # |   0 How to solve problems Coin Denominations and Exact Walks?
•  » » 6 months ago, # ^ |   +13 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
•  » » » 6 months ago, # ^ |   0 How can you prove that (Coin Denominations)?
•  » » » » 6 months ago, # ^ |   +13 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.
•  » » » » » 6 months ago, # ^ |   0 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?
•  » » » » » » 6 months ago, # ^ |   +13 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.
•  » » » » » » » 6 months ago, # ^ |   +10 Thank you very much.