By awoo, history, 18 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Retired_MiFaFaOvO 7 230
2 Volkov_Ivan 7 272
3 Egor 7 343
4 2829908231 7 360
5 rainboy 7 707

Congratulations to the best hackers:

Rank Competitor Hack Count
1 theStaticMind 14:-8
2 Chrollo_Lucifer 5:-1
3 Learner 10:-13
4 RitikBaid 3
5 Ashiok 4:-3
139 successful hacks and 617 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A fextivity 0:01
B Sonechko 0:05
C Isaunoya 0:05
D Retired_MiFaFaOvO 0:10
E Shanks 0:11
F YangDavid 0:35
G rainboy 0:44

UPD: Editorial is out

• +344

 » 18 months ago, # |   0 good luck :D
•  » » 18 months ago, # ^ |   +117 Only contest can keep us busy during quarantine. :)
•  » » » 18 months ago, # ^ |   +44 Actually thinking about when is the next contest does that ;)
•  » » » » 18 months ago, # ^ |   +34 Apparently there are no div 2+ contests until April 3 :( So a long long (note the pun) 9 days wait.
•  » » » » » 18 months ago, # ^ |   +47 Was that pun INTended?
•  » » » » » 18 months ago, # ^ |   +41 I guess that pun cannot fall short.
•  » » » » » 18 months ago, # ^ |   +58 I think cf should double the contest frequency
•  » » » » » » 18 months ago, # ^ |   -7 not double but 3 and i think there are more rated contest(i am a chinese)
•  » » » » » » 18 months ago, # ^ |   +3 with no strings attached
•  » » » » » 18 months ago, # ^ |   +13 The 9 days will be void of any rating changes for me. :(
 » 18 months ago, # |   -38 My Last contest the first time i solve two problems , and i solved them in less than 30 minutes, this contest i will solve at least three problems insha' allah :), Good Luck for all :).
•  » » 18 months ago, # ^ |   0 Inshaallah brother <3 Good luck you too
•  » » » 18 months ago, # ^ |   -39 I wish best of luck for you too <3 :) , Thanks brother <3 :)
•  » » 18 months ago, # ^ |   +9 Lands up solving none , Better luck next time Bro.
•  » » » 18 months ago, # ^ |   +1 I solved B in the contest , and solved A after it :) , you too bro :)
 » 18 months ago, # |   0 Haven't participated an educational round properly before. Can someone tell me if the hacks are accounted in ranking?
•  » » 18 months ago, # ^ | ← Rev. 3 →   +27 You do not get points for hacking. You only get one problem less solved if you get hacked.So, if you hack somebody with same number of solved problems, you raise by one position in the ranking, because the other one falls down.
•  » » » 18 months ago, # ^ |   +4 Well not necessarily: if the person whose solution I hacked was already beneath me due to submission time. :P
•  » » » » 18 months ago, # ^ |   +70 You can make a problem outta that.
•  » » » » » 18 months ago, # ^ |   +2 Problem A in next contest "predict the rank" lol
•  » » » » » » 18 months ago, # ^ |   +3 That would be too easy to hack.
 » 18 months ago, # | ← Rev. 2 →   -15 AHH forget about what I said :)))
 » 18 months ago, # | ← Rev. 2 →   +13 Educational codeforces rounds are a great harbour space initiative. The last educational codeforces round had easy A B and C questions but D and E were really really great for learning. Hope to learn a lot from this contest as well.
•  » » 18 months ago, # ^ |   -26 D was boring too.
 » 18 months ago, # |   0 I hope the tasks will be interesting.
•  » » 18 months ago, # ^ |   -48 I only hope my rating not to drop. Good luck! :)
•  » » 18 months ago, # ^ |   -17 Tasks are always interesting as well.
 » 18 months ago, # |   +34 I just hope this round will have strong pretests. :D
 » 18 months ago, # | ← Rev. 2 →   -117 I will Focus now
•  » » 18 months ago, # ^ |   +27 and that is why we never focus on ourselves and lose ratings.
•  » » » 18 months ago, # ^ |   -24 Ok, Now I will take care of it. I will focus on contest :)
•  » » » 18 months ago, # ^ | ← Rev. 2 →   -16 Wow, your rating records are similar to mine. I also think I never do my best in contests, so my rating never goes up.
•  » » 18 months ago, # ^ |   +12 Don't focus on your friends rating , focus on problems to solve as you can... and if there new ideas for you try to learn it and keep that in your mind or write it in your note book that will make your thinking high not just your rating. Good Luck for you in this contest :)
•  » » 18 months ago, # ^ | ← Rev. 2 →   +159 Will you stop commenting this in every contest blog?
 » 18 months ago, # | ← Rev. 2 →   -163 Please God Save Us from Corona Virus :( Pray to God.
 » 18 months ago, # |   +68 Teachers say that we loose our time in quarantine and we are doing nothing. LOOK TEACHERS... WE ARE GETTING EDUCATED
•  » » 18 months ago, # ^ |   +10 Exactly! those college/school hours are boring and gruesome.
 » 18 months ago, # |   +7 Thank you for giving the exact number of problems.
•  » » 18 months ago, # ^ |   +44 Does it actually matter? would anyone prepare differently for a different number of problems?
•  » » » 18 months ago, # ^ |   -12 Yes.
•  » » » » 18 months ago, # ^ |   +3 How?
•  » » » » » 18 months ago, # ^ |   +123 Extra pen for each problem
•  » » » » » » 18 months ago, # ^ | ← Rev. 2 →   -16 .
 » 18 months ago, # |   +50 We need more contests during the quarantine please! When will we have a contest about Coronavirus?)
•  » » 18 months ago, # ^ |   +14 Well We don't know if we will be alive To participate That Corona Contest
 » 18 months ago, # |   +5 Hello, I am actually slow at solving the initial problems(but i solve them) and not able to solve the tougher ones. So basically the rating never increases. So what should be done ? Thanks.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 Practise. Practise. Practise. Try to solve problems of higher difficulty. Well, I was stuck as a newbie for quite a while. But after some practice, I managed to become a pupil. Initially, I used to solve 1 problem a contest, rarely 2, sometimes none. But now, after a decent amount of practice, I am able to solve at least 2 per contest. Just don't give up.
•  » » » 18 months ago, # ^ |   +9 Thanks man!!
•  » » » 18 months ago, # ^ |   0 where to practice man!!! I am practicing a lot but some questions are not able to solved by me.this really demotivates me and as a result i loose confidence... tell man!!!
•  » » » » 18 months ago, # ^ |   0 In problemset, try solving the As. They are the easy ones. Once you get comfortable with that, go for Bs. Then the Cs. Keep building it step by step.
•  » » » » » 18 months ago, # ^ |   0 Will try!!! wish me luck...:D
•  » » » » 18 months ago, # ^ |   +3 Learn new concepts like dsu, graphs, modular arithmetic, dp ect then the solution will come from within
•  » » » 18 months ago, # ^ |   0 I think 'Practice' would help.
•  » » 18 months ago, # ^ |   0 then upsolve the tougher ones. That's actually what makes you capable of solving them in-contest.
 » 18 months ago, # |   +5 Can someone explain me the difference between education codeforces round and normal div2 rounds . TIA
