By awoo, history, 3 years 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 amiya 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 atakanysr 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 amiya 0:10
E El3ageed_Abu_Shehab 0:11
F YangDavid 0:35
G rainboy 0:44

UPD: Editorial is out

• +344

| Write comment?
 » 3 years ago, # |   0 good luck :D
•  » » 3 years ago, # ^ |   +117 Only contest can keep us busy during quarantine. :)
•  » » » 3 years ago, # ^ |   +44 Actually thinking about when is the next contest does that ;)
•  » » » » 3 years ago, # ^ |   +34 Apparently there are no div 2+ contests until April 3 :( So a long long (note the pun) 9 days wait.
•  » » » » » 3 years ago, # ^ |   +47 Was that pun INTended?
•  » » » » » 3 years ago, # ^ |   +41 I guess that pun cannot fall short.
•  » » » » » 3 years ago, # ^ |   +58 I think cf should double the contest frequency
•  » » » » » » 3 years ago, # ^ |   +3 with no strings attached
•  » » » » » 3 years ago, # ^ |   +13 The 9 days will be void of any rating changes for me. :(
 » 3 years 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 :).
•  » » 3 years ago, # ^ |   +9 Lands up solving none , Better luck next time Bro.
•  » » » 3 years ago, # ^ |   +1 I solved B in the contest , and solved A after it :) , you too bro :)
 » 3 years ago, # |   0 Haven't participated an educational round properly before. Can someone tell me if the hacks are accounted in ranking?
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +4 Well not necessarily: if the person whose solution I hacked was already beneath me due to submission time. :P
•  » » » » 3 years ago, # ^ |   +70 You can make a problem outta that.
•  » » » » » 3 years ago, # ^ |   +2 Problem A in next contest "predict the rank" lol
•  » » » » » » 3 years ago, # ^ |   +3 That would be too easy to hack.
 » 3 years ago, # | ← Rev. 2 →   -15 AHH forget about what I said :)))
 » 3 years 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.
•  » » 3 years ago, # ^ |   -26 D was boring too.
 » 3 years ago, # |   0 I hope the tasks will be interesting.
 » 3 years ago, # |   +34 I just hope this round will have strong pretests. :D
 » 3 years ago, # | ← Rev. 2 →   -117 I will Focus now
•  » » 3 years ago, # ^ |   +27 and that is why we never focus on ourselves and lose ratings.
•  » » 3 years 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 :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +159 Will you stop commenting this in every contest blog?
 » 3 years ago, # |   +68 Teachers say that we loose our time in quarantine and we are doing nothing. LOOK TEACHERS... WE ARE GETTING EDUCATED
•  » » 3 years ago, # ^ |   +10 Exactly! those college/school hours are boring and gruesome.
 » 3 years ago, # |   +7 Thank you for giving the exact number of problems.
•  » » 3 years ago, # ^ |   +44 Does it actually matter? would anyone prepare differently for a different number of problems?
•  » » » 3 years ago, # ^ |   -12 Yes.
•  » » » » 3 years ago, # ^ |   +3 How?
•  » » » » » 3 years ago, # ^ |   +123 Extra pen for each problem
 » 3 years ago, # |   +50 We need more contests during the quarantine please! When will we have a contest about Coronavirus?)
•  » » 3 years ago, # ^ |   +14 Well We don't know if we will be alive To participate That Corona Contest
 » 3 years 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.
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +9 Thanks man!!
•  » » » 3 years 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!!!
•  » » » » 3 years 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.
•  » » » » 3 years ago, # ^ |   +3 Learn new concepts like dsu, graphs, modular arithmetic, dp ect then the solution will come from within
•  » » 3 years ago, # ^ |   0 then upsolve the tougher ones. That's actually what makes you capable of solving them in-contest.
 » 3 years ago, # |   +5 Can someone explain me the difference between education codeforces round and normal div2 rounds . TIA
