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

Please Help with dp problem?
Автор BanazadehAria, история, 5 лет назад, По-английски

Hi can anyone tell any dp approach to this?

Problem link==> http://codeforces.com/contest/1151/problem/B

I can think of a O(n*m*2^10) dp But it will not pass.

Thanks in advance.

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

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

Auto comment: topic has been updated by BanazadehAria (previous revision, new revision, compare).

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

a non dp approach

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

    The whole point of this post was to find a DP approach, and you missed that

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

    Not dp but amazing :(

    → Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    But instead of this its just enough to proof(Not a really hard one) That if we have a1^...^an = 0 We can be sure that ==> a1^...^x !=0 (x != an)==>

    1-If a1^...^an-1 is 0 then x^0 = x (Correct)

    2-else==>

    We know the fact that any number is ^ itself is zero.

    And its the only number that if we xor it it will get zero.(2)

    So now we know that an equals to a1^.....^an-1 and also we know that (x!=an)==>(3) So a1^...^an-1 ^ x is not zero because of (2) and (3).

    Please Correct Me if i have any mistake in my proof.

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

You can write dp such as you think but for each bit separate.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    what you mean "for each bit seperate"

    dp[i][mask] ==> The maximum we can get using [1..i](repesant rows) and the mask is the result of the xor of the numbers that we have.

    And i think the update is O(m).

    And now were not going through any bits please clarify that thank you.

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

      dp[i][bit][bitonoroff] answer it is possible to get no zero after i-th row. For row if arr[i][j]&(1<<bit) if dp(i+1,bit,bitonoroff^1) dp[i][bit][bitonoroff]=1 else if dp(i+1,bit,bitonoroff) dp[i][bit][bitonoroff] When you on last row you return bitonoroff. If you find that at some bit dp[0][bit][0] is 1 than you find an answer, and it is easy to know which column for each row you must get

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

        Thanks, 1-What is the time complexity ?

        2-And Please Compelete Your state statement what is usage of bit and bitonoroff?

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

          1 time complexity is n*10*2*m 2 Main idea is that dp[i][mask] answer is exist such columns for each row that xor of all is non zero. We want to change mask to some another state. Answer is exist if for some bit(one of 10) (we change matrix such that matrix[i][j]=bool(arr[i][j]&(1<<bit))) and we for each bit have mask with two states.

          → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My dp approach: For each row and for each possible "xored" value try to combine it with every item of the next row. Return the first value which is not zero. My sub: 56398315

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

    Why You pass ? I think test cases are weak because You run in O(n*m*1024(Possible Mask Value) ==> (500*500*1024) ?

    → Ответить