•  » » 18 months ago, # ^ |   +26 Two biggest differences are the 12 hour open hacking phase and the score distribution (every problem carries the same weight in educational rounds).
•  » » 18 months ago, # ^ | ← Rev. 2 →   +15 Ranking: Compared with normal rounds, edu(educational) round don't have a "score distribution"Only two factors affect the ranking:"Problem solved" and "Penalty"That means, solving 2 problems is always better than solving 1 problemHowever, in normal rounds, problem F worths more points than problem A+B Hacks: 1.In the normal rounds,you can only hack if following conditions hold: You solved the problem,and you locked it The victim and you are in the same room The contest is not ended yet However, in edu rounds, you can hack anyone in the open-hack phase(even if you didn't participate the contest), and you don't need to solve the problem."Room" doesn't exist in edu rounds.2.In edu rounds, you can copy the code and test it locally, which means you can preview whether or not the solution will fail.However, in normal rounds, it's forbidden to copy the code. 3.In normal rounds,a successful hack gives you 100 points and an unsuccessful cost you 50 points.In edu rounds, hacks changes nothing to your penalty. The only difference is the victim loses a problem System test: In normal rounds, system test begins shortly after the contest.All solution will be rejudged with pretests, maintests prepared by authors and successful hacks, if there are.In edu rounds, system test begins after the open-hack phase. All solution will be rejudged by pretests and successful hacks.There's no "maintest"
•  » » » 18 months ago, # ^ |   0 Would you please elaborate on point 2. I am not sure I understood. What do you mean "forbidden to copy the code"?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 In normal Div.2 competitions, you cannot copy other's code when you are hacking them (should be in contest rules). In educational competitions (and Div.3 also I think), you will be able to copy the code and test test-cases by yourself.
•  » » » » » 18 months ago, # ^ |   0 Thanks. I did not read carefully and did not realize that was in relation to hacks.
 » 18 months ago, # |   +46 These days we need more and more contests :'D
 » 18 months ago, # |   +2 Hope to learn something new and solve 3 or more question this time. . .
 » 18 months ago, # |   +12 Please... make strong Pretest Cases!!
 » 18 months ago, # |   +21 I really pray for the load on the server as all college students of India are at home and they have nothing to do so expecting mass participation today.
 » 18 months ago, # |   +2 I really wish a color change this time!Fingers crossed! All the best everyone.
•  » » 18 months ago, # ^ |   +13 Good luck for you! Maybe you can even be a specialist or an expert after this round!
•  » » » 18 months ago, # ^ |   0 Thanks !!! :)
•  » » 18 months ago, # ^ |   0 Does it worked xD?
 » 18 months ago, # |   -12 My first unofficial Div.2
 » 18 months ago, # |   +6 Only exciting thing to engage me, during this quarantine.
•  » » 18 months ago, # ^ |   0 For me after googling corona stuff xD.
 » 18 months ago, # | ← Rev. 4 →   +3 The biggest mistake of mine is not continuous in every codeforces contest...I request all of you those who are low rated do more and more contest & upsolve,,
 » 18 months ago, # |   +15 Hoping for strong pretest this time.
 » 18 months ago, # | ← Rev. 2 →   +5 .
 » 18 months ago, # |   -8
 » 18 months ago, # |   +5 I remember that the number of problem was 6 at first. Is the purpose of extra problem to reduce difficulty gap, or is there some other purpose?
 » 18 months ago, # |   +6 contest and chill
 » 18 months ago, # |   0 17k+ registration Going to be 18k soom Is it effect corona? I hope corona can't attack anyone on other way.
 » 18 months ago, # |   +66 Monday Educational 18k participants
 » 18 months ago, # | ← Rev. 2 →   +12 18584 registrations! Still increasing!! All the best everyone!!!
•  » » 18 months ago, # ^ |   +2 13522 participaters <3
 » 18 months ago, # | ← Rev. 2 →   +30 The server is gonna explode. 18K registration O_O
•  » » 18 months ago, # ^ |   +4 Effect of quarantine due to coronavirus.
 » 18 months ago, # |   0 It's about time. Good luck everyone
 » 18 months ago, # |   +35 I think that someone should stop coming up with problems
•  » » 18 months ago, # ^ |   +26 Could you elaborate, please?
•  » » » 18 months ago, # ^ |   -18 There is one person among authors whose problems are usually not really good(its just my opinion)
•  » » » » 18 months ago, # ^ |   +37 How do you know who wrote which problem today?
•  » » » 18 months ago, # ^ | ← Rev. 3 →   -27 BledDest Ofcourse!!!
 » 18 months ago, # |   -29 WrongAnswerforces
•  » » 18 months ago, # ^ |   -18 WeakObservationForces
 » 18 months ago, # |   0 The statement of Problem C and E is poor. Is there a reason U / D operation changes x coordinate and L / R operation changes y coordinate in problem C, not U / D changes y and L / R changes x?
•  » » 18 months ago, # ^ |   +8 D is hard to understand too.
•  » » » 18 months ago, # ^ |   0 No, it's well written, permutation cycles are denoted in same manner
•  » » 18 months ago, # ^ |   0 I tried hard to find solution for C for 2*(n+m) moves.That was not fault of statement language, but lengthy statement misguides sometimes to get obvious things wrong. Luckily I noticed later and was able to solve it.
•  » » 18 months ago, # ^ |   0 I found problem C pretty clear. Rather than, problem D was more difficult to understand.
•  » » 18 months ago, # ^ |   +17 Exactly. I'd prefer: $\text{U} : (x, y) \to (x, y + 1)$ $\text{D} : (x, y) \to (x, y - 1)$ $\text{L} : (x, y) \to (x - 1, y)$ $\text{R} : (x, y) \to (x + 1, y)$ :P
•  » » 18 months ago, # ^ |   +21 I'm so confused that I asked the author like this :p
•  » » 18 months ago, # ^ |   +41 (row, column) is standard when talking about matrices.
•  » » » 18 months ago, # ^ |   -35 but variables x and y are suggestive of the mathematical 2d coordinate system
•  » » 18 months ago, # ^ |   +7 Well there is always a confusion for grids and 2d matrices. For mathematicians, it is more standard to use co-ordinate system, and for computer scientists it is more natural to think about indices / enumeration of the matrix / grid, which brings us to what it was in the question.Doing CP, I think I have been swayed towards the computer science way, and found the directions straightforward. Maybe they should have added the line ( which is usually always there ), "Rows are numbered from 1 to n, from top to bottom, and Columns are numbered from 1 to m, from left to right".
•  » » 18 months ago, # ^ |   0 The sample testcases for Problem C is good enough, so I believe explaining which is x and which is y is not important. Remember, only complain about the statement if the sample testcase is just as bad!Same thing with problem E.
 » 18 months ago, # |   +8 So, how to solve F? Is it inclusion-exclusion on each bit separately?
