Привет, Codeforces!
В 08.01.2023 17:35 (Московское время) состоится Educational Codeforces Round 141 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces!
Мы рады объявить о втором буткемпе по программированию «Hello Muscat 2023», продолжении серии буткемпов «Hello», организованном Harbour.Space University в сотрудничестве с PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club и Codeforces!
Довольно впечатляюще, не так ли? Пришло время глубже погрузиться в мир соревновательного программирования с 8-дневным интенсивом Hello Muscat 2023. Он будет проходить в Маскате, Оман, и онлайн с 8 по 16 марта 2023 года, доступны оба формата участия.
Наш тренерский состав сочетает в себе талант и опыт, в нем участвуют чемпионы мира ICPC, победители и финалисты, а также легендарные имена из области соревновательного программирования: Михаил Мирзаянов MikeMirzayanov, Егор Дубовик 244mhq, Артем Плоткин Rox, Максим Обозный MaksymOboznyi и Николай Будин budalnik.
Буткемп будет разделен на три дивизиона:
- Дивизион A. станет зеркалом Петрозаводского лагеря программирования. Подходит для команд, которые уже прошли квалификацию на Финал ICPC или стремятся к этому.
- Дивизион B. Разработан, чтобы помочь командам подготовиться к следующему сезону региональных соревнований ICPC. Подходит в качестве введения для команд и студентов, которые только начинают свой путь в мир ICPC и соревнований по программированию в целом.
- Дивизион C. Предназначен для новичков в мире соревновательного программирования.
Типы участия: очное и онлайн
Мы считаем, что участие в нашем буткемпе должно быть доступно для всех команд, где бы они ни находились, и именно поэтому мы сделали очную и онлайн-формы участия. Скидка 20% на раннее бронирование предоставляется университетам и участникам, которые зарегистрируются и оплатят до 31 января 2023 года.
- Очное:
Цена: 1500 € — 1200 €
Что включено: обучение, контесты, доступ к записям лекций, проживание в течение 9 ночей в 4-звездочном отеле Mysk, завтрак и обед, трансфер из гостиницы к месту проведения буткемпа каждый день, развлечения и приветственный подарок.
- Онлайн
Цена: 100 € — 80 €
Что включено: обучение, контесты и доступ к записям лекций.
Удачи в раунде,
Harbour.Space University Team
UPD: Разбор опубликован
Best of luck everyone.As a participant I am going to give best in this contest.
You can do anything, just don't give up!
Good luck everyone. Hope i can solve problem C
I didn't solve the problem C
did you solve b?
Yes! I solved it when there were 5 minutes left before the end of the competition.
B was quite hard for a Div 2 B problem. Man it's really hard to improve in competitive programming, I feel like im stuck. Being stupid also doesn't help.
Hope to get good rank at contest which I am not able to do so in previous rounds
Not able get good rank again
i still remember awoo's favourite problem
Good luck to everyone!!! (I hope that I can solve at least one problem :>)
Wow, I'm back after a year and comments are as cringe as ever. Joining in.
Good luck everyone . Hope I can solve at least one problem.
oh c'mon, you are a lgm. Just solve all :)
.
I think that was a joke...
yes..
good luck have fun
Classic Mathforces
not mathforces, just constructiveforces
oh yes I saved the previous non-blue profile pic somewhere else and I am getting to use it now
I should find a matching green one aswell, given the amount of times I have dropped right after reaching cyan T-T
Any proof for B?
Pretty straightforward after trying to solve for a 1d array instead of matrix
Thanks man! I wrote the solution after so many hit and trials. I need to improve my observation skills for such problems
Thanks man....it was really helpful....I complicated this problem unnecessarily
lol i did a snail
There are $$$n^2-1$$$ possible differences $$$(1\dots n^2-1)$$$. And the chain $$$1, n^2, 2, n^2-1, \dots, \left\lfloor\dfrac{n^2}{2}\right\rfloor, \left\lfloor\dfrac{n^2}{2}\right\rfloor+1$$$ (chain ending correct modulo parity), contains all differences and has $$$n^2$$$ terms, for $$$n^2-1$$$ differences.
nice profile
I code brute force as the max difference can be (n*n-1). Try to create all differences from (n*n-1) to 1.
seriously, what is the point of problems like B, where you have to find some stupid pattern on a grid?
I wasted time thinking that question is asking for only border elements.
Why do you think that is a silly thing to do? It trains observational skills.
Regardless, its not like patterns in grids of numbers are a meaningless or trivial thing to study. There are a ton of problems that can be represented as patterns in grids of numbers.. Doing regression in data analysis for example.
Too much penalty >:( and I thought the condition in problem B is $$$a_i + a_j$$$ instead of $$$|a_i - a_j|$$$.
how did you solved B?
There's at most $$$n ^ 2 - 1$$$ distinct value so we started from $$$1, n ^ 2, 2, n ^ 2 - 1, ... $$$ and apply it to a zig zag path on the matrix.
so my approach for problem C was since the nth player can at max have n wins . so a win against him would increase my chances of having a lesser rank . i tried defeating maximum players from the end. and then sort the number of wins for each player in decreasing order and decide my rank why wouldn't this logic work ?
here's my submission https://codeforces.com/contest/1783/submission/188487469
See this testcase:
People asked for binary search, dp, segment tree problems aand... here we ended up
I think C was a beautiful problem , though B was little annoying to me
D is a dp problem. C can be solved with binary search (or can be solved without it). So, what's the matter?
I didn't mean that, C, D, E are very much algorithmic problems, but many of my friends complained about them being too hard ( I think they are easy)
how to solve c?
The $$$i$$$-th opponent has either $$$i-1$$$ or $$$i$$$ wins, and the $$$i$$$-th opponent will never be better than $$$(i+1)$$$-th. So, if we want to get at least the $$$k$$$-th place, we need to be not worse than the opponent $$$(n+1-k)$$$. That means, we either win $$$(n+1-k)$$$ games, or we win $$$(n-k)$$$ games, but one of our wins is against that opponent. In the first case, just win these games against the opponents we need to prepare the least amount of time (so, we need $$$(n+1-k)$$$ minimums from the array $$$a$$$). The second case is similar — we need the time to prepare to the $$$(n+1-k)$$$-th opponent, and $$$(n-k-1)$$$ other opponents with the minimum preparation time.
Now we can either iterate on the place we take and compute these values efficiently with prefix sums, or do binary search on $$$k$$$.
Most of the good contests I participated in had at least one of them
Problem B was annoying :(
How to solve B?
some pattern based try for n = 4 it will be like
1->16->2->15
13->4->14->3
5->12->6->11
9->8->10->7
how to solve c?
You can solve C by sorting the array and finding the maximum number of people you can defeat with the given m, let's denote it by wins.
1) if wins = 0 or wins = n , then your position will be n-wins + 1 (last or first).
2) If wins >=1 and wins <= n-1, if you could defeat person with a [wins] index (his total wins are equal to wins or wins+1), your position would become one better, so the answer would be n-wins, otherwise n-wins+1. (You could go 1 position higher by having total wins equal to that person.) 188489483
As always Educational rounds are worst.
The whole point of them is to learn (standard) algorithms, not to solve interesting tasks. And I think that $$$A$$$, $$$B$$$, $$$F$$$ and $$$G$$$ are great for that ( educational ) matter.
what does one learn from B?
What Wind_Eagle has said before, how to prove theorems in mathematics. Asking for a construction in CP means that one cannot randomly guess the answer, but must be aware of the proof. And I think it is an okay problem, requiring some basic implementation which is, in fact, useful. I understand that many find it annoying though, which doesn't necessarily make it bad.
is problem c Segtree or vector of priority queues since ai<=1000 or I completely overcomplicated ?
It has to be on Binary Search but this mf B wasted an hour and my mind went blank coz of that so couldn't even think properly about C
Key observation is because each player plays each other the other players will have 1, 2, 3, 4... wins... If you can beat the player with exactly 1 more win than you while still maintaining the optimal number of wins than your place is (n-wins+2), else it is n-wins+1
GOODBYE EXPERT!! These hit and trial B's are the worst
Rounds like these make me wish there was an un-register button on Codeforces just like on Atcoder. Wtf was problem B???
How to solve D? Spent most of my remaining time trying to solve it...
Try thinking about $$$dp_{i,s} := \textrm{the number of possible suffixes of the array starting at } i\textrm{ having } a_{i+1} \textrm{ equal to } s$$$.
The transition will be something like $$$dp_{i,s} = dp_{i+1,a_{i+1}+s} + dp_{i+1, a_{i+1}-s}$$$ depending on whether $$$s = 0$$$.
are we trying to find how many different types of sum are possible at end position after applying all operations. eg. if array is a1,a2,a3,a4, at max answer can 4 with 4 different sum a4+a3+a2,a4+a3-a2,a4-a3+a2,a4-a3-a2 possible at the last position?
Bro I did same as yours appraoch but getting TLE on test 18, can you please see and help me how to avoid it. Link to solution : Solution
I would suggest doing it iterative instead of recursive. Moreover, you have an extra dimension that you can skip (see the explanation of Saul)
Can we solve C using Binary search?
I did it using binary search on the number of people we rank at least as low as. So to beat $$$k$$$ people, I pick the $$$k$$$ weakest opponents (in terms of $$$a_i$$$), if their sum of $$$a_i$$$ is less than $$$m$$$, we can rank $$$n-k+1$$$, there's also another small detail but this is mostly the idea.
Yes, we can binary search answer. When we check mid, we know that we can't lost the n — mid + 1 opponent. Let t = n — mid + 1. So we do it greedily to beat as many opponent as possible. Now there are 2 case : If the number we can beat >= t, we always win because player t can win at most t games. Else(number we can beat = t — 1) if we can beat player t, we can win too because now t win t — 1 games. 188457382
Yes.You can see my submission.
Did we have to check only from prefixes and suffixes in the C problem? Like we try to win against only suffixes or only prefixes or some prefixes and suffixes combined? (for the sorted array)
Is D even DP ? 💀
Yes
A: If min==max no solution, else {min, max, (anything)} is a solution.
B:[1, n^2, 2, n^2-1, 3, n^2-2...] arranged along any path of the matrix
C:Sort the array and you will get an almost-best solution. But it needs an extra check to get the best solution. When you've checked first k opponents with least time to prepare, look for whether you've prepared for the opponent with index k+1. If not, check whether you can remove a prepartion and prepare for (k+1)th opponent.
D:Consider for every possible value of sum(ai*sign_i), where sign_i = 1 or -1. There are at most 180000 different values, and run dp for an O(n*A^2) solution.
E:Seemingly easy inequality problem, but naive implementation will get TLE. For certain k, if all multiples of k are not in any range [bi,ai-1], then k is good. We need a segment tree to check all values of [1,n] in O(n*log(n)).
[E] You don't need a segment tree. Just do range sum using prefix arrays and iterate over all multiples of k for every k.
Ohhhhh I missed it
I just thought about "How to set a range in O(log(n))" and implemented with segment tree
Do I check whether I can prepare for the k+1th opponent in the sorted array or in the orignal array?
Original
Please correct me if I am wrong.
The logic is: If I can beat any k opponents it means I will rank alongside the k+1th person in the rankings right? So I check if I can add a preparation for the next highest opponent which I have not prepared for and remove prep for the lowest index which I have prepared for so as to beat k+1th opponent right? Such that my number of preparations always remain the same so I beat the opponent removed on total number of wins anyway.
If you don't prepare at all, the wins of each other player is their index (1-indexed).
In fact, if the number of preparations is fixed at k, you win k matches, and for each other players with index i, their number of wins will be i-1 (you prepared for it) or i (otherwise). Notice that if i < k+1, then i<=k and i-1<=k, which means whether you prepare or not, the number of wins of i-th player cannot be larger than you. It's similar for i>k+1 (their number of wins will be always larger). So only i=k+1 will matter.
Through this edu round,I know a fact that I'm a totally trash.Maybe I can never be an expert.
Very surprised by number of B and and C solves, B confused me while C seemed like a trivial sorting problem
Likewise
Worst B ever. Period.
I didn't solve B, but I liked it. It tests one's observation ($$$n^2-1$$$ upper bound) and simplification (solve it for 1d array first) skills.
That is because you didn't find a key idea of it,so your code was very long.If you found that $$$1 \sim n^2-1$$$ must be able to express,you could know that $$$n^2$$$ must be adjacent to $$$1$$$,easily we could expand it into an easy solution.
How to approach problems like B? I solved it by randomly guessing stuff.
Have you ever solved tasks from mathematical olympiads?
No. How would that be useful to tackle such problems?
These problems aren't random guessing, it's just math.
how exactly do you approach B mathematically?
This is the type of question like "how mathematicans prove theorems" or even "how tourist solve CP tasks".
just noticed your round is the next cf round, rofl. with this type of shitty opinions of yours, I pity whoever participates in that round.
True, He better not include these kind of problems. B pissed me off and I left contest within 20 minutes to play CSGO
The process "find the strictest lower/upper bound for the answer and then show that it's reachable" is common in math competitions (not only that, it also frequently appears in algorithm correctness proofs). This is the first step to the solution: it's quite easy to see that the answer is bounded by $$$n^2-1$$$ (all differences are positive, and the maximum difference cannot be greater than $$$n^2-1$$$).
Then, to actually find the way to reach this bound, you need to try some common techniques to solve problems. You can take a look at MikeMirzayanov's post on these techniques. From these, we have already used "Bold Hypothesis". The "From Specific to General" (with a twist, since we actually change the problem partially instead of just simplifying it) may help us as well: 2D sounds too complex, what if the problem is in 1D instead? This case sounds way stricter: we have only $$$n-1$$$ adjacent pairs, and all of them should be distinct. Believe it or not, but having stricter constraints actually makes the solution easier, inventing a construction on one-dimensional array is not that hard.
$$$[m, 1, m-1, 2, m-2, \dots]$$$, where $$$m$$$ is the maximum value
All that's left is to convert the 1D solution to 2D, which means that we should go through the matrix visiting all its cells, which is a common math/programming problem.
There are many ways to do this, one of the most well-known is to make a "snake" path: traverse the first row from left to right, go down, traverse the second row from right to left, go down, traverse the next row from left to right, and so on. Other solutions also exist, like making a "spiral" path.
Note that our process of solving the problem used something like "try to apply a concept and then see if it works" multiple times, and this is very common in both math problems and harder programming problems. So getting familiar with these concepts and methods will not only help you solve some constructive and/or ad-hoc problems, but also the more difficult ones, where you have to mix it with some standard data structures and algorithms.
Want to add something: some hard tasks require to try a dozen of different approaches before solving the task. This is common not only for constructive and maths, but for interactive problems, graphs or even data structures.
And solving those "just guess" tasks improve your thinking skills and allow you to recognize some patterns in future tasks.
So, dear contestants! Instead of just "problem was too bad", answer the question: was it hard or just difficult? Many people claim that the task is "bad" if they weren't able to solve it in time and got negative delta.
I had to tinker around with some randomly put together constructions till I came across the solution.
Proving it seemed easy once it was clear.
Definitely not appropriate for problem B, but it's an edu round and technically the order doesn't matter, so whatever, ig.
My opinion on the quality of Problem B has changed after reading this comment
Thanks
what's math in that?
Well it was not total math problem, but yes there was a quite neet observation, that is the maximum ans is always n^2 — 1, from there you can make the matrix multiple ways.
I got that observation but still it felt like massive hit and trial to me
But I think, here intended solution was random guessing!:(
After failing to submit E in the last 10 seconds the last time(Jan 6), this time I found the solution of E in the last 5 minutes and got AC just 5 minutes after the contest ended... [Sad]
B spoily my mood and I gave up after 20 minutes
Hi there! I try to help people by upsolving contest problems and post them after the contest on my channel — https://www.youtube.com/@grindcoding . I have been trying hard to help people by solving daily challenges across platforms and also the contest problems. Please provide me suggestions on what I can improve. Have uploaded problem C of this round already and would upload others as required by anyone of you. Any advice is appreciated :).
P.S. not the channel who promote leaking solutions during live contests. I know it provides better growth with the huge amount of cheaters, but I understand it's detrimental and against the overall spirit :) happy coding :) Soon would be making a good data structures and algorithms course to help beginners (though not a pro myself but want to contribute as I grow).
Here is the intuition I used to solve problem B:
The best possible result is we see $$$1, \ldots, n^2 - 1$$$ as the differences. What does this mean for the optimal answer? Can we always construct a matrix that achieves this result?
Lets try to achieve the optimal answer $$$n^2 - 1$$$ (differences) Consider the following sequence:
Notice that each subtraction to the right produces a new result:
Now can we convert the above construction into a matrix?
A tough contest to me :(((
problem B needs a lot of observation :((((
Any hints to approach problem 'C'?
Really reject stopping solving problems regularly T_T
I reached to the basic point where all i need is sort the array get the max sum <= m then nearlly this our final total wins.., then what?
Hint 1: Without considering your training, each other player has a unique amount of wins
Hint 2: What 1 other player's ranking can you affect that could also improve your ranking?
Hi! yes! there's one case you need to consider, can you defeat the person who has wins==wins_you_have+1, I have uploaded a editorial video on my channel you can check this here- https://www.youtube.com/@grindcoding
Let's say I want to reach a specific position Xth, what's needed? Once you've figured that,
binary search ^^
got stuck with b and no time left to think about c .. uff time to go back to green
Participate in post contest discussion
www.peer2peer.social
Wow, I really enjoyed the problemset! Problem F is just otherworldly *_*
Huge thanks to the developers of the contest! <3
Nowadays the problems in the contest are not properly sorted in the order of their difficulty. Sometimes the problem B is made very hard, whereas sometimes it is made as easy as A, and in this case the C problem is made very very Hard.
It would be nice if the difficulty order would be made moderately increasing.
problem C isn't hard. it's just sorting and a simple observation.
Welp this was a waste of time.
was anyone able to get the solution to E with $$$n√n$$$ time complexity?
O(n*log(n)) is enough. You just need to check for eack 1<=k<=n, if any multiple of k is in range [bi,ai-1] for some i which ai>bi.
it was hard but yes 188516731
It was a worst contest I have ever written. My problems never been hacked by some random pupil ranked participant.
Tips for Python
In Python, you can put negative indices in a list (A[-1] means A[len(A)-1]). This makes it easy to implement dynamic programming with negative indices. When the index can take values from -L to L, prepare a dp array of length at least 2*L+1. In this array, information on positive indices can be placed in the first half of the list, and negative indices in the second half ([0, 1, 2, 3, ..., L, ... , -L, ..., -3,-2,-1]).
Source Code for D:
Could someone tell me a test where my code fails?
https://codeforces.com/contest/1783/submission/188507888
188508171 Please show me a case where my submission for problem C get the wrong answer :((((
Can't understand vietnamese variable names...
Take a look at Ticket 16685 from CF Stress for a counter example.
The hack channel for problem C is ridiculous. If I set t to 1 and n to 500000, it will show generator crashed, which means it is hard to hack it tle！！！！！！！！！！！！！！！
Quite an ambiguous definition+example of the side adjacency for problem B. In the 2x2 example almost any nonsense one may come up with yelds same answer. For example if you define side adjacent elements as "elements on the same matrix edge". After the clarification it gets better, but still there's a chance you keep solving the wrong task on impulse.
Any ideas how this "insanely misinterpreted" problem can be solved by the way?
Once again. Same task: find the most beautiful matrix, but the adjacency definition is:
Two different matrix elements $$$a[i_1][j_1]$$$ and $$$a[i_2][j_2]$$$ are adjacent iff ($$$i_1 = i_2 = 1$$$ or $$$i_1 = i_2 = n$$$ or $$$j_1 = j_2 = 1$$$ or $$$j_1 = j_2 = n$$$) ?
1 n 2 (n-1) 3 (n-2) 4 (n-3)
Look at this like and all will be clear(first row of matrix)
Thanks, but that's the solution to the original problem, but doesn't seem like a solution to the problem I mention.
I'm interested in filling these so that the size of the set made of absolute difference of any two elements from first row or last row or last column or first column has max size.
can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row
can anyone tell me how to solve E?I Just know that for every a[i]>b[i],then check k is ok if and only if (a[i]+k-1)/k==(b[i]+k-1)/k (i.e. ceil(a[i]/k)==ceil(b[i]/k)). but this get TLE as expected. how to get a faster solution? i cant understand the solution in the front row
$$$\left \lceil{a[i]/k}\right \rceil \neq \left \lceil{b[i]/k}\right \rceil $$$ if and only if there exists a number divisible by $$$k$$$ in range $$$[b_{i}, a_{i}-1]$$$.
Therefore, we can mark all numbers in this range (for example, by using a segtree) and for each $$$k$$$, check if there is a marked number divisible by $$$k$$$.
Thanks
In problem C, does NlogN pass? I didn't want to take a risk and made an O(n+maxA) solution.
My n log n passed with 1500ms
can anyone help me understand in problem C if the test is 8 6 2 2 2 2 2 2 2 2 so if I win against the 8 and 6 and 4 so 1 1 win 2 2 win 3 3 win 4 3 win 5 5 win 6 5 win 7 7 win 8 7 win I 3 win so I should rank 3 why is the answer 5 I don't understand I got stuck in this problem for that
just because there are 4 people whose win count strictly larger than you (i.e.5,6,7,8),let the count called k. and the answer is k+1. I guess you misunderstood the computing method of the rank within this question.
Ty I think so the solution is much easier than i think ಥ‿ಥ
Brooooooooo, will re-read question 10 times now while solving.
Because rank is the no. of people with more wins than you + 1. Your win count is $$$3$$$ but $$$8$$$ and $$$7$$$ both have won $$$7$$$ and $$$6$$$ and $$$5$$$ both have won $$$4$$$, hence the no. of people with more wins than you is $$$4$$$. Therefore, your rank is $$$5$$$
Yeah i understand that they group people with the same win so that i should minimize the number of group
It's optimal to beat the any 2 players and the 4th player which results in 3 wins.
Bracketed players are the ones we beat.
And then if we count the number of wins and also consider the players we lose to we get our answer.
We ourselves have 3 wins. Order looks something like this then
Our rank is 5.
BledDest Can anyone explain problem C?
For this test case
4 4
1 2 2 1
Since we have 4 minutes I can defeat Opponent 1,2. But why in the explanation it is mentioned we can win against only opponent 1 and we have no time to prepare
That's the 5th test case.
If $$$m = 4$$$ and we prepare and win against opponents 2 and 3 and lose against 1 and 4. Don't we get 2nd place? As our opponent 4 has $$$3 + 1 = 4$$$ wins against our 2 wins. I must be missing something obvious.
Edit: ok my confusion was to fail to understand that "min place" actually means best ranking and not worst ranking.
We can pick the following opponents. (Bracketed means picked)
Which gives us 3 wins. Opponents will be ranked as follows:
This results in first place.
I almost spent the same amount of time on B as I did on C and D combined.
Seemed like I was solving some weird newspaper puzzle.
How is B an 'edu' problem?
I start to think that "edu" is not about learning, "edu" is about Harbour space, like , there are Pinely rounds, Polynomial Round, CodeTON Round etc.
It is rarely a difference between EDU and classic rounds. EDU were immature rounds initially, with no score distributions and possibilities for hacking, but later classic rounds overcome simplification and become similar to EDU, without hacking almost, but still with different costs of problems (except newer Div.>2, which are simplified further and have no difference with EDU).
It's not a random guessing problem. Notice that the difference is between 1 and $$$n^2-1$$$, so naturally we first try to get them all. For $$$n^2-1$$$, $$$n^2$$$ and 1 need to be adjacent, then for $$$n^2-2$$$, either $$$n^2$$$ and $$$2$$$ or $$$n^2-1$$$ and $$$1$$$ need to be adjacent, .... It's quite easy to achieve that. If you know gray code, Z-order, or something like those, easier.
Solution of D(with explaination please)?
you can refer to the tutorial videos on my channel -video editorial
This was a perfectly good round, without any major errors. Why all the downvotes?
Though the binary search solution greatly simplified the task, was it actually required in C?
I mean, apart from the edge case of losing to the winner and changing the required score, it was all greedy and sequential, right?
That's how I solved it. For loop
There is interesting solution of E with Eratosphens sieve: It's a fact that upper bound of a[i] / k must be <= upper bound of b[i] / k for all i. So we need to check only pairs where a[i] > b[i]. You can increase every a[i] position by any big number (1e7 + 1 in my case) and decrease every b[i] position by 1. Then we get prefix sum of this array and iterate like in sieve. If any sum on prefix with length which divides k doesn't divide 1e7, it means that we found some b[i] with b[i] / k > a[i] / k. That's it: 188522674
UPD: nevermind lol, it's basic solution
For problem D, I submitted these 2 solutions after the contest:
Submission 1 gives a Wrong Answer verdict. 188541769
But when I submitted a new solution taking the answer modulo, I got a TLE verdict. 188542103
I don't think I changed much of my code. Does anyone know what the heck is going on?
Modular operations are expensive. And even if they weren't, the first solution already took nearly 2s and adding more operations there inside the loop would yield TLE.
I see. Thanks!
If a,b are in [0,mod-1], you can use
instead of
Also you should check if(a[1]!=0) instead of if(a[2]!=0). Because of this mistake your answer will be hacked by some tests with a[2]==0, even if don't get TLE.
problems are good , but the implementation part is a bit complicated.
For D problem,can we use dfs and work it out?
Use DFS with memorization,in fact it is nearly the same with DP solution.
My good friend wrote it,though his code was not very easy to read.
188473734
188471652
As I said,you didn't use DFS with memorization.In other words,you could find that there will be many repeated search with the same $$$(i,ai)$$$.So you could record the answer of
dfs(i,ai).It will cut lots of unnecessary search.Your TLE code is a $$$O(2^n)$$$ solution.If you use memorization,it will be $$$O(n^3)$$$ because you will find $$$|ai|$$$ will not exceed $$$90000$$$.
hey, why are you returning 2 here?
if(i==n-1) { if(ai==0)return 1; else return 2; }
Because if i==n-2,there are two operations you can make:a[i+1]+a[i] or a[i+1]-a[i].But if,a[i]=0,then a[i+1]+0=a[i+1]-0,these two ways are the same way，we can just calculate 1
ohh, I see, thanks.
There's a line of code that needs to be modularized. I think my time complexity may be the same to your friend's,why mine cannot pass through?Can you help me slightly modify it and make it work?
I fixed your solution
188553247
I racked my brains last night, but I couldn't figure out how to cut the branches. It turns out that you can use space to exchange time and it increases my knowledge. Thank you very much!
So it is Mnemonic search? It turns out that I can really use some simple knowledge that I am good at to pass this topic! Because the code of my friends around me is complicated, I hope my code can be changed and pass. It really turned out to be okay.
Apparently I crashed codeforces because of a hack submission I made. I don't even remember the testcase I did, but it was supposed to bug a code that was using random generator for the answer. Anyway, thought I would leave that here so someone would look through it and see why it's still waiting for about 10 hours now!!
Here is the link to the hack: https://codeforces.com/contest/1783/hacks?verdictName=TESTING&chosenProblemIndex=A
I subitted my hack for someone's D problem last night,and it showed "generator crashed",which made me amazed,too.
No that's normal. That happens when the code you made to generate the testcase had some bugs in it.
Aha?It shows that: The hack uses generator Generator is not determinate [the verification run produces different output, cmd =cvp], [389171 bytes, '1
100000 5731847
175 801 492 274 740 3 22 624 98...850 521 474 390 847 127 534 896 874 535 704 834', sha1=0cc6f6ae5c8479c995b9dec28fcd7dc48de6b3fe] vs. [388952 bytes, '1
100000 5731847
181 530 685 865 602 856 479 769... 803 621 675 483 837 275 74 663 223 426 353 310', sha1=911ae7fb5a320770e460a2a3d1a2c49baa34c4c6]. My hack submission includes randmized integers,so I think it's naturally that the generator is not determinate. I've tried to submit code that generates random numbers before, but I've always succeeded before, but I don't know why I didn't succeed this time. I tried to write test to a file to make the value certain, but it said the file was too big and had too much text. So I think this is a bug in the cf mechanism.
Could you send me your generator?
You can search and see that the verdict of C problem in hacks is generator crashed
https://codeforces.com/contest/1783/hacks/879737/test
You uses the time as the seed,may be $$$m \le \sum{a_i}$$$ won't be satisfied.You could use a number as seed instead of time.
You shouldn't use system time to initialize the RNG, which causes value generated become indeterminate. Use fixed seed instead.
Aha?So does the fixed seed have some constraints?
Any number is ok.Such as I always uses 10086001,an interesting prime number :p
Could you check my hack too because it's preventing the update of the ratings
Sorry,this question is beyond my ability,may be you need to ask Mike for it XD
Will we see rating update and tutorial before next contest begins?
Why does "Educational round" mean slow rating update and slow tutorial?
No this is because there is a hack submission that is still waiting till now. It's mine, and I don't know what's taking it so long. I hope they fix it
lol
To think I would crash codeforces xD
I am wondering what you submitted that hacked the whole system XD
How to solve G ? Seems that the tutorial won't be soon :(
Wait for D's solution.DP is my weakness...
And there is still no tutorial yet?
Small hint to you:
In any time,$$$|a_i| \le s$$$,where $$$s$$$ is the sum of the given array.
When you are going to operate $$$i$$$,you only care the value of $$$a_i$$$ now.Try to empress the dp state as $$$f(i,now(a_i))$$$.
Thank you.I know how to solve it now. :)
I dont understand why this contest was downvoted, I felt like problems were good, specially C.
I'm wondering how 300*2*300*300 solutions were accepted for D. Thats like (10^8)/2. Aren't 10^8 solutions supposed to TLE?
It is very easy to pass in codeforces.In fact,many $$$10^9$$$ level codes could pass in 1 or 2 seconds in codeforces with their small constant.
Interesting, thanks. Wasn't really aware of it. It was a pretty straightforward dp question in that case. Will remember it for next time.
It's like the worst case scenario strategy, because none of the authors consider 10^9 solutions
176169324
Such as this code,it was a $$$O(n^3)$$$ solution and $$$n \le 1000$$$,but it was very fast,with a $$$\frac{1}{6}$$$ constant.
B is worst problem fck
Has anyone tried to submit B using simulated annealing? I tried but it gets WA: 188572639
Rating??
When is system testing going to happen?
Oh! It didn't happen all this time ? Hacking phase is finished
I was checking every while and I didn't see it happen
Oh! I thought my solutions passed the systests already... Sad. There might be a chance for Failed systests :-(
Yeah I'm growing impatient
Trush round!A is not perfect.Problem B is the worst problem I have ever seen.I wasted an hour on it.But C is very interesting.Hope more questions like C will appear in cf.
Why it's taking time to get the rating updated for this contest?
Because there is a hack submission still waiting lol
Where the rating updates at?
any tutorial?
When will the tutorial will be published ?
has this contest been declared unrated or what? why rating is not updated yet?
It takes so long in Educational Rounds
Yes, and 4 hacks are not tested yet. All that hacks are on this solution, it has random and easily gets TL. I dont know why testing solutions on hacks dont break after TL...
But in fact this code is expectly $$$O(Tn^2)$$$ in the worst cases,which is easy to pass.I didn't understand why it can be hacked(I submitted a same one and was hacked),could someone tell me?
I don't know about TLE, but does random give 100% correct answers?
If it was checked that the array was not correct,it will repeat the random algorithm till it find a correct answer.
If you have array [1, 1, 1, 1, ... , 2] you have 2 correct answers — [1, 2, 1, 1, ..., 1] or [2, 1, 1, 1, 1, ..., 1]. In this case you have n possible permutations of array, so in each random shuffle you have only 2 correct answers from n, where maximal n = 50.
if you do K random shuffles, probability of your win would be correct positions / all positions. All positions = n ^ k, correct positions = all positions — bad positions = n^k — (n-2) ^ k. So if you do K random shuffles probability of finding correct answer is
P = (n^k — (n-2)^k) / n^k.
For n = 50:
if k = 5, P = 0.1846273024
if k = 10, P = 0.33516736
if k = 100, P = 0.98312968
So on this testcase it does 100 shuffles for finding answer. So your code does t * n * K = 2000 * 50 * 100 = 1e8 operations, and you choosing random number 1e8 times for shuffling array, and this can take long time and maybe TL.
If you would find testcase where is only one correct permutation:
P = ((n^k) — (n-1)^ k) / (n^k)
if k = 5, P = 0.096079
if k = 10, P = 0.182927
if k = 50, P = 0.635830
if k = 100, P = 0.867380
if k = 200, P = 0.982412
In this case your code does t * n * K = 2000 * 50 * 200 = 2e8 operations
Yeah I thought just like you,but I tried to use $$$2000,50,1 1 1\cdots 2$$$ to hack it,but it ran very fast,just used 93ms!
link
And I just found the all the data hacked my submissions satisfied that $$$n$$$ is small(In fact,$$$n=4$$$). I'm a bit confused about it.
I just wrote a random algorithm as it.
188610805
I guess that
randomizein the hacked code is the murderer of it.Yes,
randomizefunction is bad and slow.When you tried to hack his solution it's not guaranteed that his random would use 100 operations — maybe if he would lucky he can find correct answer in 5 or 10 attempts.
About test that hacked your code, i dont really understand why it failed, because for n = 4 and k = 5, P = 0.96, so you need on the average 5 attempts for shuffle, so I dont know why it got TL...
I will try your solution in locale on testcase which hacked your solution, if I would find something interesting I will write you in messages.
It was me who hacked it. Sorry xD
I didn't care about it(And it wasn't my code in contest),I just wanted to know why it got TLE(And now I get it).And my submission above with
shuffleseems to be correct.The contest is supposed to be rated right?
Can anyone explain how to solve problem F?
We will post the official editorial in one or two hours. Here's an explanation of F copied from it.
The solution to this problem uses cyclic decomposition of permutations. A cyclic decomposition of a permutation is formulated as follows: you treat a permutation as a directed graph on $$$n$$$ vertices, where each vertex $$$i$$$ has an outgoing arc $$$i \rightarrow p_i$$$. This graph consists of several cycles, and the properties of this graph can be helpful when solving permutation-based problems.
First of all, how does the cyclic decomposition of a sorted permutation look? Every vertex belongs to its own cycle formed by a self-loop going from that vertex to itself. We will try to bring the cyclic decompositions of the given permutations to this form.
What does an operation with integer $$$i$$$ do to the cyclic decomposition of the permutation? If $$$i$$$ is in its own separate cycle, the operation does nothing ($$$p_i = i$$$, so we swap an element with itself).
Otherwise, let's suppose that $$$x$$$ is the element before $$$i$$$ in the same cycle ($$$p_x = i$$$), and $$$y$$$ is the element after $$$i$$$ in the same cycle ($$$p_i = y$$$). Note that this can be the same element. When we apply an operation on $$$i$$$, we swap $$$p_x$$$ with $$$p_i$$$, so after the operation, $$$p_i = i$$$, and $$$p_x = y$$$. So, $$$i$$$ leaves the cycle and forms its separate cycle, and $$$y$$$ becomes the next vertex in the cycle after $$$x$$$. So, using the operation, we exclude the vertex $$$i$$$ from the cycle.
Suppose we want to sort one permutation. Then each cycle having length $$$\ge 2$$$ must be broken down: for a cycle of length $$$c$$$, we need to exclude $$$c-1$$$ vertices from it to break it down. The vertex we don't touch can be any vertex from the cycle, and all other vertices from the cycle will be extracted using one operation directed at them. It's easy to see now that if we want to sort a permutation, we don't need to apply the same operation twice, and the order of operations does not matter.
Okay, then what about sorting two permutations in parallel? Let's change the problem a bit: instead of calculating the minimum number of operations, we will try to maximize the number of integers $$$i$$$ such that we don't perform operations with them. So, an integer $$$i$$$ can be left untouched if it is the only untouched vertex in its cycles in both permutations... Can you see where this is going?
Suppose we want to leave the vertex $$$i$$$ untouched. It means that in its cycles in both permutations, every other vertex has to be extracted with an operation. So, if two cycles from different permutations have a vertex in common, we can leave this vertex untouched, as long as there are no other vertices left untouched in both of these cycles. Let's build a bipartite graph, where each vertex in the left part represents a cycle in the first permutation, and each vertex in the right part represents a cycle in the second permutation. We will treat each integer $$$i$$$ as an edge between two respective vertices in the bipartite graph. If the edge corresponding to $$$i$$$ is "used" ($$$i$$$ is left untouched), we cannot "use" any edges incident to the same vertex in left or right part. So, maximizing the number of untouched numbers is actually the same as finding the maximum matching in this bipartite graph.
After you find the maximum matching, restoring the actual answer is easy. Remember that the edges saturated by the matching correspond to the integers we don't touch with our operations, the order of operations does not matter, and each integer has to be used in an operation only once. So, the actual answer is the set of all integers without those which correspond to the edges from the matching.
This solution runs in $$$O(n^2)$$$ even with a straightforward implementation of bipartite matching, since the bipartite graph has at most $$$O(n)$$$ vertices and $$$O(n)$$$ edges.
So when will system testing phase start?
I don't know. I don't understand what happened to those several hacks which can't be tested, and I am awaiting a response from Codeforces admins.
Hopefully this will be fixed soon.
Why am i not t rated?
Why do the ratings not still updated.Is any cheater caught or something else.Please update the ratings soon. Thankyou!!!
MikeMirzayanov Why am i not rated? Please update the ratings soon. Thankyou!!!
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Thanks for the Editorial :) Can anyone say why ratings are still not updated?
When will the system testing is going to start?
Sorry, this is my fault. I completely forgot about judging this round, I just somehow got distracted and flew out of my head. Is it old age? Soon the round will be re-judged taking into account hacks and then take care of the rating!
The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!
Thanks for first time I've been orange!
there is no change in my rating and i see a lot of people got their rating updated. please look into this.
MikeMirzayanov my rating is not updated till now and i see a lot of people getting their rating updated. please look into this.
It's strange those who solved 2 problems with 50 penalty are ranked #2835 in "common standing" but ranked #2834 in "rating changes". Maybe this difference is caused by someone was omitted in rating calculation…
30 minutes before the next contest. Hope for fast cheater removal
Now my rating is under 2100, if in the next div2 contest my rating is updated to 2100+, will I be rated in the next contest?
Did you participate? Was it rated for you? Just curious
I participated it. The rating has not been calculated yet.
Why rating update before next contest is important?
Some people are on boundaries of getting new color to profile...they becomes aware before their upcoming contests and prepare as per that situation....
Some might think to get good ranks in div3
Some might think that educational rounds are easy ...let's try for that and can skip some contest
Some might have got good rank and might be eager for announcements....
One of my friend won't eat food if contest not goes good....coding is turning someone emotion...❤️..
Wow that's fantastic to listen it and get ready for coding...!
We salute to efforts of all coding platforms...!! for making coding as emotion
Haha, your words are like long, complicated, but sincere prayers.
First time I “FSTed” with a later accepted time
is this round unrated?
Can anyone say why the given ratings are rolled out?
Why the Rating of this contest changes and suddenly changes back these days?
Why this contest is unrated?
or it's not unrated?
thanks!
I think that it's rated because my rating changes this morning.
My rating change at this morning, but now, it is rollback, anyone please explain for me?
mike has said: "The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!"
Yeah, thank you for for infor :)
Why my rating is not updated?
if someone is struggling with understanding problem-B, the key observation is there should be a number which can be completely absorbed into rest of the numbers. i.e. there is an a[i] whose set bits are [x1, x2, x3] and aj has set bits [x1, x3] and a[k] (k!=j && k!=i) has set bits [x2, x4, x5] then seq-a would be all elements in array and seq-b would be all elements in array except a[i] since those set bits already exist via rest of the elements