### awoo's blog

By awoo, history, 5 years ago, translation,

1221A - 2048 Game

Idea: Roms

Tutorial
Solution (Roms)

1221B - Knights

Idea: BledDest

Tutorial
Solution (PikMike)

1221C - Perfect Team

Idea: Roms

Tutorial
Solution 1 (BledDest)
Solution 2 (PikMike)

1221D - Make The Fence Great Again

Idea: Roms

Tutorial
Solution (Roms)

1221E - Game With String

Idea: Roms

Tutorial
Solution (Roms)

1221F - Choose a Square

Idea: Neon

Tutorial
Solution (Ne0n25)

1221G - Graph And Numbers

Idea: BledDest

Tutorial
Solution (BledDest)
• +63

| Write comment?
 » 5 years ago, # |   0 Very sorry gor noob question, but in G why is F(0.1) number of independent sets in graph?
•  » » 5 years ago, # ^ |   +8 $F(\{0, 1\})$ is such a coloring that no pair of vertices colored $1$ are connected by an edge. So the subtask is to count the number of ways to choose vertices to color them $1$ in such a way that no pair is connected by an edge. And that's the definition of an independent set.
•  » » » 5 years ago, # ^ |   +5 Yeah, I figured it out by myself after some time... I think you should include this explanation in the editorial though, it's not immediately obvious.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +11 Meh, I think it's fine. Editorials are not supposed to be immediately obvious for everybody.
 » 5 years ago, # |   0 I still don't understand Why it is not beneficial to increase the length of some board by three or more.... (Problem D) Can anyone help???
•  » » 5 years ago, # ^ |   0 because there is no need. even if u increase by 2 or 1 or 0 u can de different from ur neighbors
•  » » 5 years ago, # ^ |   +13 Assuming $a_i = a_{i-1}$. We can increase $a_i$ or $a_{i-1}$ by 1.If we decide to increase $a_i$ by 1, it doesn't change anything before, so the Fence is still great up to now.If we decide to increase $a_{i-1}$ by 1, it can equal to $a_{i-2}$ and break the Fence's greatness. In this situation, we can continuously increase $a_{i-1}$ by 1 (now, it increased 2 units) or increase $a_{i-2}$ by 1.That's the reason why we should increase every $a_i$ at most $2$.
•  » » » 12 months ago, # ^ |   0 what if increasing ai-2 by 1, ai-3 becomes equal to ai-2
•  » » » 4 weeks ago, # ^ |   0 yeah same doubt , what if now a(i-2) becomes equal to a(i-3) and so on ?
•  » » 4 years ago, # ^ |   0 3 case structure theorem
•  » » » 4 years ago, # ^ |   0 Can anyone tell me why am I getting a TLE for test case 16 even though I am doing the problem in O(N).85221066
•  » » » » 4 years ago, # ^ |   0 Using fast input with your code gets accepted. 85483073
 » 5 years ago, # |   0 can someone explain 5th question . I dont think explanation is correct , how can u convert fourth type segment into 2nd type segment and what about the cases in a>=2*b
 » 5 years ago, # |   0 Can someone give me the proof for problem B?
•  » » 5 years ago, # ^ |   0 Let's play chess. :v BTW, all black cells $(i,j)$ in a chess board have the same parity of $i+j$ and different from all white cells.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I did it using a bfs. Similar to bipartite colouring
•  » » » 5 years ago, # ^ |   0 I do the same with dfs :))
 » 5 years ago, # |   0 Hold on, what is OR-convolution mentioned in G? I couldn't google it.
