### maroonrk's blog

By maroonrk, history, 5 months ago,

We will hold AtCoder Regular Contest 150.

The point values will be 300-500-500-700-800-1000.

We are looking forward to your participation!

• +119

 » 5 months ago, # |   +5 Hope to solve three problems. And not get too happy just by solving two problems.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 I only got 1 :(. Should have got C but not good with graphs/dijkstra's. :( :(
•  » » » 5 months ago, # ^ |   0 i also got 1 :(
•  » » » » 5 months ago, # ^ |   0 :( :(
 » 5 months ago, # |   +11 Hope you all have a good time in this competition!
 » 5 months ago, # |   +8 I just wonder who aaa1a is.
•  » » 5 months ago, # ^ |   +8 His speed is just unbelievable.
•  » » 5 months ago, # ^ |   0 He is dmga44
 » 5 months ago, # |   -28 Couldn't solve any :( I think A was too case-heavy for me
•  » » 5 months ago, # ^ |   0 A was really straightforward. Very little case work. (Actually 0). #include void solve() { int n, k; cin >> n >> k; string s; cin >> s; int tcnt0 = count(all(s), '0'); int tcnt1 = count(all(s), '1'); int cnt0 = 0, cnt1 = 0; for (int i = 0; i < k - 1; i++) { if (s[i] == '0') cnt0++; else if (s[i] == '1') cnt1++; } int ans = 0; for (int i = k - 1; i < n; i++) { if (s[i] == '0') cnt0++; else if (s[i] == '1') cnt1++; if (cnt0 == 0 && cnt1 == tcnt1) { ans++; } if (s[i - k + 1] == '0') cnt0--; else if (s[i - k + 1] == '1') cnt1--; } cout << (ans == 1 ? yes : no) << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; cin >> t; while (t--) { solve(); } return 0; } 
•  » » » 5 months ago, # ^ | ← Rev. 4 →   0 yeah... my code was a massive lump of spaghetti with probably 7~8 if-else statements, each containing a line of yes or no. :( I guess I get lost into nowhere more often on atcoder than on cf
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 it happens. :)I got 3 WAs because I wrote s[i - k] instead of s[i - k + 1]. But it was worth it, in the end.
 » 5 months ago, # |   +26 Is it only me that feels that Atcoder problems are more simple and interesting (even hard ones), as compared to codeforces.
 » 5 months ago, # |   0 I don't understand why this code for A doesn't work. I believe I have the same idea as the editorial, although I implemented it badly, or maybe did something wrong, but I can't find it even after searching for an hour. Could someone help me out?
•  » » 5 months ago, # ^ |   0 Counter example14 20??0
•  » » » 5 months ago, # ^ |   0 Thank you so much. I am so dumb for not realizing this.
 » 5 months ago, # |   0 please explain solution of B
 » 5 months ago, # | ← Rev. 2 →   0 This is the code for starr(https://atcoder.jp/contests/arc150/submissions/35550331), which I think is TLE. #include using namespace std; #define int long long signed main(){ int t,a,b,i; cin>>t; while(t--){ cin>>a>>b; if(a>=b) cout<=1;i--){ //i是倍数 int x=b/i+(b%i!=0); //cout<
