Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### awoo's blog

By awoo, history, 3 months ago, translation, 1766A - Extremely Round

Idea: BledDest

Tutorial
Solution (BledDest)

Idea: BledDest

Tutorial
Solution (awoo)

1766C - Hamiltonian Wall

Idea: BledDest

Tutorial
Solution (awoo)

1766D - Lucky Chains

Idea: BledDest

Tutorial

1766E - Decomposition

Idea: BledDest

Tutorial
Solution (BledDest)

1766F - MCF

Idea: BledDest

Tutorial
Solution (BledDest)  Comments (78)
 » ratttttttttttttttttttttttttttttttttttttttttttttttttttttting plz
•  » » LOL, why so many downvotes.
•  » » •  » » I had a dream, not being newbie when attending Turkish Junior National Olympics in Informatics but because of the slowest rating update ever,i can't
 » 3 months ago, # | ← Rev. 2 →   When will the ratings update? :(
 » It is the first time that I will have a oringe name. I really want it could update rating as quickly as possible.plz
•  » » i feel for you :(
•  » » It's the same for me...plz
•  » » me too, it so slow
•  » » » me too too
 » 3 months ago, # | ← Rev. 2 →   I didn't read B properly and thought that $n$ could take on values other than the length of the input. I thought I needed to implement a complicated LCP+Suffix Array method than ran in $O(n*log(n)^2)$ to greedily compute the minimum number of operations needed to produce the resulting string, which I wasn't able to do during the contest.Here's my solution which actually computes the minimum number of operations: 185016918
•  » » Didn't it occur to you that you were solving a Div2B and not a Div1B? xD
•  » » Ayoooo, Chill... Nice Work man tho :"D
•  » » Same happened with me but couldn't solve the problem therefore will see your solution
•  » » Us moment
 » In A why 184918763 got TLE?
•  » » That's why you are grey.
•  » » » now is your comment:)
•  » » » » lol
•  » » Because you are iterating from 1 to n in each case. So the time complexity would be O(t*n) which would give TLE. You have already calculated if each i is extremely round or not. Just construct a prefix sum array which would tell how many extremely round numbers are less than i. Then you can answer each case in O(1).
•  » » 3 months ago, # ^ | ← Rev. 2 →   Your algorothm takes n (n = the given integer) iterations of the loop for each test case. At worst, your algorithm will have to do $999 \ 999$ iterations of the loop for each test case. A test set can contain up to $10^4 = 10 \ 000$ test cases. Your algorithm might need to do $10 \ 000 \cdot 999 \ 999 = 9 \ 999 \ 990 \ 000 \approx 10 \ 000 \ 000 \ 000 = 10^{10}$ iterations of your loop. C++ can do around $10^8$ operations on average in one second. Each iteration of your loop contains 4 fast operations: i<=n, f[i]==1, ans++ and i++. Even though these are simple and fast operations, c++ can't execute that many of them in under 3 seconds.
•  » » After finding round number you are checking every number for each queries that's why, what you can do is store round number only in array then try binary search that will reduce the time complexity.
•  » » finding law is better than exhaustion,maybe 184926907 is useful to you
•  » » 184922508I used the log() function to do the whole problem in O(t).
 » For D, we can consider only prime divisors of $y-x$ because to minimize the answer, if it's possible to get $\gcd(x,y) \neq 1$ for a certain composite $d$ s.t. $d|(y-x)$, it's definitely possible for some prime $p < d$ and we can reach multiples of $p$ at least as soon as we reach a multiple of $d$.
•  » » its all code, man.
 » 3 months ago, # | ← Rev. 2 →   state transition graph for 1766E([i] represent for a sequence end with i) •  » » This state transition is sufficient enough to arrive at the intended solution.
 » Nice round. I think D and E are the best problems I've ever seen.
 » Video Editorial of Problem C : Hamiltonian Wall Link : https://youtu.be/p4-bUeGfs48
 »
 » E is simply brilliant.
 » 3 months ago, # | ← Rev. 2 →   The complexity given for B is wrong. It is O(1). There are 26^2 possible unique 2-letter strings. Any string longer than 26^2+1 will have at least one repetition due to the Pigeonhole Principle.
•  » » You have to read the string, so it is $O(n)$. And even if you read it character by character, in order to go to the next test case, you still have to read the whole string.
 » I still don't understand why we need all the prime divisors of each number in C. Don't we only need the smallest prime divisor to know the earliest point when the chain will stop?
•  » » Yeah correct, knowing the smallest is sufficient
•  » » » 3 months ago, # ^ | ← Rev. 3 →   No, take the example (4,19), y-x = 15 and the smallest prime factor is 3, however the smallest k that ensures gcd(4+k,19+k) = 3 is k = 2, but with a prime factor of 5, we find the smallest k ensuring gcd(4+k,19+k) = 5 is k = 1. That's why we run over all prime factors and take the minimum k for each.
•  » » » » actually knowing the smallest is suffice because you can iterate x /= least[x] then update the answer, which is a bit faster. My solution during contest: 184938325
•  » » » » » Yeah I solved it that way too but I took the OP's question as "why can't you just use the smallest prime alone"
•  » » » » » » Yeah techincally we are considering the smallest prime alone
 » if anyone wants the O(1) solution for A, here it is :)184929564
 » What will be the expected rating of the first 3 questions?
 » when will the rating be updated???
