Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) Editorial

3 years ago, # ^ |

One can use this: https://mirror.codeforces.com/blog/entry/97795?#comment-866542

→ Reply

3 years ago, # ^ |

I'm also struggling to understand the logic of D. Liking a few articles that helped me understand even permutations and transpositions. Transpositions in a graph Even and Odd permutaions

→ Reply

OtabekJurabekov

3 years ago, # ^ |

I think its number of inversions.

→ Reply

Sorlag

3 years ago, # ^ |

A permutation is said to be even if it has been constructed by performing even number of swaps between any two elements. One way to check parity of a permutation (even or odd) constructed from a sorted array would be to compute the parity of number of inversions. Here is my solution to the problem submission. Array with duplicates can take up any permutation parity as the duplicates can be swapped amongst themselves.

→ Reply

cantdecide

3 years ago, # ^ |

just do it

→ Reply

Bliznetc

2 years ago, # ^ |

just did it

→ Reply

aryan.gupta

3 years ago, # |

+10

Tutorial for F got missed, I guess. Could you please update it?

→ Reply

Nea1

3 years ago, # ^ |

← Rev. 2 →

+41

Here you go https://atcoder.jp/contests/arc115/editorial/975

→ Reply

aryan.gupta

3 years ago, # ^ |

Oh demn. The exact same question! Thanks though!

→ Reply

3 years ago, # ^ |

+22

This problem can be solved in O(n * log(A)) using implicit segment tree 138937301, lets dp[i][j] = good array that ends in position i with a[i] = j, dp[i][j] = sum of all dp[i — 1][k], where k != j. dp[i][j] = sum(dp[i — 1]) — dp[i — 1][j]. So our dp changes linear, and sum changes linear so we can use seg tree

→ Reply

YPK

3 years ago, # ^ |

What does implicit segment tree do?

→ Reply

3 years ago, # ^ |

Its segment tree on range [1, A](A can be 1e9), works in O(log(A))

→ Reply

Sindy

3 years ago, # ^ |

Do you have any good resources for studying them ?

→ Reply

https://cp-algorithms.com/data_structures/segment_tree.html

3 years ago, # ^ |

→ Reply

sam571128

3 years ago, # ^ |

Using coordinate compression with normal segment trees will be faster than using a implicit segment tree.

→ Reply

3 years ago, # ^ |

Yes i know, but dont want to write compression, if my solution was TL, then i will rewrite it

→ Reply

arujbansal

3 years ago, # ^ |

How do you subtract $$$dp[i-1][j]$$$ in this approach?

→ Reply

3 years ago, # ^ |

My tree contain layer of dp(dp[i] and dp[i-1] the same tree) i want apply dp[i] = f(dp[i]) on range, where f(x) = kx + b, for i in [0, a[i]], b = sum(previous dp layer), k = -1, and for i in (a[i], 1e9], k = 0, b = 0

→ Reply

TimeTraveler

3 years ago, # ^ |

clever

→ Reply

CaesarPP

3 years ago, # ^ |

Hi, do you know of any educational material that explains exactly how you can apply a function (not necessary linear) to a segment tree? I've heard it is possible using multiple segment trees somehow.

→ Reply

3 years ago, # ^ |

With lazy propagation, and k1(kx + b) + b1 = (k1*k)x + (k1*b + b1), so we can apply one linear function to another

→ Reply

Code: https://mirror.codeforces.com/contest/1591/submission/138907414

3 years ago, # |

Really enjoyed solving problem C.

→ Reply

spookywooky

3 years ago, # |

+78

For E it is necessary to explain how to come up with an idea of the solution.

Just spitting out some implementation details is not an editorial. Who did not solve the problem does not understand that.

On the other hand, the goal of an editorial should be to explain the problem to participants not having solved it.

→ Reply

rohan.p

3 years ago, # |

+19

Another way of approaching problem D:

If all elements of the array are distinct, find how many swaps it is away from being sorted. If number of required swaps are even, the answer is YES, else, it is NO.

This can be done by making a copy of the array, sorting it, and comparing the initial array and the sorted array to find out total swaps.

