Hello Codeforces!

On Jan/08/2023 17:35 (Moscow time) Educational Codeforces Round 141 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hey, Codeforces!*

*We are pleased to announce the second “Hello Muscat 2023” ICPC programming bootcamp, the continuation of the “Hello” bootcamp series, organised by Harbour.Space University, in collaboration with PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club and Codeforces!*

*Quite exciting, isn’t it? Now it's time for you to dive deeper into the competitive programming world with the 8 days intensive Hello Muscat 2023. It will take place in Muscat, Oman and online from March 8th to March 16th, 2023, both participation formats are available. As always, we can’t wait to see you there to learn, practice and compete on the international stage, smoothing your road towards the joined World Finals 2022 and 2023 in Egypt!*

*Our coaching line-up combines talent and experience, featuring ICPC world champions winners and finalists, as well as legendary names from the field of competitive programming: Mike Mirzayanov MikeMirzayanov, Yahor Dubovik 244mhq, Artem Plotkin Rox, Maksym Oboznyi MaksymOboznyi and Nikolay Budin budalnik.*

**The Bootcamp will be split into three divisions:**

**Division A.**Division A will be a mirror of the Petrozavodsk Programming Camp. Suitable for teams who already qualified for the world finals ICPC or are aiming that high.**Division B.**Designed to help teams prepare for the next season of ICPC regional competitions. Appropriate as an introduction for teams and students just getting their foot in the door of the world of ICPC and competitive programming competitions in general.**Division C.**Designed for newcomers to the world of ICPC competitive programming.

**Types of participation: On-Site and Online**

*We believe that participation in our Bootcamp should be accessible by all teams wherever they are and that is why we made onsite and online types of participation.* **20% Early Bird Discount** *is offered to universities and participants who register and pay before Jan 31st 2023.*

**On-site:**

*Price: *

*What is included: training, contests, access to the recordings of the lectures, accommodation for 9 nights in a 4 star hotel Mysk, breakfast and lunch, transfer from hotel to venue every day, leisure, entertainment and welcome pack.*

**Online:**

*Price: *

*What is included: training, contests, access to the recordings of the lectures.*

*Good luck with the round!*

UPD: Editorial is out

Best of luck everyone . As a participant I am going to give my best in this contest.

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.

Only two words: More Practice

Only one word: repeat

Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

Thanks for the words i guess. Planning to reach 1700 by the end of the year is it realistic if I work hard?

Idk but one thing I would say Enjoy the process!

This is a good goal. I would also like to go up to 1600 a year. And I understand that this is real if you regularly work and solve problems not only that are easy for you, but also that are higher than your current level, in order to learn how to solve them.

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 am sure everyone will be successful in this competition. You can! Good luck!

I also wish everyone that no one could hack their solution! I wish everyone +100 or more than 100 to the rating of everyone!

Mathematically its not possible because if you want to get + rating changes some one has to get the negative.

BiG BrAiN

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..

oh thanks

😮

good luck have fun

Hope to become cyan, and good luck to everyone in this contest.

hmm, why I has the conbutrition? can anyone explain??

You might have gotten an upvote.

This Contest is very beauty-full

me after solving a&b :

true :) couldn't even understand what's happing with c :/

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.

If I have understood it correctly, the proof is:

Let's solve this problem for a 1D case, then we will extend it to 2D. Say, n = 3. So, the values are: 1, 2, 3, 4, 5, 6, 7, 8, 9 (from 1 to n*n) Here, the minimum value is 1 and the maximum value is 9, so, no matter what, the absolute difference will be at most 8 (when |9-1|) and the minimum absolute difference will be 1 (when |9-8|), and the other values will be in between. Our target is to maximize the total various types of such absolute differences. If we order the numbers in the following way: 9, 1, 8, 2, 7, 3, 6, 4, 5 then the target can be maximized. As in this case we are getting these all kinds of absolute differences we could ever get from them taking side-adjacent values. That are: 8 (i.e, |9-1|), 7 (i.e, |8-1|), 6 (i.e, |8-2|), ..., 1 (i.e, |5-4|)

Two numbers in an array are side-adjacent when they are positioned one after another either in the same row or in the same column. For example, for a 5x5 matrix, the indices are as follows:

So, the side adjacent to position (3, 3) are (3, 2), (3, 4), (2, 3), and (4, 3) positions. We have to find all possible side-adjacent positions for each position and take absolute differences of corresponding values and count how many unique absolute difference values we get. And obviously, we have to find an arrangement in such a way, that the number of possible such values maximizes.

Going back to 3x3 cases (for better manageability), a deterministic solution is to arrange the 1D array (which maximizes the result in 1D case, i.e: 9, 1, 8, 2, 7, 3, 6, 4, 5), in a zig-zag fashion. So, the solution is:

