Задачи придумали и подготовили:
A: KAN, dimatimoshin23, kirill.grachoff, antonis.white
C: napstablook
F: Denisson
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Автокомментарий: текст был обновлен пользователем antonis.white (предыдущая версия, новая версия, сравнить).
https://codeforces.net/blog/entry/97840
Problem E can be solved head-on with a treap or pb_ds
Appeal to antonis.white: Congratulations, you were able to come up with a problem for your super data structure!
Questions about problem D:
1. What is an even permutation?
2. How to check whether a permutation is even?
https://en.wikipedia.org/wiki/Parity_of_a_permutation
As for me, I use
sign of a permutation. It equals to $$$(-1)^{x}$$$, where $$$x$$$ is a number of pairs $$$a_i, a_j$$$, where $$$i < j$$$ and $$$a_i > a_j$$$.One can use this: https://codeforces.net/blog/entry/97795?#comment-866542
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
I think its number of inversions.
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.
just do it
just did it
Tutorial for F got missed, I guess. Could you please update it?
Here you go https://atcoder.jp/contests/arc115/editorial/975
Oh demn. The exact same question! Thanks though!
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
What does implicit segment tree do?
Its segment tree on range [1, A](A can be 1e9), works in O(log(A))
Do you have any good resources for studying them ?
https://cp-algorithms.com/data_structures/segment_tree.html
Using coordinate compression with normal segment trees will be faster than using a implicit segment tree.
Yes i know, but dont want to write compression, if my solution was TL, then i will rewrite it
How do you subtract $$$dp[i-1][j]$$$ in this approach?
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
clever
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.
With lazy propagation, and k1(kx + b) + b1 = (k1*k)x + (k1*b + b1), so we can apply one linear function to another
Really enjoyed solving problem C.
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.
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.
Code: https://codeforces.net/contest/1591/submission/138907414
Is there any proof of why this works or just intuition.
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!!
Yes, this article will give a help in case someone wants to calculate minimum swaps. Article
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.
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.
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".
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
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.
The inversion count for 3 2 1 is 3, and the inversion count for 1 3 2 is 1.
oh my bad
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
Not to disrespect but I think giving only the Code for E would have been better than this quality of Editorial .
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:
1
5 3
2 2 3 3 3
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
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?
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.
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.
you can use DSU
Explained linear method here: https://codeforces.net/blog/entry/97795?#comment-866542
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
How did you come up with this approach? Is this a well known concept? Where can I learn more about this?
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.
If P1 and P2 are permutations, then
(a) P1P2 is even provided P1 and P2 are either both even or both odd.
(b) P1P2 is odd provided one of P1 and P2 is odd and the other even.
(like if we have a and b then a+b is even if both are even or both are odd and a+b is odd if either a or b is odd, this is also true for a permutation)
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.
Thanks a lot.
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.
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.
Got it. So I can always use 3-cycle to decrease the number of reverse pairs by 2! thank u :)
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://codeforces.net/contest/1591/submission/138947313
Great solution bro. Btw I found the reverse pairs using ordered set
could someone please give the solution to problem c for the above approach
my solution
hope it's useful :)
btw
mxis the last depot we go so we don't need to turn back to origin 0. so we should maximizemxto have the minimum anwer.It was necessary to try to make all three qualifying rounds of the technocup as terrible as this one
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.
What if in Problem D the question had 4(or x) cycles instead of 3. Would it have similar logic?
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.
Thanks a lot! This was very useful!!
Bro, this is really helpful. orz
где разбор задачи f?
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.
https://codeforces.net/contest/1591/submission/138958298
https://codeforces.net/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 ?
can someone link something (like a complete guide or something) to understand problem D. Some comments said this is a well-known problem/theorem?
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
anyone solved poachers ?
Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).
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:)
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.
Could someone provide a more noob-friendly editorial for D? Thank you.
Can somebody please explain the solution for problem D. As in what is the method and why should it work for every possible case?
Автокомментарий: текст был обновлен пользователем antonis.white (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).
1591E - Frequency Queries
O(n+q) 139128594
O((n+q)log(n)) 139132580
Second solution actually got smaller run time xD
would you explain both the solution because I am not able to understand the editorial.
Consider sorted array of frequencies :
(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
Thanks for good editorial.
.
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].
+)
|A|,|B|,|C|here alternate mean the number of ways to build array such thata[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
And how do we get S ?
It's already count in
dp[n][0]ifnis even, or indp[n][1]ifnis odd.Sis one of the ways to separate the array to have odd (or even depend onn) equal segments.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?
No bro, between segments didn't have to be different, we just separated the array into segments, that it.
Ais the number of ways such thata[1] = [a2], but it doesn't mean thatAwill not contain values such that satisfiedBorC, that's why we have to use Inclusive-Exclusive bro.Thanks a lot bro! Finally able to understand it
Thanks, that's a great explanation!
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)whereT = A1 * A2...*Anand I = number of sequences with atleast one index i withAi==Ai+1Inclusion Exclusion comes into picture to calculate I.
Denote Ei is event where
Ai=Ai+1i.e there are n-1 events andI = 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://codeforces.net/contest/1585/submission/139689924
(Do check the figures from cqtshadow to come up with the base cases)
Added next greater element stack optimization to convert to O(n) https://codeforces.net/contest/1591/submission/139715435
Объясните более подробно задачу F, пожалуйста.
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
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).
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?
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.
Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).
I only know the solution of F using segment tree and it's very complex