•  » » 3 years 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).
•  » » 3 years 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"
•  » » » 3 years ago, # ^ |   0 Would you please elaborate on point 2. I am not sure I understood. What do you mean "forbidden to copy the code"?
•  » » » » 3 years 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.
 » 3 years ago, # |   +46 These days we need more and more contests :'D
 » 3 years ago, # |   +2 Hope to learn something new and solve 3 or more question this time. . .
 » 3 years ago, # |   +12 Please... make strong Pretest Cases!!
 » 3 years 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.
 » 3 years ago, # |   +2 I really wish a color change this time!Fingers crossed! All the best everyone.
•  » » 3 years ago, # ^ |   +13 Good luck for you! Maybe you can even be a specialist or an expert after this round!
 » 3 years ago, # |   -12 My first unofficial Div.2
 » 3 years ago, # |   +6 Only exciting thing to engage me, during this quarantine.
 » 3 years 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,,
 » 3 years ago, # |   +15 Hoping for strong pretest this time.
 » 3 years ago, # | ← Rev. 2 →   +5 .
 » 3 years 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?
 » 3 years ago, # |   +6 contest and chill
 » 3 years ago, # |   0 17k+ registration Going to be 18k soom Is it effect corona? I hope corona can't attack anyone on other way.
 » 3 years ago, # |   +66 Monday Educational 18k participants
 » 3 years ago, # | ← Rev. 2 →   +12 18584 registrations! Still increasing!! All the best everyone!!!
•  » » 3 years ago, # ^ |   +2 13522 participaters <3
 » 3 years ago, # | ← Rev. 2 →   +30 The server is gonna explode. 18K registration O_O
•  » » 3 years ago, # ^ |   +4 Effect of quarantine due to coronavirus.
 » 3 years ago, # |   0 It's about time. Good luck everyone
 » 3 years ago, # |   +35 I think that someone should stop coming up with problems
•  » » 3 years ago, # ^ |   +26 Could you elaborate, please?
•  » » » 3 years ago, # ^ |   -18 There is one person among authors whose problems are usually not really good(its just my opinion)
•  » » » » 3 years ago, # ^ |   +37 How do you know who wrote which problem today?
 » 3 years ago, # |   -29 WrongAnswerforces
•  » » 3 years ago, # ^ |   -18 WeakObservationForces
 » 3 years 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?
•  » » 3 years ago, # ^ |   +8 D is hard to understand too.
•  » » » 3 years ago, # ^ |   0 No, it's well written, permutation cycles are denoted in same manner
•  » » 3 years 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.
•  » » 3 years ago, # ^ |   0 I found problem C pretty clear. Rather than, problem D was more difficult to understand.
•  » » 3 years 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
•  » » 3 years ago, # ^ |   +21 I'm so confused that I asked the author like this :p
•  » » 3 years ago, # ^ |   +41 (row, column) is standard when talking about matrices.
•  » » 3 years 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".
•  » » 3 years 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.
 » 3 years ago, # |   +8 So, how to solve F? Is it inclusion-exclusion on each bit separately?