→ Reply

3 years ago, # ^ |

Is there any proof of why this works or just intuition.

→ Reply

ambs_

3 years ago, # ^ |

+19

An even permutation is that which can be decomposed into even number of transpositions. A transposition means a two cycle or in simpler terms a swap between two terms.

eg. (1 2 4 3) is an odd permutation and can be written as (3 4) (it mean 3rd term maps to 4th term and vice versa, also rest terms map into themselves and hence are not written).

A sorted permutation is an even permutation (all the terms map into themselves and identity is even) and so the given permutation has to be even because then only it can be converted into sorted permutation using three cycles (or 2 transpositions as (1 2 3) can be written as (3 1) (1 2) read from right to left). Therefore even number of swaps imply that the given permutation is composed of even number of transpositions, therefore the permutation is even.

Note:-(1 2 3) means 1 maps to 2, 2 maps to 3 and 3 maps to 1. (3 1) (1 2) mean 1 maps to 2, 2 maps to 1 which maps to 3 and 3 maps to 1 and hence both (1 2 3) and (3 1) (1 2) are same. Think it as composition of functions!!

→ Reply

priyanshu.p

3 years ago, # ^ |

Yes, this article will give a help in case someone wants to calculate minimum swaps. Article

→ Reply

burak

3 years ago, # |

Do you guys recommend any article about problem D? Or can somebody come up with a simpler explanation without diving into too much technical language? I can't understand it with my current knowledge.

→ Reply

dhruv7888

3 years ago, # ^ |

+13

Observe that when you choose three indices , such that all 3 elements at these indices are distinct , the parity of their inversion count doesn't change ( Parity means even or odd no. ) . When two elements are equal , inversion count can decrease by 1. So leading yess for all cases with duplicate value.

→ Reply

3 years ago, # ^ |

Can u please give an example for the above explanation. I did not understand the statement "the parity of their inversion count doesn't change".

→ Reply

dhruv7888

3 years ago, # ^ |

Parity of the inversion count doesn't change means that , if the no. Of inversion in current permutation was x , and after applying the operation it is y , then x%2=y%2

→ Reply

Lihwy

3 years ago, # ^ |

← Rev. 2 →

How about permutation 3 2 1? Its parity of inversion count is 2 % 2 = 0. After apply operation, it becomes 1 3 2 and parity is 1 % 2 = 1.

→ Reply

pyetwi

3 years ago, # ^ |

The inversion count for 3 2 1 is 3, and the inversion count for 1 3 2 is 1.

→ Reply

Lihwy

3 years ago, # ^ |

oh my bad

→ Reply

devanshmishra111

3 years ago, # ^ |

how does a rotation doesn't change the parity of inversions?? Lets say we select 3 indices i, j, and k (i<j<k) and rotate them ...i...j...k... -> ...k...i...j then order of all the elements from i to k — 1 wrt k changes..same argument can be made for i and j

→ Reply

dhruv7888

3 years ago, # |

+19

Not to disrespect but I think giving only the Code for E would have been better than this quality of Editorial .

→ Reply

Ammar2001

3 years ago, # |

Am I the only one who had the idea of C right, but insisted on looping from origin? 138917782, I kept trying to handle this case instead of simply looping from the farthest point:

Test

After the contest, i saw the idea of solution in comments so i reversed the loop and it was so much easier 138926142, I learned a good lesson though :D

→ Reply

SergeyYakovlev

3 years ago, # |

I have a question about D. If we have n = 5, k = 4 and the sequence (1, 2, 3, 4, 5) best ans is 11 (we go to 2, 3, 4, 5 then go to 0 then go to 1), but when i follow gaven solution i get 13 (1, 2, 3, 4 then 0 then 5). Can anybody explain me, where i am wrong?

→ Reply

AshwinBanwari

3 years ago, # ^ |

I think you misunderstood the editorial. The best answer is 7. You would add the highest number of each group of 4 starting from the highest. So first, we would look at the 4 highest (5,4,3,2), add add the highest number from that group which is 5. THen we look at next 4 highest (only 1 left) which is just 1. So we get 6. We multiply it by 2 because we must also go back, which is 12. Then, we subtract the highest value (5) because we don't have to go back for the last time we leave 0. So the answer is 12-5=7. for that example with n=5,k=4.