•  » » 5 years ago, # ^ |   0 Google sum over subsets DP, that's the thing you need.
•  » » » 5 years ago, # ^ |   0 Yah I solve G using that, just wondering what is OR convolution
•  » » » » 5 years ago, # ^ |   0 I remember seeing it here and here but idk if it's really needed in the solution.
•  » » » » » 5 years ago, # ^ |   0 Thanks a lot. As I know curiosity always leads me to sth more to learn
 » 5 years ago, # | ← Rev. 2 →   0 In problem A , how to prove that if sum of numbers other than numbers greater than 2048 is greater or equal to 2048 then answer will be Yes ?
 » 5 years ago, # |   0 Very weak test cases for A even my wrong code got accepted
•  » » 5 years ago, # ^ |   +5 ?your code is correct
 » 5 years ago, # |   0 can someone tell me what if (c + m + x - 2 * mid >= mid) means in problem C ?
•  » » 5 years ago, # ^ |   +6 If $mid$ teams are formed, then $mid$ coders are already taken and $mid$ mathematicians are also taken. That leaves us with $(c - mid) + (m - mid) + x$ people to fill the empty spot in each of the $mid$ teams. So if that condition if true, then there are enough people to form at least $mid$ teams.
 » 5 years ago, # |   +3 In Problem E, when we consider segments of type 4, where len >= 2*b, how can we say that Bob can always convert it into a segment of type 2? If (a+b) <= len < 3b, if Bob makes his move, the segment will become type 3
•  » » 5 years ago, # ^ |   0 When $len \geq 2*b$, Bob can always get a segment of type $2$ by saving the $b$ right most places and then choosing his segment. Eg. if $b=2$ and $len=8$, $\ ........ \rightarrow\ ....XX..\$ Now he can use the right most place when Alice doesn't have a move left.
 » 5 years ago, # | ← Rev. 4 →   0 Problem F ,if I submit my code with GNU C++17 ,I would Wrong answer on test 2, if I submit my code with GNU C++14,it was Accepted.Could someone tell me why? my code: 60964098 60962460. Sorry for my poor English.
 » 5 years ago, # |   0 In 5, how are we sure that 2b>=a when it is only mentioned that a>b?
•  » » 5 years ago, # ^ |   0 We don't. If a <= 2b then there is just no segment of the third type.
 » 5 years ago, # | ← Rev. 2 →   0 need a proof for problem "A" solution please
 » 5 years ago, # | ← Rev. 4 →   0 There are accepted solutions (e.g. 60854023)for Problem C (Perfect Teams) which are just$min \{c, m, \left \lfloor{\frac{c+m+x}{3}}\right \rfloor\}$Could someone please prove (or explain the idea behind) the formula?
•  » » 5 years ago, # ^ |   0 By definition, each team consists of a coder, a mathematician, and exactly three people. The resource with minimal availability decides how many perfect teams you can build.
•  » » » 5 years ago, # ^ |   0 i can understand how minimal availability of c & m decide the outcome but what does (c+m+x)/3 here signify? can you please explain? _/\_
 » 5 years ago, # |   0 haizz i am bad at implementation algorithm. That's why i rarely do well in the contest :< . Can someone give me advice on this matter, pls !! sorry for my poor english :D
•  » » 5 years ago, # ^ |   0 Read and understand good codes of the questions you are doing... try to remember loopholes and learn to make your code short and simple. Also each line of the code should be important that is your code shouldn't be redundant.
 » 5 years ago, # |   0 Can E be solved like this? I am not sure! :3First take segment length of dots, then sort them and obviously ignore the lengths smaller than b. Then we declare vector < pair > info which saves what happens if alice starts, if bob starts when there are first i lengths only.Now in these sorted lengths, take the first one and save who wins if there is only that first segment and alice starts the move, if there is only that last segment and bob starts the moveThen we iterate i from 1 to size of segment lengths array. For i-th element, we decide who will win if alice starts, if bob starts the move when there are only first i segments. We decide considering the i-th length and the information from info[i-1]......and save it in info[i]......**sorry for my explanation.....i suck at explaining :(
 » 5 years ago, # |   0 problem A mathematical induction proof: (1) if the sum of the not larger than 1 elements is greater than 1, the numbers can merged into 1. obvious. (2)suppose the sum of not larger than 2^(k-1) elements is greater than 2^(k-1), the numbers can be merged into 2^k. Then if the sum smaller than 2^k elements of is larger than 2^k , the numbers can be merged into 2^k.
 » 5 years ago, # |   0 in D what is the proof that time complexity of the recursion won't be large I did not get how the dp is exactly working