•  » » 3 years 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.
•  » » 3 years 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 $•  » » » 3 years ago, # ^ | +8 Could you explain a sketch of a linear time DP? •  » » » » 3 years 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 •  » » » » » 3 years ago, # ^ | +1 "let li be the rightmost starting point of the segments with ending points •  » » » » » » 3 years 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$.  » 3 years ago, # | ← Rev. 6 → +11 How to solve E :< •  » » 3 years 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 •  » » » 3 years 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. •  » » » » 3 years 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. •  » » » » » 3 years 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? •  » » » » » » 3 years ago, # ^ | +2 The author is deliberately counting the case cdaabaacd twice, because this case contains two consecutive segments. •  » » » » » » » 3 years ago, # ^ | 0 oh! yeah right, Thanks! •  » » » 3 years 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 ? •  » » » » 3 years 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 •  » » » 3 years ago, # ^ | 0 Thanks •  » » 3 years 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. •  » » » 3 years 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];  •  » » » » 3 years 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 >< •  » » » » » 3 years ago, # ^ | 0 haha XD •  » » » » » 3 years ago, # ^ | 0 You can think latex as another language :)) •  » » » 3 years 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 ? •  » » » » 3 years 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. •  » » 3 years 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  » 3 years 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.  » 3 years 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.  » 3 years ago, # | +26 How to solve D? •  » » 3 years 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. •  » » » 3 years ago, # ^ | 0 Great thanks. •  » » » 3 years 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? •  » » » » 3 years 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. •  » » » 3 years ago, # ^ | +6 Why the graph theory interpretation when this is exactly cyclic permutations? https://en.wikipedia.org/wiki/Cyclic_permutation •  » » » 3 years 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? •  » » » » 3 years 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). •  » » 3 years 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).  » 3 years ago, # | +2 How to do C? •  » » 3 years 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 •  » » 3 years ago, # ^ | +1 Since the number of actions is quite big, you can collect all chips in one cell and then just visit all cells. •  » » 3 years 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 •  » » 3 years 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 •  » » 3 years 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.  » 3 years 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? •  » » 3 years ago, # ^ | 0 Both n and k should be of same parity and k*k<=n. •  » » » 3 years ago, # ^ | ← Rev. 2 → 0 Proof? (that$k^2 \le n$)? •  » » » » 3 years 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. •  » » » » 3 years 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. •  » » » » » 3 years 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$. •  » » » » » » 3 years 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$•  » » » » 3 years 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). •  » » » 3 years ago, # ^ | ← Rev. 2 → 0 . •  » » 3 years 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 •  » » 3 years 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  » 3 years ago, # | ← Rev. 2 → +33 Today's problem EOne can write a simple bruteforce for n = 5 and find this trivially. •  » » 3 years ago, # ^ | +5 Could you please elaborate a bit?  » 3 years ago, # | 0 Well done every one :D. Thanks for a nice contest(even though my rating drop :( )  » 3 years ago, # | 0 How the hell do you solve A???? •  » » 3 years ago, # ^ | 0 •  » » 3 years 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";   » 3 years ago, # | +5 I would like to thank the authors for allowing me to use BM. https://codeforces.com/contest/1327/submission/74109025 •  » » 3 years ago, # ^ | +25 When you overcomplicate a simple question and become a part of the league of geniosities •  » » » 3 years ago, # ^ | +4 •  » » 3 years ago, # ^ | ← Rev. 2 → 0 I'm going to bookmark it now!!!!! AryaPawn orz  » 3 years 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? •  » » 3 years ago, # ^ | 0 Since all colors are different, we need p[i] = i, smallest k for which this happens is 3. •  » » 3 years ago, # ^ | 0 It should be 3 •  » » 3 years ago, # ^ | 0 answer is 3. p^3 = {1,2,3}. SO now you have 3 infinite cycles.  » 3 years ago, # | +28 Amazing: 20000+ registered users for this round!  » 3 years ago, # | +6 E is much easier than D? I solved E even earlier than B. •  » » 3 years 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! •  » » » 3 years 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. •  » » » » 3 years ago, # ^ | +5 Oh now I feel it is easy! Thank you, clearly explained! •  » » » » 3 years ago, # ^ | 0 I was doing the exact same thing, but don't know for what god-damn reason I gave up :( •  » » » » 3 years 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 •  » » » » » 3 years ago, # ^ | +1 2233 has 2 blocks of size 2, so it is right to calculate it 2 times. •  » » » 3 years 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 •  » » » » 3 years ago, # ^ | 0 Looks like I missed the 3rd step :( •  » » 3 years 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. •  » » » 3 years 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. •  » » » 3 years 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 •  » » 3 years ago, # ^ | 0 literally took two hours to solve D :D  » 3 years ago, # | +11 I don't know why but my rating decreases in every Educational Round...Get educated.... •  » » 3 years ago, # ^ | 0 Same xD every educational round brought us a whole "strange" problem that made us confused a lot •  » » 3 years ago, # ^ | 0 Your rating just went up by 42 points... •  » » » 3 years ago, # ^ | 0 Yeah I didn't see that coming. [facepalm]  » 3 years 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? •  » » 3 years ago, # ^ | +21 Where does the log come from? I had no log and can't see where you would get it. •  » » » 3 years ago, # ^ | 0 How to solve D? please •  » » » 3 years 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 •  » » 3 years ago, # ^ | +10 My solution has solution O(n * divs(n)) without the log factor. •  » » 3 years 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]. •  » » 3 years 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 :'(. •  » » 3 years ago, # ^ | 0 The time complexity is indeed$O(n^{4/3} + n\log{n})$. •  » » » 3 years 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})$" •  » » » » 3 years 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})$.  » 3 years ago, # | ← Rev. 3 → +4 How to solve C if we are required to minimize the number of operations ? •  » » 3 years ago, # ^ | 0 Read above.  » 3 years 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. •  » » 3 years 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]]) •  » » 3 years 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. •  » » 3 years ago, # ^ | 0 Got the error. Thanks!  » 3 years ago, # | ← Rev. 2 → +26 Wow! first time I see this number. •  » » 3 years ago, # ^ | 0 What will you do when you are being quarantined? Of course, you will find anything to kill the time  » 3 years ago, # | +3 Hey guys, can anybody explain how to solve E? Thanks •  » » 3 years ago, # ^ | +3 Refer this comment by JKLover : Link •  » » 3 years 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$•  » » » 3 years ago, # ^ | +6 Great explanation. Thank you a lot. •  » » » 3 years 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 •  » » » » 3 years 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.  » 3 years 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?? •  » » 3 years 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? •  » » 3 years 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. •  » » » 3 years ago, # ^ | 0 So in other words, we always have a solution? •  » » » » 3 years ago, # ^ | 0 Yes, indeed :) •  » » 3 years ago, # ^ | +3 Besides, You don't have to minimize the output unless it longer than 2nm .  » 3 years ago, # | +17 20K registration !!...happy quarantine...  » 3 years ago, # | +16 How to solve G? •  » » 3 years 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. •  » » 3 years 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.  » 3 years 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?  » 3 years ago, # | 0 Any hacks for A ? •  » » 3 years ago, # ^ | 0 Difficult to find, unless the code is designed only to be hacked.Example : Here you go  » 3 years ago, # | 0 how do they calculate the penalty in educational rounds? •  » » 3 years 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 )  » 3 years 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? •  » » 3 years ago, # ^ | +38 Sorry, my bad. I didn't notice it.But is there any sense for registering a fake account to express your opinion?  » 3 years 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...  » 3 years ago, # | +4 Problem B: how fast is your reading comprehension  » 3 years ago, # | 0 Were today's A,B,C easier than usual educational round problems ? •  » » 3 years ago, # ^ | 0 Easy but Tricky I would say. :D  » 3 years 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? •  » » 3 years ago, # ^ | 0 •  » » » 3 years ago, # ^ | 0 Thanks •  » » » 3 years ago, # ^ | ← Rev. 2 → +5 Isn't it generally a bit off for Educational Rounds? •  » » 3 years ago, # ^ | ← Rev. 2 → +2 Here's the extension ,also available in Firefox extension store. •  » » 3 years ago, # ^ | +1 CF-Predictor  » 3 years 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. •  » » 3 years 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.  » 3 years 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. •  » » 3 years 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.  » 3 years 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?? •  » » 3 years ago, # ^ | +4 I think E is much easier than D... E is straightforward combinatorics problem isnt it? •  » » » 3 years 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. •  » » » 3 years ago, # ^ | 0 Well i am weak in combinatorics but after the contest i upsolved it using prefix sum. My Solution  » 3 years 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 •  » » 3 years ago, # ^ | +5 I like the way you think haha  » 3 years ago, # | +48 •  » » 3 years ago, # ^ | +7 Thank you..!  » 3 years ago, # | 0 Why so much delay in the editorial ? •  » » 3 years ago, # ^ | 0 It will probably come after system testing.  » 3 years ago, # | 0 Can someone explain the problem statement for D?  » 3 years 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? •  » » 3 years 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. •  » » » 3 years 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 •  » » » » 3 years ago, # ^ | 0 P^3 is in fact 1 2 3. •  » » » » » 3 years 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 •  » » » » » » 3 years 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 } $. •  » » » » » » » 3 years ago, # ^ | 0 thanks a lot •  » » » » » » » » 3 years ago, # ^ | -6 How are we calculationg P^2 •  » » » 3 years 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. •  » » » 3 years 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$.  » 3 years 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'.  » 3 years 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! (*^▽^*)  » 3 years ago, # | +14 How many people solve problem E with OEIS? •  » » 3 years ago, # ^ | 0 can you first explain to me question E?  » 3 years 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.  » 3 years ago, # | +2 I hope will finally become purple today, thanks for the contest.  » 3 years ago, # | 0 When rating will be changed?12 hours hacking phase has been finished....... •  » » 3 years ago, # ^ | ← Rev. 3 → 0 It is done always after the system testing :PThere is a system testing done after the hacking phase  » 3 years ago, # | 0 Can anyone please exaplain me question E??  » 3 years 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 •  » » 3 years ago, # ^ | +12$k^2 > 2^{32}$•  » » » 3 years ago, # ^ | 0 spookywooky you mean k^2 > (2^31) — 1 ? •  » » » » 3 years ago, # ^ | +11 I tried to find the most concise wording, not the mathematically correct one. Your are right, of course.  » 3 years ago, # | +3 Will there be official Editorial?Thanks. •  » » 3 years ago, # ^ | 0 Mr Editorial, the stage is yours, bring it up!  » 3 years ago, # | 0 https://codeforces.com/contest/1327/submission/74166346 what's wrong in my code for E? •  » » 3 years ago, # ^ | ← Rev. 3 → 0 Your logic seems wrong, wait for the Editorial.Other than that, You forgot to use MOD at many places. You'll be printing negative values many-times.  » 3 years ago, # | ← Rev. 3 → +17 For Problem D, Can somebody help me understand the complexity difference between these solutions?AC — 74168483TLE — 74168686Note: Both of these are my submissions, only difference is in solve function (that iterates over factors and finds the ans)Edit: Use of unordered_map, map, or any other hash table is slowing the solution by order of 10. •  » » 3 years ago, # ^ | 0 i only noticed the additional logN in the complexity. Maybe that's enough to give TLE.But, instead of using map, you can just use an array. And don't do this: st[((k%j)<<30LL)+ v[k]]++;. Just do simple if else. If the current loop is not yet colored (first time getting colored), then color it. If somehow in the middle the color changes, the loop is invalid •  » » 3 years ago, # ^ | 0$len(fac)*(len(v)*log(len(v))+len(fac))$-TLE$len(fac)*log(fac)+len(fac)*(sum(fac)*log(len(v))$-AC ($log(len(v))\$ if numbers are distinct in v) I think.
 » 3 years ago, # |   0 When can we see the rating changes ?