which follows the following pattern:

This will work because the zig-zag pattern is nothing but the same 1D array (just in an entangled fashion). But the values which were side-adjacent in 1D cases are still side adjacent in 2D cases (if we just follow this path). Obviously, as it is now in 2D, there will be more side-adjacent pairs that are not shown in the path (each position can have at most 4 side-adjacent positions, namely: left, right, up and down position), but we simply don't care for them, as we already have maximized the result and the other side-adjacent values will just create duplicate absolute difference values which we already found while traversing the path.

Solution: https://codeforces.com/contest/1783/submission/190766740

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.

its not stupid instead you can find the logic behind the pattern. though i wasn't able to solve the problem i found its quite intuitive after contest... since there will be in total 2*(n*(n-1)) adjacency relationship and also maximum diff between any two adjacent could be n*n-1 < 2*(n*(n-1)), we can always generate pattern such that from 1 to n*n-1 all diff got generated. now take the maximum diff i.e., n*n-1 we cannot make it a adjacent diff between two big values so adjacent relationship can be between big and small values, like n*n and 1, 1 and n*n-1 like that. If we solve that for 1D array of length n^2 we have total n^2-1 adjacency relation so just making a spiral out of it to make the n^2 length array to a n x n matrix would suffice.

Yes i did it using Spiral Traversal :)

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

Unable to parse markup [type=CF_MATHJAX]

distinct value so we started fromUnable to parse markup [type=CF_MATHJAX]

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:

ufff my bad . thanks for the help.

Even i tried a similar approach. 1. Try defeating players from last. 2. Sort and try to defeat as many as possible. Then print the minimum of the two ranks. But it failed on TC 2.

I was also thinking the same but this will not work because we are concerned more about the total number of wins by "me".

even if we win against last person but our time left is 0, our total win is only 1 so players before last one (like p=2 or 3) can win and our rank will fall.

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

SpoilerD 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)

You need some testers for educational round too lol. There are so many ups (and lots of downs) in the quality of these contests

how to solve c?

SpoilerThe $$$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$$$.

i tried binary search But not Know how to write function correctly Plzz share some hint

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

Thanks I overcomplicated it too much

how did you come up with the pattern?

As always Educational rounds are worst.

The whole point of them is to learn (standard) algorithms,

notto 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'tnecessarily make it bad.Infact the reverse is the case, it is very easy to guess the pattern for problems like this without knowing the proof.

I'm pretty sure for this problem, people just randomly guessed patterns that gave $$$n^2 - 1$$$ as difference, and only a few actually proved the patterns or derived it mathematically.

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

same

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)

Yup now got AC by iterative Code : Iterative Solution

Thank you Saul-Goodman

Can we solve C using Binary search?

I too want to know this, I got an intuition but couldn't mold it in any kind of solution.

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.

Ohh I understand it now. Thank you very much!

Worst contest for me!

B is easy than usual

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.

Spoiler$$$[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.

SpoilerThere 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!:(

Thats how you solve it, xD

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).

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

SpoilerI 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,

bold hintbinary 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

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:

188508171 Please show me a case where my submission for problem C get the wrong answer :((((

Can't understand vietnamese variable names...

Okay :(((

Thank you a lot :(((( I just sort the array and an extra check to get the best solution for the k-th opponent :((( Sorry Because my code is just like a mess :((

Take a look at Ticket 16685 from

CF Stressfor a counter example.Oh thanks alot :(

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

adjacentiff ($$$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

$$$\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.

Oh my bad

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, '1100000 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

Ok thanks

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

It's really nothing xD Just a long testcase to hack a solution that uses random generator. That's all 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

This Bootcamp, is it meant only for students? Or can I join at the ripe age of 33?

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

Oh..then, I am growing impatient these days

Where the rating updates at?

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

`randomize`

in the hacked code is the murderer of it.Yes,

`randomize`

function 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

`shuffle`

seems to be correct.Yeah some types of shuffle will work. I saw someone use random_shuffle and when I looked at it in the documentry it looked like a very good way of shuffling, and a fast way too. It just two successive elements, which is really all what you might need for the answer

The contest is supposed to be rated right?

IMO Editorial should be provided shortly after the hacking phase finished.It's too long.

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.

SpoilerThe 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.

ratings not been updated MikeMirzayanov

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?

why rating is still not updated?

Ratings have not been released yet!!!

Still no change in ratings :(

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…

No only some are eliminated before 3000 rank...I mean to say...their rank of contest is pretty good before hack period and copy cat searching dudes..

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.

help me. I am not able to figure out test case in which my code will fail. Your text to link here...

Check out this testcase

First time I “FSTed” with a later accepted time

is this round unrated?

Can anyone say why the given ratings are rolled out?