•  » » Perhaps the program of calculating rating change has crashed and CF stuffs are calculating manually
•  » » » what, manually???
•  » » » » I cannot come up with any other idea why rating has not been updated yet now
•  » » » » » manually? are you sure there are that many of them during the war?
•  » » » » » » What does war have to do with this
•  » » » they even rolled back my rating of last to last contest for some reason D:
 » Why this submission passed problem 2? Surely it's complexity is O(n^2) Your text to link here...
•  » » There are only 26^2 = 676 patterns of two successive characters.It means that this loop will end within at most approx.700*|s| times, and is enough fast to pass.This is called Pigeonhole principle.
•  » » » I think any string longer than 704 will always be YES, and I guess the string below might be the longest one that can be NO. •  » » because the test data is not large,you should notice "The sum ofnndoesn't exceed2⋅1052⋅105over all testcases."
•  » » Hey, one place scanf is used for taking input int len; scanf("%d",&len); In other place cin is used for taking input string s1; cin >> s1;is there any significance for it as in improves time or memory consumption or anything?Thanks.
 » The contest which made me master! 139 is a happy number.
•  » » It made me blue! (perhaps back to cyan tommorrow)
 » Problem- E:- Can anyone tell, which case they where missing while they where getting WA at test case 16.expected: '1476747', found: '996573'How to correct it.Thanks in advance :)
 » 3 months ago, # | ← Rev. 2 →   The B solution is wrong: Try this testcase: - t=1 - string='abcdabef' - n=6, - the answer is yes according to solution but it's wrong becuase: - 4 operations for 'abcd', - then 5th operation for copying and appending 'ab' string, - then 6th and 7th operation for 'ef', - so number of operations exceed n.
•  » » n must be equal to length of string
•  » » » My stupid mistake of not reading the question properly.
 » 3 months ago, # | ← Rev. 2 →   in problem D why we put p-1 in [ r = min(r, ((x + p — 1) / p) * p — x); ] it should be r = min(r, ((x + r) / p) * p — x) ; why he put r = p-1 ??
 » 3 months ago, # | ← Rev. 2 →   Can someone explain this block in D plz? int r = INF; for (int p : getPrimes(d)) r = min(r, ((x + p - 1) / p) * p); cout << r - x << '\n'; Why r = min(r, ((x + p - 1) / p) * p);? This means k equals (p-1)?UPD: Ok, guess I got it. So by doing ((x + p — 1) / p) * p we get some number j, which is: p|j x <= j <= x + p — 1
•  » » i didn't understand why
•  » » » So we need a number that is the closest to x from right side (or can be same x). Also, this number should contain some factor of number (y-x), because x+k and y-x should contain some common factor. How do we do it?By r = min(r, ((x + p - 1) / p) * p); we get some value j which is j >= x and j <= x+p-1. Why does it work? Tbh, I don't have some formal proof. Just look at examples. Why r = min(r, ((x + p - 1) / p) * p); and not r = min(r, ((x + p) / p) * p);? Look at example like this: x = 10, p = 10. Without (-1) you will get j = 20. With (-1) you will get j = 10. j = 10 is correct, because it is closer to x (x = j = 10, k = 0). OR: you could use r = min(r, ((x + p) / p) * p);, just check before it if (gcd(x, y — x) != 1). If gcd(x, y — x) != 1, then print 0 immediately.
 » My O(1) solution to problem A: 185166119
 » 3 months ago, # | ← Rev. 2 →   The Solution for Problem C is wrong. (Maybe)For Test Case:13BWBBWBThe output should be "NO" but it's giving "YES".
•  » » 3 months ago, # ^ | ← Rev. 4 →   well my approach was a dfs, and I think the code is pretty self explanatory. It works for this test case. 185170837I realize that should have participated when I upsolved most of the questions :cry：
•  » » You are violating the requirement:Additionally, he wants each column to have at least one black cell, so, for each j, the following constraint is satisfied: c1,j, c2,j or both of them will be equal to 'B'.You have input data, which is not possible for this task. Your middle column doesn't have any black cells.
•  » » » oh I didn't read carefully！Thats why dfs is not needed. Thanks for clarifying that.
 » D used SPF(smallest prime factor) concept to find the prime factorisation of y-x.
 » awoo's editorial is awesome in the sense it shows us how we can approach the problem ..
 » can anyone pls explain DP approach of problem C ?
 » 3 months ago, # | ← Rev. 2 →   A different solution for problem A  int n; cin >> n; int sum = 0; while(n > 10) { sum += 9; n /= 10; } cout << sum + n << '\n'; 
 » Is the concept "smallest prime factor" (minD) a well-known thing?
•  » » Yes.
 » 7 weeks ago, # | ← Rev. 2 →   Can anyone pls tell me how the value of k equal to ((x + p - 1) / p) * p in problem D ?
»

//easy solution of problem c //****can anyone tell me why a swap operation has done in if condition??

# include <bits/stdc++.h>

int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr), std::cout.tie(nullptr); int T; std::cin >> T; while (T--) { int n; std::cin >> n; std::string s, t; std::cin >> s >> t; int a = 1, b = 1; for (int i = 0; i < n; ++i) { if (s[i] == 'B' && t[i] == 'B') { std::swap(a, b);////**********?? ///continue; } else { (s[i] == 'B' ? b : a) = 0; } } std::cout <<"-->"<< (a || b ? "YES" : "NO") << '\n'; } return 0; }

 » the pair contribution dp thing is something i've really only seen in digit dp problems, interesting to see it works with subarrays as well :)