nitin12384's blog

Atcoder Beginner Contest 278 Discussion blog.
By nitin12384, history, 17 months ago, In English

I didn't find any announcement blog for ABC 278.
So I posted this .

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

Comments Comments (27)
| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was intended solution for F, bitmask dp? I did that and got WA for 4 cases.

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

    Yes. I got it accepted using bitmask DP. My code

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

    One thing you gotta take care is that how are subproblems dependent on each other.
    Lets say if you can choose string indexed $$$x$$$ after choosing string $$$i$$$. Then
    $$$dp[i][mask]$$$ is dependent on $$$dp[x][mask2]$$$, where
    $$$mask2$$$ is a value with one lesser number of set bits that $$$mask$$$.
    Hence doing a bottom up DP is hard.

    I did it using top down memorized DP.

    Edit — I just realized that you also did memoized DP.

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

    Probably, but I did a complete search dfs. Here is my submission: https://atcoder.jp/contests/abc278/submissions/36632674

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

      One new test case was added after contest. It causes TLE if I don't do memoization. I don't have the test case, but if I use the following test case on your submission, your submission will TLE too.

      Spoiler
      → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

hint for E?

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

    Say you have answer of $$$(k,l)$$$
    What information do you need to keep track of, to be able to get answer of $$$(k, l+1)$$$ from answer of $$$(k,l)$$$?

    Also Notice that $$$N \le 300$$$. So keeping frequency count isn't that hard.

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

    Move the block ($$${w * h}$$$) in the following form.


    -------------
            |
-------------
|
-------------
            |

    so on..

    You can move the block by one step in $$${O(max(w, h))}$$$ so you may solve this problem in $$${O(H * W * max(h, w))}$$$. use map or unordered_map for counting distinct element and update them in each step of block.

    → Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve G ?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    ++

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

    My solution(but didn't manage to get AC for now) was to consider two cases: when $$$l \neq r$$$ then first player always has winning strategy erasing cards in the middle to obtain two equal parts and then having the symmetric strategy. When $$$l = r$$$ then you can solve the problem in quadratic time using grundy values.

    Edit: got AC now.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C++ 20 when ?? I literally wrote C++ 20 built-in features today and erased realising atcoder doesn't have C++ 20

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

I think it was a good round. (Got a good +ve delta, so can't nitpick lol).

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would you please review my G? I think my implementation is super good...

https://atcoder.jp/contests/abc278/submissions/36653750

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Query forces

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a Newbie. I used list of unordered-map for problem C. I was getting a runtime error for like last 10 test cases. Can anyone help? My code

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

    Since you are creating a vector of size n(which in the worst case can be 10^9), you encounter an RE verdict.

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

      Oh. Brother, So is this happening beacause the possible max size of a vector is less than (10^9). And Can you please suggest an alternative....

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

        To be on the safe side, I would suggest using vectors when the max size is maybe less than 10^7. Or better use arrays. Whatever you use, the size should be at max 10^7. Sometimes 10^8 might work, but I haven't encountered any problem which needs such a huge array. In this problem, you can use a map. And another suggestion will be not to use unordered maps with the default hash method. Those are hackable. Ordered maps will do the job for you.

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          Thanks you brother. Using map instead worked.

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

        I created　a map　that maps　pairs　to　a　Boolean　value. （or you can create your own hash table) https://atcoder.jp/contests/abc278/submissions/36639240

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

          A map mapping to bool is just like a set.

          → Reply