→ Reply

BlueHeart0621

3 years ago, # |

← Rev. 2 →

Question about D. The tutorial says that problem D can be solved in some methods with O(n) complexity. So how to calculate the parity of a permutation in O(n) complexity. The BIT and CDQ are both in O(n log n) complexity. Or is there any other method to solve D without calculating the parity of a permutation.

→ Reply

Lihwy

3 years ago, # ^ |

you can use DSU

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Explained linear method here: https://mirror.codeforces.com/blog/entry/97795?#comment-866542

→ Reply

NM_Mehedy

3 years ago, # ^ |

Also, you can solve this using DFS.

Suppose we have a permutation

-> 2 3 1 5 4

-> 1 2 3 4 5 (index)

If you create a graph you'll find some cycles. Here we have 2 cycles.

2-> 1 -> 3 -> 2 and 5 -> 4 -> 5

Here the first cycle has length 3 and the second cycle has length 2.

We can always sort any cycles having odd lengths using the operation described in the problem. So the number of cycles having odd lengths doesn't matter. On the other hand, If the number of cycles having even length is even then we can sort them otherwise we can't.

So if we have an even number of even length cycles then the answer is yes otherwise no.

You can find the length of a cycle using dfs.

Code

→ Reply

SouLPegasiuuuS

3 years ago, # ^ |

How did you come up with this approach? Is this a well known concept? Where can I learn more about this?

→ Reply

NM_Mehedy

3 years ago, # ^ |

← Rev. 2 →

Basically, here I'm checking whether a permutation is even or not?

Firstly, you need to know about The Number of Transpositions in a Permutation and Even and Odd Permutations and their theorems.

In the second link, you'll find a theorem.

Theorem

From the first link, you'll know that number of transpositions from a cycle = length of the cycle – 1.

So if a cycle's length is odd means the number of transpositions from it is even. Similarly, if a cycle's length is even means the number of transpositions from it is odd.

Now, in order to be an even permutation, a permutation must have the odd number transpositions cycle even number of times. (as mentioned in the theorem)

So, a permutation is even if it has odd number transpositions cycle even number of times means the even length cycles must be present even number of times.

(I hope I didn't make it complicated.)

I don't think it's a very well-known concept. I learned it yesterday. A large number of participants solved it using inversion count.

→ Reply

SouLPegasiuuuS

3 years ago, # ^ |

Thanks a lot.

→ Reply

Ekke

3 years ago, # |

For problem D, I can't figure out why these groups generate all the even permutations of A. How could it lead to all? Stunned.

→ Reply

https://mirror.codeforces.com/contest/1591/submission/138958298

3 years ago, # ^ |

← Rev. 4 →

Even permutaion can be represented as composition of even number of transposotion. We will divide this representation on pairs and change their by on this rules:

($$$i$$$ $$$j$$$)($$$i$$$ $$$j$$$) = "can be removed at all"

($$$i$$$ $$$j$$$)($$$i$$$ $$$k$$$) = ($$$i$$$ $$$k$$$ $$$j$$$)

($$$i$$$ $$$j$$$)($$$k$$$ $$$t$$$) = ($$$i$$$ $$$j$$$ $$$k$$$)($$$j$$$ $$$k$$$ $$$t$$$)

This way we got a representation of each even permutation as composition of $$$3$$$-cycles.

→ Reply

Ekke

3 years ago, # ^ |

← Rev. 2 →

Got it. So I can always use 3-cycle to decrease the number of reverse pairs by 2! thank u :)

→ Reply

4He3Liu1Shan.5Hu

3 years ago, # |

← Rev. 2 →

I have another solution for problem D.

First, consider the "reverse pairs" which means a pair $$$(a_i, a_j)$$$ where $$$1 \leq i < j \leq n$$$ and $$$a_i > a_j$$$. For any sorted arrays, the number of reverse pairs is zero.