•  » » 5 months ago, # ^ |   +8 I write this solution during contest too and it passed. Maybe the tests are too weak.
 » 5 months ago, # | ← Rev. 4 →   +8 Can problem — A Continuous 1 https://atcoder.jp/contests/arc150/tasks/arc150_abe solved using DP ?? I tried dp but it couldn't get correct solution .My idea :Each '?'has 2 options to be replaced using '0' or '1' .I formed this recursive logicidx -> index , leftOne == K — alreadyPresentOne '1'I'm asking from isPossible() , whether it's possible to have K consecutive 1's And for each True I increment counter , If counter > 1 return False. bool isPossible(int idx, int leftOne) { if (idx >= n && leftOne != 0) return 0; if (leftOne == 0) { //Check if K consecutive 1' possible and ++counter if (pfxSum[i] == tar) { ++counter; return true; } } return false; } while (idx < n && s[idx] != '?') { ++idx; } bool way1 = false, way2 = false; // if (dp[leftOne][idx] != -1) // return dp[leftOne][idx]; if (s[idx] == '?') { s[idx] = '1'; way1 = isPossible(idx + 1, leftOne - 1); s[idx] = '0'; way2 = isPossible(idx + 1, leftOne); s[idx] = '?'; } return (way1 || way2); } But when I turned it into dp[index][leftOne] , I couldn't do I realise it's because let say I've 00?1???10? if at one instance like 001111010? dp[7][0] == No but then for 0001111100 dp[7][0] == YesPlease verify if it's dp solvable or not ??
 » 5 months ago, # |   0 Can someone please explain how to solve problem B. How the range of X is fixed : X=max(0, ⌊(B−1)/k⌋+1−A) ? How to obtain this ⌊(B−1)/k⌋+1−A ? Is it through calculus ?
•  » » 6 weeks ago, # ^ |   0 these lower bounds are obtained by applying conditions of x>=0 and y>=0 in obtained equations
 » 5 months ago, # |   +8 I think my solution to problem C is a little weird, and I am not sure if it is correct (although get AC). I use normal bfs, starting from node-1, but with k stages, where k is just the input in the statement. For each stage, we keep visiting all the unvisited nodes until we meet nodes-x, where a[x]=b[stage]. During the process, if node-n has been visited, then the answer is no, otherwise is yes.By the way, problem B uses the sqrt-technique, which is somehow similar to problem B in ARC139. I feel very lucky that I realize this quickly.
•  » » 5 months ago, # ^ |   0 That is essentially the same as editorial, just another way how to implement 0/1 bfs.The values in array $d$ are euqivalent to the amount of iterations before you discovered some value in your case.
•  » » » 5 months ago, # ^ |   0 Thank you for your kind reply. But after reading tutorial, I find that solution is more reasonable and formed in a systematic way, while mine seems a little bit unclear.
 » 5 months ago, # | ← Rev. 2 →   0 How I "solved" B: First, notice that ans is at most min(b-a,a) so you can bruteforce for all x<=1 mil and this handles all cases with a<=1mil. For the remaining cases(a>1mil): Suppose b+y = z(a+x), bruteforce for all z <= b/a and y<=b/a. Both loops are <= 1000 runs I think this is WA solution but weak tests. If it happens to be correct, can anyone show proof?
•  » » 5 months ago, # ^ |   +5 Why would it be wa? also if you know z you don't need to bruteforce y. This is my solution
•  » » » 5 months ago, # ^ |   0 I thought there might be a case with y>1000, thats why. I guess the idea is AC, when you get y with math.
•  » » 5 months ago, # ^ |   0 Will you please explain more what you are doing in remaining cases(a>1mil) part? I am unable to understand only by watching your code.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 I've made it easier to understand: Here
 » 5 months ago, # |   0 Why is BFS wrong for problem C https://atcoder.jp/contests/arc150/submissions/35553054
•  » » 5 months ago, # ^ |   0 maybe 01bfs
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Let me know if you got the reason why using BFS is not working.Thanks in advance
•  » » » 5 months ago, # ^ |   0 because if n is 9, and a road is 1 -> 4 -> 8 -> 9, and another is 1 -> 3 -> 6 -> 7 -> 5 -> 8 -> 9, and 4 8 is b[2], b[3],3 6 7 5 in not in b[], then BFS with get dp[9] = 4,but the answer should be dp[9] = 2
•  » » » » 5 months ago, # ^ |   0 4 8 is b[2], b[3],3 6 7 5 in not in b[]can you elaborate this part
 » 5 months ago, # |   +13 In editorial of problem D — tester's solution: "Not only bad vertices but also good vertices can be chosen.". Why doesn't that change the result?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +24 The outcome of the random variable $X_v$ depends on status of the parents of $v$. That is, it just needs to 'keep track' of the parents to know when $v$ has become good and it needs to stop performing operations. This intuition explains why we don't care about the operations which pick something apart from $v$ and its parents. Those operations neither change the state of $v$'s parents, nor do they directly change the value of the random variable (which would only be affected when we pick precisely $v$). A similar argument holds for not caring about whether we pick good or bad vertices. Even if we pick a good vertex, it was already coloured black from earlier. So the status of none of the parents change. We know we didn't pick $v$ itself, since the process would have already stopped if $v$ was good beforehand. This operation doesn't affect the value of the random variable as well. And so we're free to consider them as valid moves.
 » 5 months ago, # | ← Rev. 2 →   +1 I was lost while reading editorial of B. Someone save me please.