•  » » 18 months ago, # ^ |   +54 Solve for each bit separately, multiply results. To solve for one bit, I did a linear DP setting 0s from left to right and counting ways to do so.Essentially you only have two restrictions to deal with: First of all, for given position P you can't put 0 there if it is a part of some 1-segment. In case you decide to put 0 there, the previous 0 can't be too far to the left so you don't have some 0-segment being completely between those two 0s.
•  » » 18 months ago, # ^ |   +59 No inclusion-exclusion, but let's look at each bit separately.Consider some fixed bit, we have some ranges $l \ldots r$ where this bit must be constantly 1 and some other ranges where this bit must have at least one zero. Let's delete the ranges of the first type and shrink the array. Now we have some ranges and in each range we must have at least one zero (if some of these ranges became empty after the shrink, answer to the problem is 0). Now let $\mathrm{dp}[k]$ be the number of ways to fill the array up to $k$ such that there is a zero at $k$ and all the constraints that have the right endpoint $•  » » » 18 months ago, # ^ | +8 Could you explain a sketch of a linear time DP? •  » » » » 18 months ago, # ^ | ← Rev. 3 → +11 Let$dp[i]$be the number of ways to fill up the array up to position$i$with a$0$at position$i$. If we're in a segment where only$1$s are allowed, then$dp[i] = 0$(you can't set a$0$there).Otherwise let$l_i$be the rightmost starting point of the segments with ending points$< i$. We now know that we need to put a zero somewhere between$l_i$and$i - 1$, inclusive (otherwise there is no$0$in said segment). This$l_i$can be kept updated with proper bookkeeping. Since there are no other restrictions, we can set the zero anywhere between$l_i$and$i - 1$, inclusive. This gives us:$dp[i] = \sum_{k=l_i}^{i - 1} dp[k]$We can calculate this sum in$\mathcal O(1)$if we build a prefix-sum structure while calculating our dp. To get the result, we can just imagine counting the number of arrays of size$n + 1$which end on a$0$. This gives us a total running time of$\mathcal O(k(n + m))$which gives AC. Maybe there is a simpler solution than mine, but I hope, this already helps.Edit: Here is a link to my submission, maybe it helps to understand: https://codeforces.com/contest/1327/submission/74120243 •  » » » » » 18 months ago, # ^ | +1 "let li be the rightmost starting point of the segments with ending points •  » » » » » » 18 months ago, # ^ | ← Rev. 2 → +4 We're only talking about the last$0$before$i$. If we put the last$0$at$i - 1$for example, we can then look where we placed the last$0$before$i - 1$. Either it's between$l_i$and$r_i$, or afterwards. But even if it is afterwards, we slowly but steadily get closer to$r_i$and when we're at$i = r_i + 1$, then we have no other option then putting it inside$l_i$and$r_i$. In either way, we have put a$0$inside$l_i$and$r_i$.  » 18 months ago, # | ← Rev. 6 → +11 How to solve E :< •  » » 18 months ago, # ^ | ← Rev. 4 → +4 I had a multiplication instead an addition and unfortunately I solved the problem 5 minutes after the contest ended. It is a combinatorial problem.Let's say we want to find the answer for block_size = i. This block will contain the same digits (lets name them with letter "a"). Because block_size can't be larger we want the adjacent digits to be different (lets name them with letter "b"). Now the picture is this: xxxbaa...aabxxx (x are the empty cells for now) You can have 10 possible values for "a". Total ways for a and b are 10 * 9. The rest cells can be anything, so we have 10^(N-i-2) ways to set them a value. Now for that fixed picture, ways are equal to 10 * 9 * 10^(N-i-2). But in how many ways we can fix a block of size "i" having two adjacent empty cells ? This can be done in N — i — 1 ways, so we multiply by that as well. Finally we need to add up (this is where I used multiplication by accident) the corner case where we have only one adjacent cell.Here is my source-code: https://codeforces.com/contest/1327/submission/74125507 •  » » » 18 months ago, # ^ | ← Rev. 2 → +4 How about the case when you have something like this : xxxxbaabaabxxxxx? Shouldn't this increase the answer by two because we have two blocks there? I don't see how your solution counts for that. •  » » » » 18 months ago, # ^ | ← Rev. 3 → +9 Split this xxxxbaabaabxxxxx to these two pictures xxxxbaabxxxxxxxx and xxxxxxxbaabxxxxx.Now the initial picture xxxxbaabaabxxxxx will appear twice. Once for the case we have fixed the first "aa" and once for the case we have fixed the second "aa".Probably what you are thinking is that we are counting similar patterns more than once, here we need to take into consideration every "aa", so actually these two blocks of "aa" are independent.It will be easier if you stop thinking 10^N numbers but a string of N positions in which you want to add digits. •  » » » » » 18 months ago, # ^ | 0 I still can't understand your point like if u assume cdaabaacd this is one number but aren't we counting our answer twice for i=2 by considering xxaaxxxxx and xxxxxaaxx different but they will count our above number twice? •  » » » » » » 18 months ago, # ^ | +2 The author is deliberately counting the case cdaabaacd twice, because this case contains two consecutive segments. •  » » » » » » » 18 months ago, # ^ | 0 oh! yeah right, Thanks! •  » » » 18 months ago, # ^ | ← Rev. 2 → +13 Why did you take both the adjacent digits same ? Shouldn't be the total no of ways be 9*10*9 ? •  » » » » 18 months ago, # ^ | ← Rev. 3 → +1 Yes if block size is less than n-2 and we are considering the block is between the number (having adjacent element both side) it will be 9*9*10 , and when we consider the block to be at the corner of the number then it will have only adjacent then we will multiply with 9*10 •  » » » 18 months ago, # ^ | 0 Thanks •  » » » 18 months ago, # ^ | 0 very nice explanation •  » » 18 months ago, # ^ | ← Rev. 6 → +11 I used dynamic programming.First, let's consider a block of size n. Then there will only be 10 ways to fit them. I will represent the block as X. X (10) Then, if we consider a block of size n-1, There will be 180 ways to fit them. X? (10 * 9) 9 -> because it cannot be the same as X ?X (90) Then, n-2, there are 2610 ways X?? (90 * 10) X? + ? ?X? (90 * 9) ?X + ? ??X (900) You can see that the configuration ending with ? can be computed from the previous block size and the configuration ending with X can be computed naively.So, here is the dp.$dp_{n, s} = \begin{matrix} 10 * dp_{n+1, 0} + 9 * dp_{n+1, 1} & if : s=0\\ 10 * dp_{n+1, 1} & if : s=1 \end{matrix}$s = 0 is for configurations ending with ?, and s = 1 is for configurations ending with X.This doesn't work specifically for n-1, because the first ? (for ?X) is counted as 9 instead of 10, so make that a base case and use the dp starting for n-2. •  » » » 18 months ago, # ^ | ← Rev. 3 → 0 Oh, thanks. It is easy to understand but is that the formula is dp[n + 1][0] = dp[n + 1][1] = 0; for n -> 0 dp[n][s] = is_configurations ? 10 * dp[n + 1][0] + 9 * dp[n + 1][1] : 10 * dp[n + 1][1];  •  » » » » 18 months ago, # ^ | ← Rev. 2 → +1 yea, but the base case is for n and n-1, not n+1. dp[n][0] = 0; dp[n][1] = 10; dp[n-1][0] = 90; dp[n-1][1] = 90; latex is so hard >< •  » » » » » 18 months ago, # ^ | 0 haha XD •  » » » » » 18 months ago, # ^ | 0 You can think latex as another language :)) •  » » » 18 months ago, # ^ | 0 This is a very nice dp. I have one question to see if I got it right. Let's say we have block of size=4 in the configuration ??0000X? (X != 0). The term$10 \cdot dp_{n+1, 0}$comes from the fact that with nine ways we can produce this: ??000YX? (Y != 0) and with one way we can produce this (??000X0?).Is it right ? •  » » » » 18 months ago, # ^ | +3 No. it means if you currently have ??0000X? and you add another character, it becomes ??0000X??, and because this additional character is not incident to the block that we care about, it is guaranteed to not extend the block. So, there are 10 ways to do that (0-9).For$9 * dp_{n+1,1}$, it's 9 because the additional character is incident to the block, so it cannot be the same with the block in order to not extend it. •  » » 18 months ago, # ^ | 0 we could use FFT to solve this problem let f be [1,9,90,900...],and g=f*f，then 10*g[n-i] will be the answer for the i th term  » 18 months ago, # | ← Rev. 2 → +8 In problem B, I thought that maybe it's better to use the word index rather than number. I misunderstand the word number as count.  » 18 months ago, # | 0 if the contest was 2:15 or 2:30 min, then it might be better(since there was 7 qns). Anyhow nice problems.  » 18 months ago, # | +26 How to solve D? •  » » 18 months ago, # ^ | ← Rev. 6 → +45 If you draw a directed graph with edges$(v, p_v)$, then each its component will contain one cycle. When we raise our permutation to the power$k$, an edge from$v$will start pointing at a vertex$k$steps away. The initial permutation is OK if and only if we have a unicolored loop.Now, note that, for some loop of length$L$, if we raise our permutation to the power$m$that$gcd(L, m) = G \ne 1$, we will be able to jump along this loop in such a way that we will only visit every$G$-th vertex, which reduces the number of vertices in our path and, hopefully, makes it unicolored. For example, if we have a loop of length$36$and raise our permutation to the power$9$, then, starting at$s$, we will visit only$(s + 9k) \mod 36$-th vertices of a loop. Our big loop as though breaks into$9$small loops of length$4$. We can travel along each of them and check if any one becomes unicolored.Now do it for every divisor of the length (since GCD of$k$and some other number can be only a divisor of$k$) of every loop found. It wiil not TL as the number of divisors of a number less than$2 \cdot 10^5$doesn't exceed$200$, and each such procedure takes linear time. •  » » » 18 months ago, # ^ | 0 Great thanks. •  » » » 18 months ago, # ^ | +7 "When we raise our permutation to the power k, an edge from v will start pointing at a vertex k steps away." — How did you find about this? What was your approach? •  » » » » 18 months ago, # ^ | 0 Don't think of it as modifying edges. Think of it as traversing k edges.p[v] traverses one edge, p^2[v] traverses two edges, etc. •  » » » » 18 months ago, # ^ | +6 Looking at the cycles is a very common pattern in anything to do with permutations. What the cycles do when you take the permutation to the$k$-th power is basically standard knowledge about permutations. •  » » » 18 months ago, # ^ | +6 Why the graph theory interpretation when this is exactly cyclic permutations? https://en.wikipedia.org/wiki/Cyclic_permutation •  » » » 18 months ago, # ^ | 0 can you tell how can we say that we will be able to jump Gth vertex from s, where G = gcd(m, L), m = power raised and L is length of cycle? •  » » » » 18 months ago, # ^ | 0 Think of this as, finding the minimum k such as: s ≡ s + k * m (mod L). This translates to 0 ≡ k * m (mod L). Now for k to be minimum, such that this equation holds true, k * m = LCM(L, m). So, k = LCM(L, m)/m. We know, LCM(L, m) * GCD(L, m) = L * m. Therefore, k = L / GCD(L, m). •  » » 18 months ago, # ^ | ← Rev. 4 → +11 You do not need graph theory at all. Each permutation is the product of cycles. https://en.wikipedia.org/wiki/Cyclic_permutation In each cycle a permutation p^k is like stepping through the cycle k times. So we need to find minimum k so that we start somewhere in the cycle, step by k while maintaining a color (looping around if needed), and eventually returning to our starting point. For the last example our cycles are (1 7 3 5) (2 4 6 8). Our cycle colors are (5 8 6 7) (3 4 5 4). In this case we only consider k that divides cycle length C. To see why consider repeatedly adding k mod C which is what we are doing. We end up stepping through all multiples of gcd(k,C). This gcd is less than k if k does not divide C so k was not optimal.In general we have [Lagrange's Theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) For this case we consider (cyclic) subgroups of cyclic groups (one for each cycle).  » 18 months ago, # | +2 How to do C? •  » » 18 months ago, # ^ | ← Rev. 3 → +16 Push all points to 1 corner then iterate them over every grid of the board .it's no more than 2nm •  » » 18 months ago, # ^ | +1 Since the number of actions is quite big, you can collect all chips in one cell and then just visit all cells. •  » » 18 months ago, # ^ | +1 go to most up-left(1,1).then travel through all the squares and go to the most under-right(n,m).it is always smaller equal than 2*n*m •  » » 18 months ago, # ^ | ← Rev. 2 → +5 You can first use$n + m - 2$operations to push all of the stuffs to the right-down corner.Then travel the whole board with$n - 1\text{U}$,$1\text{R}$, (repeat it with$m - 1$times).Total times of operations will be$nm + n + m - 2$, and it will be sure less than$2nm$.Hope it helps :P •  » » 18 months ago, # ^ | +1 You can always solve the problem in <= 2*n*m steps if you follow these steps.1. Gather every chip to the top-left place. It should take (n-1)+(m-1) steps max.2. Now move these chips together through the matrix in a spiral order. This should take n*m steps max.Totals steps taken = (n+m-2) + n*m which will never exceed 2*n*m steps. •  » » » 18 months ago, # ^ | 0 Spiral traversal is much harder to code than boustrophedon (back and forth) traversal  » 18 months ago, # | 0 Since recent previous contests had the first question based on parity, I could only think the solution based only parity. How the hell do you solve question-A? •  » » 18 months ago, # ^ | 0 Both n and k should be of same parity and k*k<=n. •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 Proof? (that$k^2 \le n$)? •  » » » » 18 months ago, # ^ | +4 Well, we should consider the circumstance where$k$and$n$have the same remainder under modulo$2$.Because otherwise there isn't a solution.While adding up odd numbers, if$n$is greater than$k^2$, let$d = n - k^2$, we can get$2|d$, so we can replace some of the smaller odd numbers into bigger ones. •  » » » » 18 months ago, # ^ | ← Rev. 2 → 0 Min number made of k odd numbers is$(k*(k+1) + k*(k-1))/2$So you can construct every number equal or bigger that that with same parity. •  » » » » » 18 months ago, # ^ | 0 I understand the sum of the first$k$odds is$k^2$but I've been staring at this equation$(k * (k+1) + k * (k-1))/2$on paper for 30 minutes and I don't understand what it means. I'm just curious, can you elaborate (without reducing it using algebra). All I see is the formula for arithmetic sum and$\binom n2$. •  » » » » » » 18 months ago, # ^ | 0 I think what the OP wanted to say was that the minimum number made by first 'k' odd numbers is (k∗(k+1)+k∗(k−1))/2, which is same as the square of k, solved by reducing using algebra. The OP's wording is wrong because the minimum number you can make with k odd numbers is infinite, unless you are given those k odd numbers. •  » » » » » » 18 months ago, # ^ | +1  1 2 3 4 5... + 1 2 3 4... --------- 1 3 5 7 9... first line is$k*(k+1)/2$, second line is$(k-1)*k/2$•  » » » » » » » 18 months ago, # ^ | 0 oohhh wow •  » » » » 18 months ago, # ^ | ← Rev. 2 → 0 Sum of First n odd nos. is n**2.1=1;1+3=4;1+3+5=9;So k should be <= root(n). •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 . •  » » » » 18 months ago, # ^ | 0 No, it should be less than equal to. Consider 221 and 175 as input. •  » » 18 months ago, # ^ | -7 First of all, the sum of the first$k$odd numbers is$k^2$.Then, if$n$is greater than$k^2$and the remainder$k$and$n$have under modulo$2$are the same, then it is sure that we can figure out a proper solution.Otherwise, there's no solution.Hope my explanation helps :P •  » » 18 months ago, # ^ | +1 let us assume odd number are 2a1-1,2a2-1,2a3-1,....2ak-1 as per equation sum up all n= 2*(a1+a2+a3+...ak) -k;so a1+a2+a3...ak = n+k/2;first check if n+k is divisible by 2 or not , if so then for all distinct a1!=a2!=a3..!=ak ,minimum sum of first k distinct positive number is k*(k+1)/2; if this sum is smaller than or equal to (n+k)/2 ,then ans is yes ,else no  » 18 months ago, # | ← Rev. 2 → +33 Today's problem EOne can write a simple bruteforce for n = 5 and find this trivially. •  » » 18 months ago, # ^ | +5 Could you please elaborate a bit?  » 18 months ago, # | 0 Well done every one :D. Thanks for a nice contest(even though my rating drop :( )  » 18 months ago, # | 0 How the hell do you solve A???? •  » » 18 months ago, # ^ | 0 •  » » 18 months ago, # ^ | 0 If you observe the basic even odd numbers. Sum of any numbers even times will always even and the sum of any numbers odd times will be odd. So, wither we need both n and k even or odd. Other than that if the sum of first "k" odd numbers is greater than "n" then it is not possible to get any set of "k" numbers with "n" as the sum. And sum of first n odd numbers is n^2. Hopefully, It will help. Thanks. •  » » 18 months ago, # ^ | ← Rev. 3 → 0 Short answer cout<<((((n-=k*k)<0)||(n&1))?"NO":"YES");Details answer n -= k * k; // 1 + 3 + 5 + ... + 2 * k — 1 = k * k if (n < 0) // if n < smallest sum of first k odd number cout << "NO"; else if (n % 2 == 0) // we can chose first (k — 1) odd number than choose last as n — sum cout << "YES"; else cout << "NO";   » 18 months ago, # | +5 I would like to thank the authors for allowing me to use BM. https://codeforces.com/contest/1327/submission/74109025 •  » » 18 months ago, # ^ | +25 When you overcomplicate a simple question and become a part of the league of geniosities •  » » » 18 months ago, # ^ | +4 •  » » 18 months ago, # ^ | ← Rev. 2 → 0 I'm going to bookmark it now!!!!! AryaPawn orz  » 18 months ago, # | ← Rev. 3 → 0 What should the answer be to this test case in D: n=3 , P = [3,1,2] ,C=[1,2,3]? There does not exist any k for this case right? •  » » 18 months ago, # ^ | 0 Since all colors are different, we need p[i] = i, smallest k for which this happens is 3. •  » » 18 months ago, # ^ | 0 It should be 3 •  » » 18 months ago, # ^ | 0 answer is 3. p^3 = {1,2,3}. SO now you have 3 infinite cycles.  » 18 months ago, # | +28 Amazing: 20000+ registered users for this round! •  » » 18 months ago, # ^ | 0 quarantine mode  » 18 months ago, # | 0 for the first time, I have no idea how my A and B got AC!!.  » 18 months ago, # | +6 E is much easier than D? I solved E even earlier than B. •  » » 18 months ago, # ^ | ← Rev. 2 → 0 I spend lot of time on E, thinking of things like multinomials, but that would straight up blow the complexity. Also tried generating function, but gave up. Can you give a hint? Thanks! •  » » » 18 months ago, # ^ | ← Rev. 3 → +5 If a block has a size of i:There are 10 plans for all numbers in the block, 9 plans for each number adjacent to the block, 10 plans for each number not adjacent to the block.Then just discuss:The block includes both the first and last element.The block includes either of the first and last element.The block includes neither of the first and last element.Here is my submission. •  » » » » 18 months ago, # ^ | +5 Oh now I feel it is easy! Thank you, clearly explained! •  » » » » 18 months ago, # ^ | 0 I was doing the exact same thing, but don't know for what god-damn reason I gave up :( •  » » » » 18 months ago, # ^ | +1 Say for example n=4, and we have to find the answer for block size = 2;Now _ _ _ _, I fill the second and third places with any number. 10 ways to do it. I fill the first and last place with any number other than the one I placed on second and third : 81 ways to do that.Total ways = 810.Now, _ _ _ _ I fill the (first and second) or (third and fourth) place with any number. 10 ways to do it The Remaining places can be filled with 9*10 = 90 ways. Total ways = 810 + (90*2*10) = 2610.Now my question is that, when I calculate it this way, Am I not repeating the same cases? For example, _ _ _ _ I fill the first 2 places with a two. then randomly the second and third place get a 3. the number is 2233. OR I fill the last 2 places with a 3, and then randomly fill the first 2 places with a 2. I end up getting 2233.These are the same cases. Dont we end up recalculating them? JKLover •  » » » » » 18 months ago, # ^ | +1 2233 has 2 blocks of size 2, so it is right to calculate it 2 times. •  » » » 18 months ago, # ^ | +16 There is a common idea behind tasks like this on Codeforces. Write bruteforce Look on some first answers Try to transform them (like in this task divide all answers by 10) Try to find this sequence on OEIS. ??? Profit! In example, there is this sequence for today's E •  » » » » 18 months ago, # ^ | 0 Looks like I missed the 3rd step :( •  » » 18 months ago, # ^ | +3 Really? B was just a comprehension question. Masked in an annoyingly huge statement, was the real problem: perform the greedy mapping as described, and just check at the end if any princess and kingdom pair is unassigned. Implementation is trivial. E was not easy at all. The only reason I solved E is because I wrote a brute-force and observed the pattern for small values. I still have no idea why the pattern is there. •  » » » 18 months ago, # ^ | ← Rev. 2 → +3 I mean that E is easier than D.I agree with you,E is exactly more difficult than B.I solved E earlier than B just due to my mistake in conprehension. •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 problem E can be solved in many different ways (including OEIS cough cough), and so I think it's significantly easier than D.But D doesn't require any algorithms, just an understanding of why it works in time limit. That might be why it's supposed to be easier than E.Whatever... I demand D and E to be swapped •  » » 18 months ago, # ^ | 0 literally took two hours to solve D :D  » 18 months ago, # | +11 I don't know why but my rating decreases in every Educational Round...Get educated.... •  » » 18 months ago, # ^ | 0 Same xD every educational round brought us a whole "strange" problem that made us confused a lot •  » » 18 months ago, # ^ | 0 Your rating just went up by 42 points... •  » » » 18 months ago, # ^ | 0 Yeah I didn't see that coming. [facepalm]  » 18 months ago, # | 0 What is the time complexity for D? I believe most submissions had O(n x logn x sqrt(n) [all divisors]). How could it pass? •  » » 18 months ago, # ^ | +21 Where does the log come from? I had no log and can't see where you would get it. •  » » » 18 months ago, # ^ | 0 How to solve D? please •  » » » 18 months ago, # ^ | 0 I got the log initially by somewhat different implementation than most. I basically check the answer for all divisors of each disjoint cycle. In the check function, I used binary lifting/search of some sorts to get the kth power permutation. Anyways, I got a TLE verdict :( Link •  » » 18 months ago, # ^ | +10 My solution has solution O(n * divs(n)) without the log factor. •  » » 18 months ago, # ^ | +13 O(n sqrt(n)), but actually it's O(160 n) since there are at most 160 factors for number in [1,n]. •  » » 18 months ago, # ^ | ← Rev. 2 → 0 -is-this-fft-, Mucosolvan, cwise okay, thanks, I misread the limit of the second for (to i, not to n) :'(.Guess stuck by wrong time analysis exists :'(. •  » » 18 months ago, # ^ | 0 The time complexity is indeed$O(n^{4/3} + n\log{n})$. •  » » » 18 months ago, # ^ | +35 Random boring comment: while this$O(n^{1/3})$bound may be reasonable in practice for given constraints, it is worth keeping in mind that the function we are talking about is subpolinomial: see wiki. So it is a bit like saying "We implemented$n^2$here, optimized it with bitsets to$\frac{n^2}{32}$, and since$n=1000$, our solution is$O(n\sqrt{n})$" •  » » » » 18 months ago, # ^ | +8 Personally, I don't see any problems with$O(n^{\frac{1}{3}})$since, for example, saying that$\sqrt{n} = O(n)$doesn't contradict with the definition of big-O notation.On the contrary, the example with bitset contradicts with the definition of big-O unless adding constraints on$n$every time you mention$O(n \sqrt{n})$.  » 18 months ago, # | ← Rev. 3 → +4 How to solve C if we are required to minimize the number of operations ? •  » » 18 months ago, # ^ | 0 Read above.  » 18 months ago, # | +14 Why does this code give Runtime Error on Test 1?https://codeforces.com/contest/1327/submission/74124335It works on my machine and I couldn't find any source of undefined behavior in the code. •  » » 18 months ago, # ^ | +5 Error: attempt to subscript container with out-of-bounds index 3, but container only holds 3 elements.This probably happens in line 142: if(c[i[w+len/j]] != c[i[w]]) •  » » 18 months ago, # ^ | +9 You have an out-of-bounds access on line 142: if(c[i[w+len/j]] != c[i[w]]). Here i = {1,2,3}, w=0,len=3,j=1 situation is reached and out-of-bounds occurs. •  » » 18 months ago, # ^ | 0 Got the error. Thanks!  » 18 months ago, # | ← Rev. 2 → +26 Wow! first time I see this number. •  » » 18 months ago, # ^ | 0 What will you do when you are being quarantined? Of course, you will find anything to kill the time  » 18 months ago, # | +3 Hey guys, can anybody explain how to solve E? Thanks •  » » 18 months ago, # ^ | +3 Refer this comment by JKLover : Link •  » » 18 months ago, # ^ | ← Rev. 2 → +16 Consider a block of length$i$($i$goes from$1$to$(n-1))$. We can have$(n - i + 1)$such blocks. Let the digit placed in the entire block be$k$. For every block, the immediate left and right digits surrounding the block can contain all digits except$k$, otherwise the length of the current block will change. Therefore, for these left and right places we have$9$possible digits and for all remaining places we have$10$possible digits. We need to handle two cases : Case 1 : The blocks of the kind$0...(i-1)$and$(n-i)...(n-1)$have only one surrounding digit in each,$(i)th$and$(n-i-1)th$respectively where we can place$9$digits. Number of remaining places with$10$possibilities at every place =$(n - i - 1)$. Total possible ways =$2$x$10^{(n - i - 1)}$x$9$Case 2 : All blocks except the two mentioned in case 1 (there will be$(n - i - 1)$such blocks). Each of these blocks has both left and right surrounding digits. Number of remaining places =$(n - i - 2)$.Total possible ways =$(n - i - 1)$x$10^{(n - i - 2)}$x$9^2$.Overall answer for a block of length$i$=$10 * (Case 1 + Case 2)$(multiplied by 10 since the current answer is just for one possible digit across the entire block). Simplifying the expression gives the result =$9$x$10^{(n - i - 1)}$x$(9$x$(n - i) + 11)$For$i = n$the answer is simply$10$•  » » » 18 months ago, # ^ | +6 Great explanation. Thank you a lot. •  » » » 18 months ago, # ^ | 0 Say for example n=4, and we have to find the answer for block size = 2;Now _ _ _ _, I fill the second and third places with any number. 10 ways to do it. I fill the first and last place with any number other than the one I placed on second and third : 81 ways to do that.Total ways = 810.Now, _ _ _ _ I fill the (first and second) or (third and fourth) place with any number. 10 ways to do it The Remaining places can be filled with 9*10 = 90 ways. Total ways = 810 + (90*2*10) = 2610.Now my question is that, when I calculate it this way, Am I not repeating the same cases? For example, _ _ _ _ I fill the first 2 places with a two. then randomly the second and third place get a 3. the number is 2233. OR I fill the last 2 places with a 3, and then randomly fill the first 2 places with a 2. I end up getting 2233.These are the same cases. Dont we end up recalculating them? cuber_coder •  » » » » 18 months ago, # ^ | +4 Yes you are right in your example that you are considering the number 2233 twice but for different block each time. Though the number is same but the interval used for block is different and we are counting number of blocks and not the frequency of number. Moreover it can be clarified from the fact that 2233 is chosen twice as it has 2 blocks 2 length 2. Hence in the given logic for each block length i a number is considered same number of times as the frequency of blocks having length i and same digit.  » 18 months ago, # | 0 why is everyone in C , computing n times L,m times R, and then in a (n,m)loop D & U ??whats logic ,and how did you all reached this conditionAre you guys are trying to access all points from most bottom(point) to the highest point, then why not begin() from lowest input point instead of (0,0), else ain't the length of out instruction will increase?? •  » » 18 months ago, # ^ | +3 Because you must gather all point to one place. What if when you iterate, there's some point that didn't pass the place it has to pass? Or there're some points that have to pass someplace lower than itself or lower than the lowest point? •  » » 18 months ago, # ^ | +3 It's simpler this way. The problem doesn't ask us for a short sequence of operations. And moving all points to a corner and then moving all of them over the whole board works. •  » » » 18 months ago, # ^ | 0 So in other words, we always have a solution? •  » » » » 18 months ago, # ^ | 0 Yes, indeed :) •  » » 18 months ago, # ^ | +3 Besides, You don't have to minimize the output unless it longer than 2nm .  » 18 months ago, # | +17 20K registration !!...happy quarantine...  » 18 months ago, # | 0 Problem B — WTH! Submitted code in PyPy3 — TLE but same code for Python3.7 — Accepted and then codeforces suggests PyPy3 works faster. •  » » 18 months ago, # ^ | 0 Pypy has JIT solution: don't use python  » 18 months ago, # | +16 How to solve G? •  » » 18 months ago, # ^ | +4 You build an Aho-Corasick automaton from the t_i strings and then do a dp over the automaton states and the set of characters you've already used.So, for a bitmask m and a Aho-Corasick state s, dp[m][s] would be the highest value attainable using the characters corresponding to the set bits in m for the first popcount(m) question marks, while ending in state s. You'll need to know the cost of all strings ending in a state, which you'll have to propagate along back links. In the transition, you look at all possible characters you could use for the next question mark, and then add the cost of the state you get after using that character, and all the states you visit when adding the fixed characters up to the next question mark (or the end).This comes out to$O(14 \cdot 2^{14} 10^3 + 4 \cdot 10^8)$which passes in 1.5s/4s for me. •  » » 18 months ago, # ^ | ← Rev. 2 → +13 Use Aho–Corasick algorithm to build an automaton.Consider dp(automaton node, bitmask of used letter), and there will be up to$2^{14} \times 1000$states. We can not use this state to iterator string$s$.But the transition of the dp state between two "?" is only related with automaton node. So between two "?", we only need to preform transition of the automaton node, and when we meet a "?", use the above transition to perform transition of complete dp state (this will only happen up to$14$times).Sorry for my bad English, and you can see my submission 74095972.  » 18 months ago, # | 0 Is finding the shortest cycle in the graph with edges between 'i' and 'input[i]' a wrong approach? After this, I considered nodes with the same colour separately like what is the path length between two nodes of same colour that maybe my answer too, took min of all possible answer. Got WA on 2nd test:( is the approach wrong?  » 18 months ago, # | 0 Any hacks for A ? •  » » 18 months ago, # ^ | 0 Difficult to find, unless the code is designed only to be hacked.Example : Here you go  » 18 months ago, # | -6 Couldn't even do A •  » » 18 months ago, # ^ | 0 It was so frustrating lol •  » » 18 months ago, # ^ | ← Rev. 2 → 0 :(  » 18 months ago, # | 0 how do they calculate the penalty in educational rounds? •  » » 18 months ago, # ^ | ← Rev. 2 → 0 Summation of total time taken for each problem.Suppose you solve problem A in 10mins and Problem B in next 15 mins.Then total penalty is (10 + (15 + 10) + extra time penalty for previous wrong submissions) mins Or basically just sum up the time shown below your submissions in the ranklist and add extra time penalty for wrong submissions )  » 18 months ago, # | -42 Statement of D was very confusing is there any sense for using same letter$(c)$to denote colors as well as multiplication of permutations? •  » » 18 months ago, # ^ | 0 wow I didn't even notice that •  » » 18 months ago, # ^ | +38 Sorry, my bad. I didn't notice it.But is there any sense for registering a fake account to express your opinion?  » 18 months ago, # | ← Rev. 2 → 0 As I know little about replacement I think E is much easier than D... But I didn't try to solve E on the contest...  » 18 months ago, # | +4 Problem B: how fast is your reading comprehension  » 18 months ago, # | 0 Were today's A,B,C easier than usual educational round problems ? •  » » 18 months ago, # ^ | 0 Easy but Tricky I would say. :D  » 18 months ago, # | 0 A long time ago, I used an extension that computed approximate rating changes before official results were out. Can anyone send link to that? •  » » 18 months ago, # ^ | 0 •  » » » 18 months ago, # ^ | 0 Thanks •  » » » 18 months ago, # ^ | ← Rev. 2 → +5 Isn't it generally a bit off for Educational Rounds? •  » » » » 18 months ago, # ^ | 0 No idea •  » » 18 months ago, # ^ | ← Rev. 2 → +2 Here's the extension ,also available in Firefox extension store. •  » » 18 months ago, # ^ | +1 CF-Predictor  » 18 months ago, # | 0 Is this kind of self-hacking allowed? https://codeforces.com/contest/1327/submission/74121343It seems kind of obvious and shameful that people would stoop to such low levels. Very disappointed. •  » » 18 months ago, # ^ | 0 Doesn't really matter since you get no points for hacking. Infact it atleast makes it fairer for other contestants, since the hacked user's rank worsens.  » 18 months ago, # | 0 why does the problem D (1327D - Infinite Path) have so many tags  » 18 months ago, # | -9 In Problem D, it says that the answer always exists.I maybe wrong, but I feel that for this testcase the answer doesn't exist. 1 4 2 1 4 3 4 3 1 2I don't think an answer exists. because the p^2 = 1234 p^3 = 2143 .......... and so on. We never get an answer here. Please correct me if I am wrong. •  » » 18 months ago, # ^ | +1 On p^2 we already get the answer, start the infinite sequence with any index you still end up at the same index. And same index has same color.  » 18 months ago, # | -14 Bad Day for me. On looking the number of submissions, i thought E is more easier than D but failed to solve E at the time of contest. Later on i found D was more easier for me than E.Did you guys solved any problem similar to E before?? •  » » 18 months ago, # ^ | +4 I think E is much easier than D... E is straightforward combinatorics problem isnt it? •  » » » 18 months ago, # ^ | ← Rev. 2 → 0 You don't even need combinatorics. I just calculated sequence for first 1 <= n <= 6 digit numbers and with some observation constructed the sequence.PS: This might not be a good way of solving problems like this, but that's what i did. •  » » » 18 months ago, # ^ | 0 Well i am weak in combinatorics but after the contest i upsolved it using prefix sum. My Solution  » 18 months ago, # | ← Rev. 2 → +5 You can try to think about a clever solution for problem E... ooor you can brute force first values and let Berlekamp Massey do its magic finding a linear recurrence that solves the problem without understanding anything of what it is doing: submission :P •  » » 18 months ago, # ^ | +5 I like the way you think haha  » 18 months ago, # | ← Rev. 3 → 0 I tried to minimize the number of operations required for problem C . The logic roughly goes as: I find the point which is closest to it's target and take it there in min steps updating all other points, and keep repeating this. This might not be optimal but takes less steps atleast than the solution of most.But I'm getting some wierd Diagnostics issue and hence a WA on Test 4, although my output is correct.https://codeforces.com/contest/1327/submission/74139658Can someone help out?  » 18 months ago, # | -7 Quick tutorial  » 18 months ago, # | +48 •  » » 18 months ago, # ^ | +7 Thank you..!  » 18 months ago, # | 0 Why so much delay in the editorial ? •  » » 18 months ago, # ^ | 0 It will probably come after system testing. •  » » » 18 months ago, # ^ | -11 After everyone has upsolved.  » 18 months ago, # | 0 Can someone explain the problem statement for D?  » 18 months ago, # | 0 in problem D: for this input: 1 3 2 3 1 1 2 3 I ran it on an accepted solution and it got 3 can anyone please explain to me why? •  » » 18 months ago, # ^ | -10$ \forall \sigma \in S_n, \sigma^n = \mathrm{Id} $.You get$ n $classes of color equivalence, each with 1 element, so the answer is at most 3.But it can't be less than 3, because otherwise you get a cycle of length 3 and it contains 3 colors. •  » » » 18 months ago, # ^ | 0 P^1 = 2 3 1 , P^2 = 3 1 2 , P^3 = 2 3 1 and 2 3 1 doesn't have an infinite path •  » » » » 18 months ago, # ^ | 0 P^3 is in fact 1 2 3. •  » » » » » 18 months ago, # ^ | ← Rev. 2 → 0 How is P^3 = 1 2 3 can you please show me the steps for it to be 1 2 3 •  » » » » » » 18 months ago, # ^ | +4$ P $= 2, 3, 1$ P^2 $= 3, 1, 2$ P^3[1] = P^2[P[1]] = P^2[2] = 1 $.$ P^3[2] = P^2[P[2]] = P^2[3] = 2 $.$ P^3[3] = 3 $, because$ P^3 $is a permutation of$ { 1, 2, 3 } $. •  » » » » » » » 18 months ago, # ^ | 0 thanks a lot •  » » » » » » » » 18 months ago, # ^ | -6 How are we calculationg P^2 •  » » » 18 months ago, # ^ | ← Rev. 4 → 0 Haha, I tried to prove and lol now I have a counterexample for that statement.$ P = (1 2 3) (4 5 6 7) (8) $.Order of$ P $is$ 12 $, but$ n = 8 $.But in that particular case,$ \sigma^3 = (1)(2)(3) $indeed. •  » » » 18 months ago, # ^ | ← Rev. 2 → +3 Btw this is not true:$\forall \sigma \in S_n, \sigma^n = \mathrm{Id}$Consider$ \sigma = (1)(2 3 4) $.Then,$ \sigma^4 = (1)(2 3 4) $and not$Id$.  » 18 months ago, # | 0 For problem E this can help https://oeis.org/A255380 As in the given link it's for special case 10. we didn't need that , so in the formula just remove a(n-11) that's all.Overall didn't liked the problem as 'E'. •  » » 18 months ago, # ^ | 0 Thanks for the link! Very interesting problem too.  » 18 months ago, # | 0 Why there are more participants solved E than D? （；´д｀）ゞIn my opinion, it is better to swap D and E. I managed to solve D but then I did not have enough time to solve E. (Honestly I had. But I just kept making foolish mistakes..) Maybe I should stop to solve E instead of insisting on D as soon as I noticed that fact.All in all, nice contest! Like it! (*^▽^*)  » 18 months ago, # | 0 Where is solution?  » 18 months ago, # | +14 How many people solve problem E with OEIS? •  » » 18 months ago, # ^ | 0 can you first explain to me question E?  » 18 months ago, # | +14 Thanks to codeforces for giving us opportunity to participate in too many contests. I have a request. Please make contests more frequent during this hard time.  » 18 months ago, # | +2 I hope will finally become purple today, thanks for the contest.  » 18 months ago, # | 0 When rating will be changed?12 hours hacking phase has been finished....... •  » » 18 months ago, # ^ | ← Rev. 3 → 0 It is done always after the system testing :PThere is a system testing done after the hacking phase •  » » » 18 months ago, # ^ | 0 Are there any rules that after system testing how many times it takes?  » 18 months ago, # | 0 Can anyone please exaplain me question E??  » 18 months ago, # | 0 why dafuq does it happen? my sol of A didnt get accepted bcoz the datatype was int and not long long int. Although it was given that the limits were till 10 to the power 7 •  » » 18 months ago, # ^ | +12$k^2 > 2^{32}\$
•  » » » 18 months ago, # ^ |   0 spookywooky you mean k^2 > (2^31) — 1 ?
•  » » » » 18 months ago, # ^ |   +11 I tried to find the most concise wording, not the mathematically correct one. Your are right, of course.
 »