It's easy to find that if the n elements in the array are distinct, then in each operation we can cancel 2 pairs. So we can calculate the number of reverse pairs. If the number is even then the answer is Yes; on the contrary, the answer is No.

But if some elements in the array are the same, we can move the same elements so in an operation. So in this case, for each operation, we can cancel 1 or 2 pairs. So the answer will be always Yes.

To calculate the number of reverse pairs, we can use the merge sort algorithm in $$$\mathcal{O}(n \log n)$$$ complexity.

Code here. https://mirror.codeforces.com/contest/1591/submission/138947313

→ Reply

nishu2002

3 years ago, # ^ |

Great solution bro. Btw I found the reverse pairs using ordered set

→ Reply

CTRLPLUSC

3 years ago, # |

could someone please give the solution to problem c for the above approach

→ Reply

Sobzi

3 years ago, # ^ |

my solution

hope it's useful :)

→ Reply

Sobzi

3 years ago, # ^ |

btw mx is the last depot we go so we don't need to turn back to origin 0. so we should maximize mx to have the minimum anwer.

→ Reply

exhausted

3 years ago, # |

← Rev. 2 →

It was necessary to try to make all three qualifying rounds of the technocup as terrible as this one

→ Reply

Fanarill

3 years ago, # |

← Rev. 2 →

Damn I thought C was about dp, but the next day I realised it could be solved greedily. I thought about test cases like $$$[1,2,3, 1000, 1001]$$$ and $$$k = 2$$$ and basically whenever I stayed there's only two options: return back to $$$0$$$ coordinate to retrieve resources or continue to supply the depots. Nevertheless, I was wrong and these two options could be proccessed without any recursion. I guess, I will try to solve this problem after the contest.

→ Reply

tanuki_10

3 years ago, # |

What if in Problem D the question had 4(or x) cycles instead of 3. Would it have similar logic?

→ Reply

_Enginor_

3 years ago, # |

+11

I my self struggled to understand the logic behind problem D but after some thinking i tried to prove the logic of this code.

So i am sharing my some notes which might me helpful to understand the solution.

PROBLEM D EXPLAINATION

→ Reply

ElyesChaabouni

3 years ago, # ^ |

Thanks a lot! This was very useful!!

→ Reply

SouLPegasiuuuS

3 years ago, # ^ |

Bro, this is really helpful. orz

→ Reply

Serikbay777

3 years ago, # |

+10

где разбор задачи f?

→ Reply

FattyLovesMangoes

3 years ago, # |

← Rev. 2 →

Why my solution for problem E is giving MLE?

Edit: NVM, it's because of the deque. C++ Deque is taking a huge amount of space, don't know why.

→ Reply

shadow9236

3 years ago, # |

https://mirror.codeforces.com/contest/1591/submission/138922744

Same submission after removing #pragma passes.

Is there a guide on when to not use pragmas and when to use them ?

→ Reply

endless_summer

3 years ago, # |

can someone link something (like a complete guide or something) to understand problem D. Some comments said this is a well-known problem/theorem?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+11

You can look for definitions here.

That's why $$$3$$$-cycles generates group of even permutations: link

That's how to find parity of permutation in O(n): link

→ Reply

Sindy

3 years ago, # |

anyone solved poachers ?

→ Reply

3 years ago, # |

Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).

→ Reply

M_bolshakov

3 years ago, # |

-9

Great set of problems, very glad that I've participated in this round. I find solution in D pretty cool, at least it's better what I've submitted:)

→ Reply

Samsara_soul

3 years ago, # |

+104

Attention!

Your problem 1591F. Non-equal Neighbours significantly coincides with problem arc115e — LEQ and NEQ. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your problem). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.ml/blog/entry/8790. Such violation of the rules may be the reason for downvoting your article or other penalties. In case of repeated violations, your contribution may be low.

→ Reply

NadmanKhan

3 years ago, # |

Could someone provide a more noob-friendly editorial for D? Thank you.

→ Reply

Guptaansh

3 years ago, # |

Can somebody please explain the solution for problem D. As in what is the method and why should it work for every possible case?

→ Reply

