BanazadehAria's blog

Please Help with dp problem?
By BanazadehAria, history, 5 years ago, In English

Hi can anyone tell any dp approach to this?

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

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

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

a non dp approach

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

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

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

      I edited the comment, thanks for pointing that out

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

    Not dp but amazing :(

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

    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.

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

      I think you have the same proof

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

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

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

    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.

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

      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

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

        Thanks, 1-What is the time complexity ?

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

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

          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.

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

            so we loop through 10 bits and make a dp for all of the 10 states?

            → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply