Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### chokudai's blog

By chokudai, history, 3 months ago, ,

We will hold AtCoder Beginner Contest 146.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +35

 » 3 months ago, # |   +11 It would be better if someone post English editorial of AtCoder contests!
•  » » 3 months ago, # ^ |   +3 Although they do not have English editorials officially ( yet!, hopefully they will in the future ), but Geothermal usually writes his solutions in English, and posts them shortly after the contest. So you should read them, it is very helpful.
•  » » » 3 months ago, # ^ |   0 Oops same answer at the same time. xd
•  » » » » 3 months ago, # ^ |   0 Haha, yeah. I was surprised too. And it seems, we both gave each other a +1 xD.
•  » » » 3 months ago, # ^ |   0 Thank you for the information! :)
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 There will be a blog after the contest by Geothermal sharing his/her approach in English.
•  » » » 3 months ago, # ^ |   0 Thank you too for the information! :)
 » 3 months ago, # |   +19 I've written an English editorial: https://codeforces.com/blog/entry/71701
•  » » 3 months ago, # ^ |   +17 I have done so as well. :)https://codeforces.com/blog/entry/71699
•  » » 3 months ago, # ^ |   +5 Thank you!You guys are saviors.
 » 3 months ago, # |   0 For problem C Can someone tell me what is wrong in my code I got WA in one test case Your code here...import math n,m,x = map(int,input().split()) #print(n,m,x) for i in range(1,25): k = (x - m*i)//n #print(k,i) if k<0: print((x-m*(i-1))//n) break if k==0: print(k) break if int(math.log10(k))+1 == i: print(min(10**9,k)) break 
 » 3 months ago, # |   +8 Anybody else found this contest somewhat easier than a normal beginner contest?
•  » » 3 months ago, # ^ |   +6
•  » » » 3 months ago, # ^ |   0 Very nice of you to say that ! Thanks! :D
•  » » » » 3 months ago, # ^ |   +1 That's not me, it's Yoda.
•  » » » » » 3 months ago, # ^ |   0 So I would say — "Thank you Master".
 » 3 months ago, # |   0 can Somebody please explain to me more Problem E ? I have read both of the tutorials and still don't get it. Thank you
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 HintFirstly, we store prefix sums, to get range sums in O(1). Now, notice that $[L, R]$ interval is good if $Pref(R) - Pref(L-1) \mod K = R - (L-1)$.This means, $R - (L-1) < K$ — (1)Also, rearranging a bit we get, $Pref(R) - R$ = $Pref(L-1) - (L-1) \mod K$So, we make a new array ( let's call it F ), such that $F(i) = Pref(i) - i$.Then, number of required intervals ending at index $i$ are number of $j < i$ such that $F(j) = F(i)$, and $i - j < K$ SolutionLet's make a map, storing frequencies of elements of array $F$.Moving from left to right, at index $i$ you will have information from $i-K+1$ to $i$ (sliding window). Then just add frequency of $F(i)$ at each index.My submission ( I have done the same thing, but from back to front ).
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thank you very much. I got it now :))
•  » » » 3 months ago, # ^ |   0 I have a question for the last line of the hint. Shouldn't it be F(j) = F(i) mod K?
•  » » » » 3 months ago, # ^ |   0 Ah yes. I was calculating everything modulo $K$. I forgot to explicitly write it.Actually, the main jist is that, you have to do all calculations modulo $K$, the only inference was that you should only consider subarrays ( or contiguous subsequences, as questions states ), of length at most $K-1$.
•  » » 3 months ago, # ^ |   +3 You should explain what you do understand and don't understand, and/or what step in someone's editorial you can't follow.(Otherwise there's nothing stopping someone else from posting yet another explanation that you don't understand, which isn't helpful to them or you.)
•  » » » 3 months ago, # ^ |   0 Thanks for the reply. I am not saying you haven't explained well. I just coudn't understand and I know it's my fault cause apparently it's too easy for many people. I get the part where there has to be Pi≡Pj but what I don't get is how to get all the pairs verifying this condition ?? and about the condition you montionned do you mean that the maximum number of elements should be less than K ?
•  » » » » 3 months ago, # ^ |   0 Thanks for explaining what steps you wanted to know more about!Let me try to explain those parts. Let's solve the reduced problem: given an array $p$, find all pairs of equal elements that are at most $K$ apart. To do that, let's count all the pairs $(i, j)$ (with $i j - K$ such that $p_i = p_j$ (which we can do efficiently using a hashmap to keep track of the counts for each $p_i$ in the past $K$ indices). If we add up all these numbers (loop over each $j$), we end up with the total number of pairs. This is because every pair $(i, j)$ is counted exactly once, when we count all the valid $i$s for that $j$.Does that help?
•  » » » » » 3 months ago, # ^ |   0 This comment made all the difference to me. Thank you for your Time and effort. I now got it perfectly. :))
 » 3 months ago, # | ← Rev. 2 →   0 Hi all, for problem F, I did a (too simple) implementation. It obviously fail, but the problem is that I am not able to understand why it should return a shortest path that is not the lexicographically minimal. This is my code: ll solve() { int N, M; cin >> N >> M; string s; cin >> s; int counterOnes = 0; // here I just filter if there is no solution for (int i = 0; i < s.length(); ++i) { if (s[i] == '1') { ++counterOnes; if (counterOnes >= M) { cout << -1 << endl; return 0; } } else { counterOnes = 0; } } string out; int index = s.length() - 1; // if I reach this, there is a solution for sure while (index > 0) { // loop from the biggest step to 1 for (int j = std::max(0, index - M); j < index; ++j) { if (s[j] == '1') continue; out += to_string(index - j); out += " "; index = j; break; } } out.pop_back(); std::reverse(out.begin(), out.end()); cout << out << endl; return 0; } I cannot identify a negative pattern to proof that this fails :( Is there a way to download/see the testcases, after the ATCoder contest terminates?Thanks a lot for any help
•  » » 3 months ago, # ^ |   0 std::reverse(out.begin(), out.end()); You actually reverses the "string", not the numbers. For example, "1 12" becomes "21 1" from your code, but it should be "12 1". Then the rest of your solution is correct.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thanks my saver!!! I feel so dumb! Sure I didn't realised it, I thought the entire solution was wrong, while instead I did a so crazy error... Replaced the out string with a stack, printing directly in the right order, and everything worked. Unfortunately too late for the contest. Next time... :) thanks again