1591E - Frequency Queries

3 years ago, # |

Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).

→ Reply

toniskrijelj

3 years ago, # |

O(n+q) 139128594

O((n+q)log(n)) 139132580

Second solution actually got smaller run time xD

→ Reply

Blue_Moon_07

3 years ago, # ^ |

would you explain both the solution because I am not able to understand the editorial.

→ Reply

toniskrijelj

3 years ago, # ^ |

Consider sorted array of frequencies :

frequencies:               0 0 0 0 1 1 1
number that has frequency: 1 5 2 4 3 7 6

(this is example)

Now to increase frequency of x= 5 you want to do following:

***

0 0 0 0 1 1 1

1 4 2 5 3 7 6

(you swap 5 with last number that has frequency same as 5 (in this case 0), this is also position before the first position of some number with frequency of x+1 (in this case 1)) And then:

0 0 0 1 1 1 1

1 2 4 5 3 7 6

You increase the frequency of 5 and now array stays sorted while you used only 2 swaps.

This is main idea, now to make it work you need:

lb[i] — same as in editorial, you can use this to find position before first position in array that has frequency >= than some i

p[i] — actual array that we are storing (in first example the array 1 5 2 4 3 7 6), you need this in order to answer queries in O(1) as you can just find required value at some index in array, also you need this to know which element is at some position so we can swap it

p^-1[i] or i call it pos[i] — this stores where is i located in above array (p) (it's position)

example: if array p = 4 2 1 3, pos[4] = 1, pos[3] = 4, pos[2] = 2, pos[1] = 3

you need this because you should find where is X located in array so you know which positions you should swap when doing step "***"

So with these values you can answer queries fast, and also recalculation of these values are pretty easy and fast (O(1))

The logN solution is same as this, only without the lb[i] array because I wasn't sure if I would come up with that idea, so I used different method that I am more familiar with:

Keep track of first[x], last[x] (first and last position so that position has frequency x), set ok which stores which frequencies we actually have, this is used when answering queries to find first position with frequency >= L

→ Reply

Blue_Moon_07

3 years ago, # ^ |

Thanks for good editorial.

→ Reply

thanhdno

15 months ago, # ^ |

← Rev. 2 →

→ Reply

3 years ago, # |

Can someone please explain the n^2 idea for 1585F in more simpler terms? I couldn't understand what will be the answer after computing dp[N][0] and dp[N][1].

→ Reply

cqtshadow

3 years ago, # ^ |

← Rev. 2 →

+) |A|, |B|, |C| here alternate mean the number of ways to build array such that a[1] = a[2], a[2] = a[3], a[3] = a[4].

+) S mean the total of ways to build the array ( I don't now call it in set stuff lol )

I believe this picture will help you if you already know basic inclusive-exclusive.

Notice that it will be opposite when n is odd.

Update: Sorry for who saw the picture before this edit, I was misspeltt intersection and union signs

→ Reply

toniskrijelj

3 years ago, # ^ |

And how do we get S ?

→ Reply

cqtshadow

3 years ago, # ^ |

← Rev. 2 →

It's already count in dp[n][0] if n is even, or in dp[n][1] if n is odd.

S is one of the ways to separate the array to have odd (or even depend on n) equal segments.

→ Reply

3 years ago, # ^ |

Thanks for explaining with a diagram. dp[i][0]+=dp[j−1][1]⋅f(j,i)

dp[i][0] means ending at i with even number of segments right? and we are calculating it as selecting some j and saying j->i forms one segment and till j-1 form odd number of segments.

But how are we making sure whatever number we are putting in j-> i is not in the last segment formed till j-1?

We are saying till j-1 we need odd segments but the last segment can contain any number which may collide with our choice of j->i making count as odd for dp[i][0]?

or am I missing something here?

→ Reply

cqtshadow

3 years ago, # ^ |

← Rev. 3 →

No bro, between segments didn't have to be different, we just separated the array into segments, that it.

A is the number of ways such that a[1] = [a2], but it doesn't mean that A will not contain values such that satisfied B or C, that's why we have to use Inclusive-Exclusive bro.

→ Reply

3 years ago, # ^ |

Thanks a lot bro! Finally able to understand it

→ Reply

P___

3 years ago, # ^ |

Thanks, that's a great explanation!

→ Reply

3 years ago, # ^ |

With the help from cqtshadow, Finally I understood the application of inclusion-exclusion principle here. Adding few more details here to help someone new to inclusion-exclusion principle.

Let the given numbers be A1, A2, ..... An.

We can calculate the answer as Total ways(T) - invalid ways(I) where T = A1 * A2...*An and I = number of sequences with atleast one index i with Ai == Ai+1

Inclusion Exclusion comes into picture to calculate I.

Denote Ei is event where Ai=Ai+1 i.e there are n-1 events and I = E1 U E2 .... U En-1

$$$ I = \cup_{i=1}^{n-1}E_{i} = \sum_{i=1}^{n-1}E_i - \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}E_i \cap E_{j} + \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}E_i \cap E_{j} \cap E_{k} ....$$$