•  » » 3 years ago, # ^ |   0 The ratings are updated now
 » 3 years ago, # |   +5 CF-Rating Predictor showing -5, the rating updated by +5 :P
•  » » 3 years ago, # ^ |   0 It was because it takes into account the red participants as well.
•  » » » 3 years ago, # ^ |   +11 Earlier, it didn't used to consider the out of contest participants. And after the contest, specifically after the ratings update, it shows exactly the same as the update in the rating.
 » 3 years ago, # |   0 E is quite simple and easy to implement. But how about deleting the ',' (That means the string is like 001002003004...999)? How can this task be solved? Sorry about my poor English and mathematics :(
•  » » 3 years ago, # ^ |   0 It seems dp digitable, since no block of numbers will be formed from 3 consecutive numbers.
 » 3 years ago, # |   +5 Where is the editorial ?
 » 3 years ago, # |   0 the announcement "Digits from different numbers don't from blocks", what does that mean? I don't really understand.
•  » » 3 years ago, # ^ |   +3 I think the word "from blocks" might be "form blocks"...
 » 3 years ago, # |   0 Can somebody please explain why should the ans for Problem D fot the input test case : 1 4 2 4 1 3 2 1 2 1is 2 . I am getting 4.Thanks!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 do you mean: 1 4 2 4 1 3 2 1 2 1 ?
