GuralTOO's blog

Coci round #3
By GuralTOO, history, 7 years ago, In English

I am glad to remind you that this Saturday will be held 3-rd round of Croatian contest.
I strongly recommend you to participate, as coci is one of the best IOI style competitions.
Hope for discussion of the problems after the round!

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

»
7 years ago, # |
  Vote: I like it +45 Vote: I do not like it

6 tasks, 3 hours, no-feedback
IOI style!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    PROBLEMS (the main part of each contest) are IOI stylish

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Oh no contest is clashing with Codechef Lunch time :(

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Just reminder.
2 hours left, enjoy the contest and try to have fun ;)

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to apply DP+BITMASK for C problem?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    my solution:

    the state is dp[mask] where mask value is at most (2^n)-1 (I started counting form 0)

    in this mask if the iTH bit was ON this means the iTH glass is not empty.

    if the number of the turned on bits is k the answer is zero.

    or you will apply two "for" loops on this mask..

    let's say:

    for(int i=0;(1<<i)<=mask;i++)

for(int j=0;(1<<j)<=mask;j++)

    Now if the iTH bit or the jTH bit is off or i equals to j ,don't do any thing.

    or you will try to pure the water from iTH glass to the jTH glass and the answer is a[i][j]+dp[mask-(1<<i)]

    where a[i][j] is the cost to pure the water from the iTH glass to the jTH glass and you will turn off the iTH bit because the iTH glass in empty after that

    my code

    I put factor "on" in the solve function because I don't want to count the turned on bits everytime (this doesn't effects on the memorization because every mask has unique number of turned on bits).

    I hope this information is useful :D

    sorry for my bad English.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems to me something like (2^n)*(2^n). How about 2^n*n^2 solution?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's actually n*n*(2^n) because you will do the operation for every mask once and every operation is O(n^2) and the number of masks is 2^n :D

        (Note that I used an array to store results so I don't have to calculate the answer for every mask more than one time).

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My really easy solution:

    http://pastebin.com/4v3sZvk7

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      What did you mean, when you wrote

      vector < int> bit; // bits of our num?

      Is num, i?

      → Reply