I didn't find any announcement blog for ABC 278.
So I posted this .
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I didn't find any announcement blog for ABC 278.
So I posted this .
Name |
---|
Was intended solution for F, bitmask dp? I did that and got WA for 4 cases.
Yes. I got it accepted using bitmask DP. My code
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.
Yes, I did top down DP as well. Don't know where it's going wrong :)
https://atcoder.jp/contests/abc278/submissions/36653923
I think max(ans, dp...) should be the max(ans, !dp...) atleastOne is unnecessary.
Suggestion: curplayer is unnecessary. Easy to cause chaos. Just let dp(mask) returns whether a player will win if she/he faces the mask and it is her/his turn. For example
https://atcoder.jp/contests/abc278/submissions/36632991
Probably, but I did a complete search dfs. Here is my submission: https://atcoder.jp/contests/abc278/submissions/36632674
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.
hint for E?
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.
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.
How to solve G ?
++
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.
C++ 20 when ?? I literally wrote C++ 20 built-in features today and erased realising atcoder doesn't have C++ 20
gcc9 does not support c++20.
What are built-in features of c++20 which can be helpful in cp. I am very much interested in learning about that. Can you share them or is there any blog or something?
https://codeforces.net/blog/entry/96040?#comment-851241
I think it was a good round. (Got a good +ve delta, so can't nitpick lol).
Would you please review my G? I think my implementation is super good...
https://atcoder.jp/contests/abc278/submissions/36653750
Query forces
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
Since you are creating a vector of size n(which in the worst case can be 10^9), you encounter an RE verdict.
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....
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.
Thanks you brother. Using map instead worked.
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
A map mapping to bool is just like a set.