Привет, Codeforces!
В 23.03.2020 17:35 (Московское время) состоится Educational Codeforces Round 84 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | EvenImage | 7 | 230 |
| 2 | Volkov_Ivan | 7 | 272 |
| 3 | Egor | 7 | 343 |
| 4 | 2829908231 | 7 | 360 |
| 5 | rainboy | 7 | 707 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | atakanysr | 14:-8 |
| 2 | Chrollo_Lucifer | 5:-1 |
| 3 | Learner | 10:-13 |
| 4 | RitikBaid | 3 |
| 5 | Ashiok | 4:-3 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | fextivity | 0:01 |
| B | Sonechko | 0:05 |
| C | Isaunoya | 0:05 |
| D | EvenImage | 0:10 |
| E | AntiBsayer | 0:11 |
| F | YangDavid | 0:35 |
| G | rainboy | 0:44 |
UPD: Разбор опубликован
good luck :D
Only contest can keep us busy during quarantine. :)
Actually thinking about when is the next contest does that ;)
Apparently there are no div 2+ contests until April 3 :( So a long long (note the pun) 9 days wait.
Was that pun INTended?
I guess that pun cannot fall
short.I think cf should double the contest frequency
with no
strings attachedThe 9 days will be
voidof any rating changes for me. :(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 :).
Lands up solving none , Better luck next time Bro.
I solved B in the contest , and solved A after it :) , you too bro :)
Haven't participated an educational round properly before. Can someone tell me if the hacks are accounted in ranking?
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.
Well not necessarily: if the person whose solution I hacked was already beneath me due to submission time. :P
You can make a problem outta that.
Problem A in next contest "predict the rank" lol
That would be too easy to hack.
AHH forget about what I said :)))
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.
D was boring too.
I hope the tasks will be interesting.
I just hope this round will have strong pretests. :D
Всем удачи ! Я желаю вам всем занимать самые высокие места.
I will Focus now
and that is why we never focus on ourselves and lose ratings.
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 :)
Will you stop commenting this in every contest blog?
Teachers say that we loose our time in quarantine and we are doing nothing. LOOK TEACHERS... WE ARE GETTING EDUCATED
Exactly! those college/school hours are boring and gruesome.
Thank you for giving the exact number of problems.
Does it actually matter? would anyone prepare differently for a different number of problems?
Yes.
How?
Extra pen for each problem
We need more contests during the quarantine please! When will we have a contest about Coronavirus?)
Well We don't know if we will be alive To participate That Corona Contest
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.
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.
Thanks man!!
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!!!
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.
Learn new concepts like dsu, graphs, modular arithmetic, dp ect then the solution will come from within
then upsolve the tougher ones. That's actually what makes you capable of solving them in-contest.
Can someone explain me the difference between education codeforces round and normal div2 rounds . TIA
Two biggest differences are the 12 hour open hacking phase and the score distribution (every problem carries the same weight in educational rounds).
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 problem
However, in normal rounds, problem F worths more points than problem A+B
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
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"
Would you please elaborate on point 2. I am not sure I understood. What do you mean "forbidden to copy the code"?
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.
These days we need more and more contests :'D
Hope to learn something new and solve 3 or more question this time. . .
Please... make strong Pretest Cases!!
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.
I really wish a color change this time!
Fingers crossed! All the best everyone.
Good luck for you! Maybe you can even be a specialist or an expert after this round!
My first unofficial Div.2
Only exciting thing to engage me, during this quarantine.
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,,
Hoping for strong pretest this time.
.
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?
contest and chill
17k+ registration Going to be 18k soom Is it effect corona? I hope corona can't attack anyone on other way.
18584 registrations! Still increasing!! All the best everyone!!!
13522 participaters <3
The server is gonna explode. 18K registration O_O
Effect of quarantine due to coronavirus.
It's about time. Good luck everyone
I think that someone should stop coming up with problems
Could you elaborate, please?
There is one person among authors whose problems are usually not really good(its just my opinion)
How do you know who wrote which problem today?
Спасибо awoo за его прекрасные задачи. Поскорей бы следующий educational ...
А что не так? A, B, C, F точно неплохие
Ну скажем честно, F не читал) Но А, Б действительно неплохие.
Есть небольшая проблема: в туре должны быть не только "неплохие" задачи
WrongAnswerforces
WeakObservationForces
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?
D is hard to understand too.
No, it's well written, permutation cycles are denoted in same manner
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.
I found problem C pretty clear. Rather than, problem D was more difficult to understand.
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
I'm so confused that I asked the author like this :p
(row, column) is standard when talking about matrices.
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".
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.
So, how to solve F? Is it inclusion-exclusion on each bit separately?
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:
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 $$$ \lt k$$$ are satisfied.
Could you explain a sketch of a linear time DP?
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 $$$ \lt 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://mirror.codeforces.com/contest/1327/submission/74120243
"let li be the rightmost starting point of the segments with ending points <i. We now know that we need to put a zero somewhere between li and i−1, inclusive (otherwise there is no 0 in said segment)."
Shouldn't we put a zero somewhere between li and ri (where ri is the right border of the segment whose left border is li), instead of between li and i-1?
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$$$.
How to solve E :<
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://mirror.codeforces.com/contest/1327/submission/74125507
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.
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.
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?
The author is deliberately counting the case cdaabaacd twice, because this case contains two consecutive segments.
oh! yeah right, Thanks!
Why did you take both the adjacent digits same ? Shouldn't be the total no of ways be 9*10*9 ?
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
Thanks
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 asX?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 withXcan 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 withX.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.Oh, thanks. It is easy to understand but is that the formula is
yea, but the base case is for n and n-1, not n+1.
latex is so hard ><
haha
XDYou can think
latexas another language :))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 ?
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.
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
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.
if the contest was 2:15 or 2:30 min, then it might be better(since there was 7 qns). Anyhow nice problems.
How to solve D?
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.
Great thanks.
"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?
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.
Why the graph theory interpretation when this is exactly cyclic permutations? https://en.wikipedia.org/wiki/Cyclic_permutation
See my answer https://mirror.codeforces.com/blog/entry/75082?#comment-592145
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?
Think of this as, finding the minimum k such as:
s ≡ s + k * m (mod L). This translates to0 ≡ 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).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).
How to do C?
Push all points to 1 corner then iterate them over every grid of the board .it's no more than 2nm
Since the number of actions is quite big, you can collect all chips in one cell and then just visit all cells.
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
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
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*mwhich will never exceed2*n*msteps.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?
Both n and k should be of same parity and k*k<=n.
Proof? (that $$$k^2 \le n$$$)?
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.
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.
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$$$.
first line is $$$k*(k+1)/2$$$, second line is $$$(k-1)*k/2$$$
Sum of First n odd nos. is n**2.
1=1;
1+3=4;
1+3+5=9;
So k should be <= root(n).
.
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
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
Today's problem E
One can write a simple bruteforce for n = 5 and find this trivially.
Could you please elaborate a bit?
Well done every one :D. Thanks for a nice contest(even though my rating drop :( )
How the hell do you solve A????
https://mirror.codeforces.com/blog/entry/75082?#comment-592022
Short answer
cout<<((((n-=k*k)<0)||(n&1))?"NO":"YES");Details answer
I would like to thank the authors for allowing me to use BM. https://mirror.codeforces.com/contest/1327/submission/74109025
Source — https://mirror.codeforces.com/blog/entry/61306
When you overcomplicate a simple question and become a part of the league of geniosities
I'm going to bookmark it now!!!!! AryaPawn orz
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?
Since all colors are different, we need p[i] = i, smallest k for which this happens is 3.
It should be 3
answer is 3. p^3 = {1,2,3}. SO now you have 3 infinite cycles.
Amazing: 20000+ registered users for this round!
E is much easier than D?
I solved E even earlier than B.
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!
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.
Oh now I feel it is easy! Thank you, clearly explained!
I was doing the exact same thing, but don't know for what god-damn reason I gave up :(
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
2233 has 2 blocks of size 2, so it is right to calculate it 2 times.
There is a common idea behind tasks like this on Codeforces.
In example, there is this sequence for today's E
Looks like I missed the 3rd step :(
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.
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.
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
literally took two hours to solve D :D
I don't know why but my rating decreases in every Educational Round...Get educated....
Same xD every educational round brought us a whole "strange" problem that made us confused a lot
Your rating just went up by 42 points...
Yeah I didn't see that coming. [facepalm]
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?
Where does the log come from? I had no log and can't see where you would get it.
How to solve D? please
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
My solution has solution O(n * divs(n)) without the log factor.
O(n sqrt(n)), but actually it's O(160 n) since there are at most 160 factors for number in [1,n].
-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 :'(.
The time complexity is indeed $$$O(n^{4/3} + n\log{n})$$$.
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})$$$"
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})$$$.
How to solve C if we are required to minimize the number of operations ?
Read above.
Why does this code give Runtime Error on Test 1?
https://mirror.codeforces.com/contest/1327/submission/74124335
It works on my machine and I couldn't find any source of undefined behavior in the code.
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]])
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.Got the error. Thanks!
Wow! first time I see this number.
What will you do when you are being quarantined? Of course, you will find anything to kill the time
Hey guys, can anybody explain how to solve E? Thanks
Refer this comment by JKLover : Link
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$$$
Great explanation. Thank you a lot.
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
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.
Мне кажется или этот код https://mirror.codeforces.com/contest/1327/submission/74109662 специально написан так, чтобы его смогли взломать? И его действительно взломали. Зачем это?
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 condition
Are 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??
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?
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.
So in other words, we always have a solution?
Yes, indeed :)
Besides, You don't have to minimize the output unless it longer than 2nm .
20K registration !!...happy quarantine...
How to solve G?
You build an Aho-Corasick automaton from the
t_istrings and then do a dp over the automaton states and the set of characters you've already used.So, for a bitmask
mand a Aho-Corasick states,dp[m][s]would be the highest value attainable using the characters corresponding to the set bits inmfor the firstpopcount(m)question marks, while ending in states. 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.
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.
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?
Any hacks for A ?
Difficult to find, unless the code is designed only to be hacked.
Example : Here you go
how do they calculate the penalty in educational rounds?
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 )
Statement of D was very confusing is there any sense for using same letter $$$(c)$$$ to denote colors as well as multiplication of permutations?
Sorry, my bad. I didn't notice it.
But is there any sense for registering a fake account to express your opinion?
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...
Problem B: how fast is your reading comprehension
Were today's A,B,C easier than usual educational round problems ?
Easy but Tricky I would say. :D
A long time ago, I used an extension that computed approximate rating changes before official results were out. Can anyone send link to that?
https://cf-predictor-frontend.herokuapp.com/contestSelector.html
Thanks
Isn't it generally a bit off for Educational Rounds?
https://chrome.google.com/webstore/detail/cf-predictor/ocfloejijfhhkkdmheodbaanephbnfhn?hl=en
Here's the extension ,also available in Firefox extension store.
CF-Predictor
Is this kind of self-hacking allowed? https://mirror.codeforces.com/contest/1327/submission/74121343
It seems kind of obvious and shameful that people would stoop to such low levels. Very disappointed.
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.
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 2
I 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.
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.
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??
I think E is much easier than D... E is straightforward combinatorics problem isnt it?
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.
Well i am weak in combinatorics but after the contest i upsolved it using prefix sum. My Solution
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
I like the way you think haha
System showing me a message "illegal id" whenever I try to hack a solution of another guy, can anyone tell me what's the problem here doing that?
A video explanation of problem E
Thank you..!
Why so much delay in the editorial ?
It will probably come after system testing.
Can someone explain the problem statement for D?
Can someone explain the problem statement for D?
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?
$$$ \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.
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
P^3 is in fact 1 2 3.
How is P^3 = 1 2 3 can you please show me the steps for it to be 1 2 3
$$$ 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 } $$$.
thanks a lot
How are we calculationg P^2
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.
Btw this is not true:
Consider $$$ \sigma = (1)(2 3 4) $$$.
Then, $$$ \sigma^4 = (1)(2 3 4) $$$ and not $$$Id$$$.
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'.
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! (*^▽^*)
How many people solve problem E with OEIS?
can you first explain to me question E?
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.
I hope will finally become purple today, thanks for the contest.
When rating will be changed?
12 hours hacking phase has been finished.......
It is done always after the system testing :P
There is a system testing done after the hacking phase
Can anyone please exaplain me question E??
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
$$$k^2 \gt 2^{32}$$$
spookywooky you mean k^2 > (2^31) — 1 ?
I tried to find the most concise wording, not the mathematically correct one. Your are right, of course.
Will there be official Editorial?Thanks.
Mr Editorial, the stage is yours, bring it up!
https://mirror.codeforces.com/contest/1327/submission/74166346 what's wrong in my code for E?
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.
For Problem D, Can somebody help me understand the complexity difference between these solutions?
AC — 74168483
TLE — 74168686
Note: 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.
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$$$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.
When can we see the rating changes ?
The ratings are updated now
CF-Rating Predictor showing -5, the rating updated by +5 :P
It was because it takes into account the red participants as well.
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.
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 :(It seems dp digitable, since no block of numbers will be formed from 3 consecutive numbers.
Where is the editorial ?
Please upload the editorial!!
the announcement "Digits from different numbers don't from blocks", what does that mean? I don't really understand.
I think the word "from blocks" might be "form blocks"...
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 1
is 2 . I am getting 4.
Thanks!!
do you mean:
?
Yes.
But, 4 is correct. Why did you get the idea that it's 2?
Yeah, exactly. I am also getting 4. But the answer given is 2.
Oooops. Wanted to post this comment under announcement of introducing 64bit system
Why does O(N^2) work for DIV2 B ? Can anyone provide a source where I can learn how to estimate the time complexity required properly .... I thought that O(NK) wouldn't work in B because N was given as 2* 10^5 and thus couldn't solve it during the contest. Thanks in advance !
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.
"It's also guaranteed that the total number of kingdoms in lists over all test cases does not exceed 10^5."
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.
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 ?
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.
For example, what is the complexity of DFS?
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.
Thank you ! I will be much more careful now while estimating complexities !
I messed up in this round :(
The second approach. I also solved it using the 1st approach first. And got a — 1.
is editorial qurantined
I think the author of this round forgot to add the editorial. :(
In B ... can more than one daughter marry same princes...?
Nope, it's mentioned in the problem clearly. Polycarp doesn't want his daughters caught up in polygamy.
I want editorial...
and i want rose ;)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
del
EDU 84 became invisible from everyone's profile's contest section but ratings still exist. Maybe some updates/changes are coming.
Добавьте разбор в материалы соревнования.
Can anyone please tell me why this solution of mine wouldn't work? https://mirror.codeforces.com/contest/1327/submission/74190187 I have shifted all pieces first to extreme right, then extreme down. After that I have traversed all blocks in the matrix one by one.
Your code only sweeps row n to row 2. You forgot to sweep row 1.
Uploaded solution videos for A-E on this link.
https://www.youtube.com/playlist?list=PLl4Y2XuUavmuDC4ZST4F_peD1jO_xvVfW