•  » » » 3 years ago, # ^ |   0 Yes.
•  » » » » 3 years ago, # ^ |   0 But, 4 is correct. Why did you get the idea that it's 2?
•  » » » » » 3 years ago, # ^ |   0 Yeah, exactly. I am also getting 4. But the answer given is 2.
 » 3 years ago, # | ← Rev. 3 →   0 Oooops. Wanted to post this comment under announcement of introducing 64bit system
 » 3 years ago, # |   0 Why does O(NK) work for DIV2 B ? Can anyone provide a source where I can learn how to estimate the required time complexity properly ... I thought that O(NK) wouldn't work for B because N was given as 2* 10^5 and K <= N and thus couldn't come up with a solution.
•  » » 3 years ago, # ^ |   +1 "It's also guaranteed that the total number of kingdoms in lists over all test cases does not exceed 10^5."
•  » » 3 years ago, # ^ |   +1 It is O(N+sum(g_i)) which is O(N+K), as you do not do K operations N times, you do g_i operations each time.
•  » » » 3 years ago, # ^ |   0 Thanks for you reply ! I kind of now understand where I went wrong with the calculation. Any source where I can learn how to estimate the required time complexity properly ?
•  » » » » 3 years ago, # ^ |   0 Well, aside from this trick, I don't know what is there to learn. Just maybe try to count number of operations in different ways. TL;DRFor example, what is the complexity of DFS? Codevoid dfs(int v) { used[v] = true; for (int i = 0; i < g[v].size(); ++i) if (!used[g[v][i]]) dfs(g[v][i]); } for (int i = 0; i < n; ++i) if (!used[i]) dfs(i) What you see here is N calls of dfs, where you have recursive calls, each containing a loop of potentially over N vertices. So, depending how good is your estimate for the recursive calls, you could expect O(N^3) or O(N^2). The latter is correct, if only a constraint for N is given.However, if the constraint for M (number of edges) is also given, you might want to use it as well. So, let's count how many times you call dfs(). There are N initial calls (from the main loop). Recursive calls only occur at the condition when used[g[v][i]] == false, and at the next step (when you enter dfs) this value becomes true, so for each vertex this call will be made at maximum once. So there will be O(N) dfs() calls. However, each call also includes a loop over g[v].size() elements. Again, you can estimate it as O(sum_over_all_v(g[v].size())) <= O(N * max(g[v].size())) <= O(N * N). But if you consider that sum_over_all_v(g[v].size()) = 2 * M (sum of all vertex degrees), your estimate will become O(M), and total complexity will be O(N*M). In short, don't be too hasty in raising estimate of your loops.
•  » » » » » 3 years ago, # ^ |   0 Thank you ! I will be much more careful now while estimating complexities !
 » 3 years ago, # | ← Rev. 2 →   0 I messed up in this round :(
•  » » 3 years ago, # ^ |   0 The second approach. I also solved it using the 1st approach first. And got a — 1.
 » 3 years ago, # |   +11 is editorial qurantined
•  » » 3 years ago, # ^ |   0 I think the author of this round forgot to add the editorial. :(
 » 3 years ago, # |   0 In B ... can more than one daughter marry same princes...?
•  » » 3 years ago, # ^ |   +3 Nope, it's mentioned in the problem clearly. Polycarp doesn't want his daughters caught up in polygamy.
 » 3 years ago, # |   +8 I want editorial...
•  » »