Блог пользователя GuralTOO

Автор GuralTOO, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Oh no contest is clashing with Codechef Lunch time :(

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to apply DP+BITMASK for C problem?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    My really easy solution:

    http://pastebin.com/4v3sZvk7