•  » » 5 months ago, # ^ |   +3 We want $B+Y$ to be a multiple of $A+X$, i.e., $B+Y = k(A+X)$ for some positive integer $k$.If someone told you what $k$ you need to use, then part 1 of the editorial tells you how to find $X$ and $Y$ such that $X+Y$ is smallest. We have, $Y = kX+kA-B$ and $X+Y = (k+1)X+kA-B$. To minimize $X+Y$ is then same is to minimize $X$, because $k$, $A$, and $B$ are fixed. We choose smallest $X$ such that $Y \ge 0$ (recall $Y = kX+kA-B$). This value is $\max(0, \lfloor\frac{B-1}{k}\rfloor + 1 -A)$ (convince yourself of this). Part 2 then tells you that for $k \le \sqrt{B})$ you can just compute this value, and the number of different values of $\lfloor\frac{B-1}{k}$ for $k > \sqrt{B}$ is at most $\sqrt{B}$. For example, if $B = 101$, then $\lfloor\frac{B-1}{k}\rfloor$ can take values $9, 8, 7, 6, 5, 4, 3, 2, 1$ if $k\ge 11$. So you compute minimizing $X$ using $k = 1, 2, \ldots, \sqrt{B}$ first then compute minimizing $X$ using $\lfloor\frac{B-1}{k}\rfloor = 1, 2, \ldots, \sqrt{B}$. (Maybe try 2 or 3 more values if I am missing some constants.)
•  » » » 5 months ago, # ^ |   +1 Thanks for your explanation!
•  » » » 5 months ago, # ^ |   0 Y = kX + kA -B Having Y >= 0, I get X >= floor((B-kA)/k) How do I reach X >= floor((B-1)/k) + 1 -A from here?
•  » » » » 5 months ago, # ^ |   +1 This is just a hacky shortcut. You want $kX + kA - B \ge 0$, i.e., $X \ge \frac{B}{k} - A$. There are two cases.Case 1. $\frac{B}{k}$ is an integer, so we can set $X = \frac{B}{k} - A$. You can see that, in this case, $\frac{B}{k} = \lfloor\frac{B-1}{k}\rfloor + 1$ (because $\lfloor\frac{B-1}{k}\rfloor = \frac{B}{k} - 1$).Case 2. $\frac{B}{k}$ is not an integer, so the next higher integer is $\lfloor\frac{B-1}{k}\rfloor + 1$.
•  » » » » » 5 months ago, # ^ |   +1 Thank you! This shall help me in the future as well
•  » » » » » » 5 months ago, # ^ |   0 You're welcome!
•  » » 5 months ago, # ^ |   +1 I also couldn't understand the editorial of B. Then I looked at more editorials and found a better explanation from the official video editorial:For B + Y = k(A+X), there are two approaches to find X + Y: Approach 1: Enumerate X from 0 to A-1, we can get a value of X + Y for each case and keep the minimum. Approach 2: Enumerate k from 1 to B/A, we can get a value of X + Y for each case and keep the minimum. Note the range of X and k, when A is extremely small or extremely large, either Approach 1 or Approach 2 can be very slow. Therefore, pick a value of sqrt(B) to determine to only use the faster of the 2 approaches.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +1 Much cleaner! Just to add a tiny elaboration: if $A \le \sqrt{B}$, then Approach 1 uses $\le\sqrt{B}$ iterations, and when $A > \sqrt{B}$, Approach 2 uses at most $B/A \le\sqrt{B}$ iterations.Edit: Actually, reasoning for why Approach 2 only checks until $B/A$ is not clear to me.
•  » » » » 5 months ago, # ^ |   +1 IF you go over the range, you will notice the Xs and/or the Ys computed by the formula can become negative. Negative Xs or Ys are not allowed.
•  » » » » » 5 months ago, # ^ |   0 Oh, so there is more argument needed. I had previously misunderstood it.
 » 5 months ago, # |   0 In problem B, he has not used the $\sqrt{N}$ algorithm but something else. Can someone explain his code please
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 In int r = (b + (a + x) - 1) / (a + x); and int y = r * (a + x) - b;, he is just computing smallest y for a given x. If r==1, then basically a+x has become greater than or equal to b, i.e., the resulting r is going to be the same for subsequent xs, i.e., the subsequent ys are going to get only larger, so we break. Sorry to be incomplete and I am not 100% sure, but I suspect in x = (b + (r - 2)) / (r - 1) - a;, he is trying to get the next x value which will not give the same r value as for this iteration. My guess is that this way, you would try at most $O(\sqrt{A+B})$ values for x by a similar calculation as in the editorial.
 » 5 months ago, # |   0 My approach to C is different from that of the editorial (and I don't know whether it is correct):I computed some data by hand, and found out that for all the data given in the problem, I saw this feature: SpoilerIf we disconnect all the points that say, $a_x=b_i$ (we want to find that $x$), from the graph.Then, if there still exists a path from 1 to N, then the answer is No.Because first if there exists a path not containing either of the $x$, it is no, and second, if there is another order, it will be connected also.Maybe we can use DSU to compute the answer? Or maybe this "feature" is wrong? Or is this right?
 » 5 months ago, # |   0 I have a small confusion regarding simple path Simple path doesn't mean it is the shortest path right , it means path which doesnot contains two or more same vertices Then in the sample test case 2 of problem C why we are not considering path (1,2,3,4,5) ?
