PraveenDhinwa's blog

By PraveenDhinwa, history, 6 years ago, In English

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.

Contest Link: www.codechef.com/IOITC182

Good luck!

Cheers,

Team CodeChef

  • Vote: I like it
  • +42
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you provide editorials? Did you publish the previous editorials(Day 1)?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problems Coin Denominations and Exact Walks?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Coin Denominations
    Exact Walks
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can you prove that (Coin Denominations)?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            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.net/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 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              Thank you very much.