$$$ ans = A1*A2*..*An - \sum_{i=1}^{n-1}E_i + \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}E_i \cap E_{j} - \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}E_i \cap E_{j} \cap E_{k} ....$$$

Here notice the lengths of all positive terms and negative terms. If n is odd, all positive terms are odd length and negative terms are even length(viceversa if n is even). Hence we can group them and get 2d dp.

Wrote a n^2 solution (although TLE) to check my understanding https://mirror.codeforces.com/contest/1585/submission/139689924

(Do check the figures from cqtshadow to come up with the base cases)

→ Reply

3 years ago, # ^ |

Added next greater element stack optimization to convert to O(n) https://mirror.codeforces.com/contest/1591/submission/139715435

→ Reply

Olympia

3 years ago, # |

← Rev. 2 →

I was not clever enough to realize the even cycles argument. There's an easier way, though (or at least, I think it's easier).

The first idea is the same as the editorial's: if we ever have a repeat element (i.e. an element which appears >= 2 times in the array), then we can always sort it.

Now, some elements are out of place. For example, if we take the array [2, 3, 1, 4, 6, 5, 7], then five elements are out of place (those out of place are bolded). We can ignore elements that are in their proper places, since they won't affect the answer. At least, it would make sense if we start by cyclically shifting the elements that aren't out of place.

With this in mind, we know that we want the first element to be 1. Since the first element is actually 2 in the aforementioned example, we should cyclically shift the 1,2, and any other arbitrary element (it doesn't matter which one). This will put 1 in its proper position. Since 1 is in its proper position, we can ignore it from here on out. Depending on the arbitrary third element of our choice, our new array could be [1, 3, 7, 4, 6, 5, 2]. So now, the 2nd element is out of place, so we should swap the 2, the 3, and some arbitrary third element. And so forth (I think you get the idea).

The solution is surprisingly straightforward to implement if you keep track of the index of occurrence of all elements in the vector.

Code is here: 139441826

→ Reply

MatheusOP

2 years ago, # ^ |

Thank you so much for the explanation!

I was trying to solve the problem using a really similar logic (ie. trying to sort the array in a "greedy" way, fixing the first position, then the second, then the third... until the (n-2)th position. But I was missing the "if we ever have a repeat element then we can always sort it." part. Reading your comment made me realise that.

Following this same logic, I'm still trying to figure out the reason we can always sort the sequence if there are any duplicates. One of the reasons I could think of was that by the end of the operations we end up with the last elements being something like "x y x" in which x < y. So in this case, even if the first x is in its correct position, we still need to apply a shift, to get "x x y". That being said, this reason is not sufficient, as can be seen in this commit (see line 91).

→ Reply

koderkushy

3 years ago, # |

sorry for necro-commenting but there is a problem G in Technocup 2022 — Elimination Round 3. there seems to be no editorial nor any mention of it among the comments.. would the editorial for it be added?

→ Reply

3 years ago, # ^ |

← Rev. 4 →

Sorry, I forgot to translate editorial as there wasn't any rush to post english editorial for this problem.

I will do it right now.

UPD: Done.

→ Reply