•  » » 5 months ago, # ^ |   0 In path every consecutive vertex is connected directly by an edge. 2 and 3 do not share an edge
•  » » » 5 months ago, # ^ |   0 2 and 3 have an edge right ? This is the sample test case 2 :5 5 3 1 2 2 3 3 4 4 5 2 5 1 2 3 5 2 1 3 23rd line of the test case represents there is an edge between 2 and 3
•  » » » » 5 months ago, # ^ |   0 If we consider path (1,2,3,4,5) then yes the condition will be satisfied but the problem statement says that condition has to be satisfied for all simple paths. It is not satisfied for (1,2,5)
 » 5 months ago, # |   0 #include #define int long long using namespace std; signed main() { int T; cin >> T; while(T--) { int N, K; cin >> N >> K; string S; cin >> S; int freq = 0; map> Freq; int ques = 0; for(int i = 0; i < K; i++) { freq += (S[i] == '1'); ques += (S[i] == '?'); if(freq + ques == K) { Freq[freq].push_back(i); } } for(int i = K; i < N; i++) { freq += (S[i] == '1'); ques += (S[i] == '?'); freq -= (S[i - K] == '1'); ques -= (S[i - K] == '?'); if(freq + ques == K) { Freq[freq].push_back(i); } } if(!Freq.size()) { cout << "No" << endl; } else { auto itr = Freq.rbegin(); if((*itr).second.size() == 1) { cout << "Yes" << endl; } else { cout << "No" << endl; } } } return 0; } Since 2 out of 26 test case has been showing WA. Which edge cases I'm missing, please help me to find out?
 » 5 months ago, # |   0 Can anyone helped explain this code of Problem B? https://atcoder.jp/contests/arc150/submissions/35534665