•  » » 5 years ago, # ^ |   0 because all boards will be increased by no more than two.
•  » » » 5 years ago, # ^ |   0 Yeah I know but there's a for loop with calc function with three possibilities x=0 x=1 x=2 so it's o(3^n) complexity isnt it ? Or if statement is making it o(n) but why
•  » » » » 5 years ago, # ^ |   0 No it is 3*3*n
 » 5 years ago, # |   0 My recursive DP solution for problem D is timing out , It times out in the test case where answer is always 0 , the weird thing is that it times out even after I hardcode the case where number of elements are always 1! can someone please check and let me know where I can optimize ? Thanks ! https://mirror.codeforces.com/contest/1221/submission/61071469
•  » » 4 years ago, # ^ |   0 I hope your problem is already solved by now, but I'm writing it for other people!Use fastio. I was having the same problem! Write this inside main(): ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
•  » » 4 years ago, # ^ |   0 Great Code!!!
 » 5 years ago, # | ← Rev. 4 →   0 Can anyone please help me in problem D. I am getting wrong answer on teset case 2. I am using tabulation approach instead of memoization. Here is also Link to my submission. Thanks in advance #include using namespace std; #define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long int ll; int main(){ SPEED; ll t; cin>>t; while(t--){ ll n; cin>>n; ll a[n]; ll b[n]; for(ll i = 0; i< n; i++){ cin>>a[i]>>b[i]; } ll dp[3][n]; dp[0][0]=0; dp[1][0]=b[0]; dp[2][0]=b[0]*1ll*2; for(ll i = 1; i <= n-1; i++){ for(ll j = 0; j< 3; j++){ ll temp = LONG_MAX; for(ll k = 0; k < 3; k++){ if(a[i]+j!=a[i-1]+k){ temp = min(temp, dp[k][i-1]+b[i]*1ll*j); } } dp[j][i]=temp; } } cout<
•  » » 5 years ago, # ^ |   0 just use temp=1e18 insted of LONG_MAX
 » 5 years ago, # | ← Rev. 2 →   0 I don't understand the formula of DIV2C c + m + x — 2 * mid >= mid__ Please help...
•  » » 5 years ago, # ^ |   0
 » 5 years ago, # |   0 Why am I getting a TLE in this solution to the D. Link: https://mirror.codeforces.com/contest/1221/submission/61306295
•  » » 5 years ago, # ^ |   +3 write this in your codeios_base::sync_with_stdio(false); cin.tie(NULL);
 » 5 years ago, # |   0 I can't understand editorial for problem F. What do you store in the segment tree, also how do you initialize it?
 » 5 years ago, # |   0 In problem E if 2b
 » 4 years ago, # |   0 Can anyone tell me the botton up solution of question D? Link is ->Question D
•  » » 4 years ago, # ^ |   0 Because both the tutorials have top down method
•  » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 Bottom UP dp solution for C (make that fence great Again): link https://mirror.codeforces.com/contest/1221/submission/76082735
 » 4 years ago, # |   0 can we solve E using grundy numbers?
•  » » 4 years ago, # ^ |   0 I guess no since grundy theorem requires a symmetric game and now a isn't equal to b.Maybe there is a generalization of the theorem but idk.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yeah i tried to get accepted with grundy numbers, but it didn't work.
 » 10 months ago, # | ← Rev. 2 →   0 Can someone please explain why is this code for problem D getting TLE'd? Thanks in advance. https://mirror.codeforces.com/contest/1221/submission/216444244