### awoo's blog

By awoo, history, 18 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)
• +77

| Write comment?
 » 18 months ago, # |   +50 ratttttttttttttttttttttttttttttttttttttttttttttttttttttting plz
•  » » 18 months ago, # ^ |   +7 LOL, why so many downvotes.
•  » » 18 months ago, # ^ |   +29
•  » » 18 months ago, # ^ |   +2 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
 » 18 months ago, # | ← Rev. 2 →   +9 When will the ratings update? :(
 » 18 months ago, # |   +34 It is the first time that I will have a oringe name. I really want it could update rating as quickly as possible.plz
•  » » 18 months ago, # ^ |   +11 i feel for you :(
•  » » 18 months ago, # ^ |   +6 It's the same for me...plz
•  » » 18 months ago, # ^ |   0 me too, it so slow
•  » » » 18 months ago, # ^ |   +5 me too too
 » 18 months ago, # | ← Rev. 2 →   +28 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
•  » » 18 months ago, # ^ |   +45 Didn't it occur to you that you were solving a Div2B and not a Div1B? xD
•  » » 18 months ago, # ^ |   0 Us moment
 » 18 months ago, # |   +6 In A why 184918763 got TLE?
•  » » 18 months ago, # ^ |   -49 That's why you are grey.
•  » » » 18 months ago, # ^ |   +35 now is your comment:)
•  » » 18 months ago, # ^ |   +9 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).
•  » » 18 months ago, # ^ | ← Rev. 2 →   +15 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.
•  » » » 5 months ago, # ^ |   0 I mean what you meant is codeforces, or his pc doesn't have computation power to execute it. c++ is just a language
 » 18 months ago, # |   +4 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$.
•  » » 18 months ago, # ^ |   +1 its all code, man.
 » 18 months ago, # | ← Rev. 2 →   +76 state transition graph for 1766E([i] represent for a sequence end with i)
•  » » 18 months ago, # ^ |   +3 This state transition is sufficient enough to arrive at the intended solution.
 » 18 months ago, # |   0 Nice round. I think D and E are the best problems I've ever seen.
 » 18 months ago, # |   +10 Video Editorial of Problem C : Hamiltonian Wall Link : https://youtu.be/p4-bUeGfs48
 » 18 months ago, # |   +8
 » 18 months ago, # |   +9 E is simply brilliant.
•  » » 5 months ago, # ^ |   0 It would have been more brilliant if the states have been around 10000000000000000000000000000000000000000000000000000000000000000 and transistions ended at russia and started at your brain
 » 18 months ago, # | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ |   +34 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.
 » 18 months ago, # |   0 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?
•  » » 18 months ago, # ^ |   0 Yeah correct, knowing the smallest is sufficient
•  » » » 18 months ago, # ^ | ← Rev. 3 →   +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.
•  » » » » 18 months ago, # ^ |   0 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
•  » » » » » 18 months ago, # ^ |   0 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"
 » 18 months ago, # |   0 if anyone wants the O(1) solution for A, here it is :)184929564
 » 18 months ago, # |   +3 What will be the expected rating of the first 3 questions?
 » 18 months ago, # |   +12 when will the rating be updated???
•  » » 18 months ago, # ^ |   +10 Perhaps the program of calculating rating change has crashed and CF stuffs are calculating manually
•  » » » 18 months ago, # ^ |   +5 what, manually???
•  » » » » 18 months ago, # ^ |   +5 I cannot come up with any other idea why rating has not been updated yet now
•  » » » » » 18 months ago, # ^ |   +3 manually? are you sure there are that many of them during the war?
•  » » » » » » 18 months ago, # ^ |   0 What does war have to do with this
 » 18 months ago, # |   +3 Why this submission passed problem 2? Surely it's complexity is O(n^2) Your text to link here...
•  » » 18 months ago, # ^ |   +4 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.
•  » » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   +6 The contest which made me master! 139 is a happy number.
•  » » 18 months ago, # ^ |   +8 It made me blue! (perhaps back to cyan tommorrow)
 » 18 months ago, # |   0 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 :)
 » 18 months ago, # | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ |   0 n must be equal to length of string
 » 18 months ago, # |   0 Is the concept "smallest prime factor" (minD) a well-known thing?
 » 15 months ago, # |   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 :)
 » 11 months ago, # |   0 Why my solution of problem D gives TLE? 215848671
 » 10 months ago, # |   0 Can any one help me in understanding what this part of code do in the solution of 1766D — Lucky Chains int r = INF; for (int p : getPrimes(d)) r = min(r, ((x + p - 1) / p) * p); cout << r - x << '\n'; 
 » 3 weeks ago, # |   0 https://mirror.codeforces.com/contest/1766/submission/262903359dfs solution for task C