Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3823 |

3 | Benq | 3738 |

4 | Radewoosh | 3633 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3529 |

7 | ecnerwala | 3446 |

8 | Um_nik | 3396 |

9 | ksun48 | 3390 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | cry | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 160 |

5 | -is-this-fft- | 158 |

6 | awoo | 157 |

7 | adamant | 156 |

8 | TheScrasse | 154 |

8 | nor | 154 |

10 | djm03178 | 153 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of VK Cup 2019-2020 - Final Round (Engine)

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/12/2024 20:19:20 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Edit: Nvm, it's showing up now

How does the interactor work for F?

You can find Smith values for all vertices in $$$O(E \sqrt{E})$$$, and then all the arithmetic should be simple enough.

Could you elaborate? (What's a smith value?)

The only source I know about Smith theory is Winning Ways For Your Mathematical Plays, chapter 12. In short, every position in such a game is equivalent to a nim heap $$$*k$$$, or $$$\infty_S$$$ for a set of non-negative numbers $$$S$$$. $$$\infty_S$$$ is winning if $$$0 \in S$$$, and a draw otherwise. Smith value of a position is one of these options.

The addition rules are: $$$*a + *b = *(a \oplus b)$$$ (just Grundy), $$$\infty_S + *k = \infty_{S \oplus k}$$$ (XOR every element of $$$S$$$ with $$$k$$$), $$$\infty_S + \infty_{S'} = \infty_{\varnothing}$$$.

This paper has a short summary in section 6: https://www.msri.org/people/staff/levy/files/Book56/12siegel.pdf

I just wanted to ask you a question Benq. Tried to message you but was unable to do so.

"do smth instead of nothing and stay organized". What is "smth" in here? I am so curious and can not resist asking.

something

Thank you. I googled "smth technique", "smth method", even "smth algorithm".

But never searched only

"smth". It just never crossed my mind.Any tips on how you can compute the values in $$$O(|E|\sqrt{|E|})$$$? I figured out how to do it in $$$O(\sum_{i=1}^{|V|}degreein_{i} * degreeout_{i})$$$ which is bounded to $$$O(|V| * |E|)$$$, but I can't seem to find any improvement.

You can place $$$*k$$$ in a vertex $$$v$$$ if:

there are edges from $$$v$$$ to vertices marked $$$*0, \ldots, *(k - 1)$$$, and no edge to a vertex marked $$$*k$$$;

for each $$$u$$$ -- unmarked option of $$$v$$$ there is an edge to $$$*k$$$.

If the rule can not be applied anymore to any vertex, then all remaining vertices are $$$\infty$$$'s.

If all $$$*0, \ldots, *(k - 1)$$$'s are placed, then all possible $$$*k$$$'s can be placed in $$$O(E)$$$ with a reverse BFS-like traverse. We can stop after $$$k \sim \sqrt{E}$$$, since there has to be $$$\Omega(k^2)$$$ distinct edges for a $$$*k$$$ to exist.

Div2 C can be solved with binary search for the answer. 97454890

Sir, can you please tell me how did got to the solution of A? I just couldnt solve it after spending 2 hrs on it

Well, this is how I thought: -the easiest way for gcd not to be one — to take even numbers only, so gcd of any two to them is at least 2. -Okey, now it is necessary that there are no pairs of numbers that one is divisible by another. And again the easiest way to do so is to make ratio of any two less than 2. So we would have no such pairs for sure.

With two observations above I immediately got to the solution.

Thank you sir...really dont know how to bring those ideas even after regular practice..

Can you please explain your logic too!

In C?

First, let's say we are given some time x. How can we determine whether it's possible to get all the food in no more than x?

Let's go throw the a array. If a[i] > x then we need to go to take this item on our own. Summarise all such a[i]. If sum <= x, then it's ok, we can do this. Otherwise, it's not possible to do this in x.

Now we can use binary search on answer. (read about it in internet). We can do this since for some first x-s we can't do this in no more than x and starting from some x, which we want to find, we can. So in fact just need to find the first x such that we can do that in no more than x. And to find it we use the binary search.

can you see my code for C ? 103697796

i can neither understand the editorial nor your explanation.

what i did was , i would add up the time of the user if and only if that resulting sum after going to restaurant is less than the max(delivery) time.

But my solution is failing the 2nd test case itself ?

Or does it?

97479244

Suneet ORZ

Vectorization speeds up the 3000^3 main loop up significantly. (I didn't think that would be enough though, whoops.)

Anyway, the problemsetters should have done better. Thinking of this solution is quite simple, and countering it is also simple (just raising both the limits and TL works.)

see https://mirror.codeforces.com/blog/entry/84257?#comment-718314 for another reference

Can someone please tell me in whats wrong with my this solution for Div2D ? Submission

I can give a counter testcase Try 1 5 2 5 4 5 3

The answer should be no I think your code would output yes

Ahh thanks I found my mistake...

The answer should be no in the following array But this program says yes

~~~~~ 13 20 13 10 13 15 10 15 15 14 ~~~~~

In 1443D-Extreme Subtraction, my idea was to maintain two other arrays which will store the minimum element to the left of element in array and minimum element to the right of element in array respectively for each element in the array. This way I could check for all elements if they are less than or equal to the sum of left minimum element and right minimum element and if there is an element which is greater than this sum then for sure we can not reduce that element to zero. I passed the given test case but failed pretest 2. I'm attaching the code below please help if you can in letting me know where exactly I went wrong. Here is the code 97483817

The condition is not sufficient, e. g. your code prints yes for the following counterexample

(It's not possible, the output should be no)

P.s. Please don't post whole code, since it makes the comment section longer and less readable

Sir, can you kindly tell why the above approach of pythonPappi doesn't work?

As said, the described condition is necessary (all the inputs that produce "Yes" have to satisfy this condition), however, it's not sufficient (meaning that not every input satisfying this condition will have a "Yes" as solution). To see this, you can look at the counterexample I provided in my original comment. You need to come up with another condition.

Actually I came up with the same example when my solution gave WA. So, from your reply, shall I conclude that the above solution is not logically incorrect but rather it's not sufficient to solve the problem??

Yep. Exactly. The actual condition is narrower than the condition mentioned.

Div2B is simple. I wonder why I wasted my time to come up with a dp solution :))

waste a lot of time in dp +1

Can you explain your DP solution?

i have solved Div2B with a dp solution XD

the same for me

I want to cry out loud, got almost all things in problem C except the case when you have to bring all the parcel on your own!!! I feel it happened because I stressed out in the last, won't do that from next time. AC https://mirror.codeforces.com/contest/1443/submission/97496785

who asked?

Why be so toxic?

What does engine editorial mean?

This VK cup contest has several tracks (mobile, design, machine learning), and one of them is called "engine" which is basically a competitive programming track.

Div2D/Div1A tagged dp and greedy. Anyone please explain dp solution.

In Div-2 D,

The problem sounds like this — check that there are increasing and decreasing arrays, the element-wise sum of which is equal to the given array.Can someone elaborate on what this means and how it relates ?

If we could only decrease prefixes, then the whole array would need to be non increasing. If we could only decrease postfixes, then the whole array would need to be non decreasing.

Since we can do both, it must be a sum of both.

same, what is "the element-wise sum"?, can someone explain it?

Consider a non-decreasing array1 [2,4,5,8,11] and a non-increasing array2 [14,8,5,5,1]. As said above: If we could only decrease prefixes, we would want the array to be something like array2. If we could only decrease suffixes, we would want the array to be something like array1. Since we can do both, an array of the type array1 + array2, i.e. [2+14, 4+8, 5+5, 8+5, 11+1] would also give us a "YES"

can you explain how to check that?

Thanks for really helpful explanation)

The tutorial should have had this example..!!

Very short $$$O(n)$$$ solution for div2F/div1B 97497692, but I'm not fully clear about why it works.

Take a look at this submission 97441804.

The idea is the same I think.

Try to prove these facts:

For 1443A — Kids Seating, If there are 3 kids, can't we print "202 204 206" as answer? I get this when i submit the code "wrong answer Integer element [index=1] equals to 202, violates the range [1, 8] (test case 1)"

every number must be in the range 1 to 4n

Can someone give an explanation for div2D solution? I can't really understand what is written in the editorial.

Editorial of D is written for those who have solved D, I think :(

Observation 1:- We can do operations in any order it doesn't affect our final array A.

Observation 2:- If we do all prefix operation first and after it we get an array A which is non- decreasing then the ans is YES(as now you can apply suffix operation and decrease one by one from last also all elements must be greater than or equal to 0) if we get any other array then the ans is NO.

now our only motive is to make the array non-decreasing after applying prefix operations.

Why observation 2 is correct(with example) :-

A = [12,7,20,8,17]

step 1 -> at first we can decrease A[0] to 7 A = [7,7,20,8,17]

step 2 -> Since 7 7 20 is already in non decreasing order now we check 20 and 8 ..... since 20 > 8 so we have to decrease our first k(k=3) elements by 20-8 to make 20 equal to 8 . A = [-5,-5,8,8,17]

though we got an non — decreasing array but our First two elemnts are less than 0 so ans = "NO"

for more clarity https://mirror.codeforces.com/problemset/submission/1443/97522500

sorry for bad english.

I_will_come_back you explained really well! I really wish that the editorials are written in great detail so that everyone understands.

Thanxx mate... Ya i also feel same for some editorials....

very nice, thanks!

Your explanation is really easy to understand!

mast explanation diya brother :)

As stated in other comments, We can just chose to perform all the prefix operations first. In that case, the array after performing the prefix operations must be non-decreasing.

I saw I_will_come_back's submission. Thank you for the explanation. Just wanted to post a simpler way to solve it using the same concept.

So I traversed the array from the end and kept a count of the decrement till the index 'i' For eg. [11 7 9 6 8] initially: count =0 , i = n-2 Since the final array should be non-decreasing,Whenever we encounter, arr[i]> arr[i+1] we'll update count and arr[i] i.e. for i = 2 here, arr[i] will become 6 and count will be updated to 3. After the loop, we just need to check if all elements in the modified array are >=0 or not.

Take a look at my submission if needed.

97652518

Have fun coding :')

Why this code is getting different verdicts for the same code in C++17(64) and C++17 ?

Accessing

`a[i]`

if`i`

is out of bounds is undefined behavior. Anything is allowed to happen.Maybe your solution is just too slow, but in one case you were lucky to get runtime error. Another theory is that accessing

`a[i]`

for some big`i`

overwrote`n`

causing your loops to go on very long.Thanks! n must have been overwritten. The solution isn't slow, this submission got accepted. This thing ruined my contest, I am not using global variables ever again.

Global state is evil, but I'm not sure how you will prevent out-of-bounds access just by not using global variables.

Would double check too. I wouldn't at least get weird verdicts by not using global variables.

11 6 7 10 9 9 8 ,can anybody explain why and how it is yes

BTW, my solution to Div2.D problem.

This may be a dumb question but how is the answer for sample 3 in div2D NO?

Is the following not a possible sequence of performing operations?

[1 3 1 3 1] -> [0 2 0 3 1] -> [1 2 0 3 1] -> [2 2 0 3 1] -> [1 1 0 3 1] -> [0 0 0 3 1] -> [0 0 0 2 0] -> ... (and similarly for the 2 0 in the suffix)

You can't increment! The question states that you can pick first k or last k elements of the given array and decrement it by 1.

Oh okay thank you :)

Made the silliest mistake of my life in Div2D.

if(n==1) cout << arr[0] << endl;

instead of

if(n==1)

cout << "YES" << endl;

:(

is it rated?

Just to mention, as a full-BFS solution to Div.1 problem C:

Let $$$base_{0,u}$$$ be the minimum (even) number of required transpositions to reach the vertex $$$u$$$. Similarly let $$$base_{1,u}$$$ be the minimum (odd) number of required transpositions to reach the vertex $$$u$$$.(Note that their difference wouldn't be greater than 1.) We can evaluate $$$base$$$ numbers by a 0-1 BFS algorithm:

Create a graph with a node for each of the $$$base$$$ array cells;

`u->v`

edge in the original graph, connect $$$(0, u)$$$ to $$$(0, v)$$$ with a $$$0$$$ edge.`u->v`

edge in the original graph, connect $$$(1, v)$$$ to $$$(1, u)$$$ with a $$$0$$$ edge.Now declare $$$dis_{u, i, j}$$$ as the minimum number of token movements needed to reach $$$u$$$ while $$$base_{i, u} + j$$$ transpositions have been applied and the oddity(# % 2) of the applied transpositions is equal to $$$i$$$(Yes! Half of the states are unused/invalid.). To update $$$dis$$$ values, create a new graph with a node for each triple $$$(u, i, j)$$$.

`u->v`

edge in the original graph, connect $$$(u, 0, j)$$$ to $$$(v, 0, j + base_{0, u} - base_{0, v})$$$ with a $$$1$$$ edge.`u->v`

edge in the original graph, connect $$$(v, 1, j)$$$ to $$$(u, 1, j + base_{1, v} - base_{1, u})$$$ with a $$$1$$$ edge.Then run a 0-1 BFS from the $$$(1, 0, 0)$$$ node to evaluate each $$$dis_{u, i, j}$$$.

The answer equals to the minimum value among $$$2^{base_{i, n} + j} + dis_{n, i, j}$$$ with all of the possible $$$i, j$$$ values.

It can be easily proved that it's enough to set the $$$log(m)$$$ as an upper bound for $$$j$$$(third argument of $$$dis$$$) and still solution works correctly. So the size of $$$dis$$$ would be $$$n . 2 . log(m)$$$ and the whole solution would work with $$$O((n + m).log(m))$$$ time complexity.

Is this just for the first part of the problem? What about when you have to do $$$m-1$$$ transpositions? (A line graph with alternating directions on edges.) It seems $$$j$$$ will have to be $$$O(m).$$$

Not actually; Note that $$$j$$$ is the difference between "minimum number of required transpositions to reach $$$u$$$(i.e. $$$base_{i, u}$$$)" and "the actual number of applied transpositions to reach $$$u$$$ in an optimal way", this

differencewouldn't exceed $$$log(m)$$$.I think in your example $$$base$$$ values would be large enough(almost equal to m or n).

Oh, of course, I understand the definition now. Cool!

Is there any explanation (proof) for 1442B — Identify the Operations for a fact that decisions 1..X-1 (to pick i-1 or i+1) doesn't influence outcome of step X? Basically that it doesn't matter what we did before, step X will always have 0, 1 or 2 options for all possible sequences. I got AC, but wasn't able to prove it.

Here's my thought:

Suppose that we're currently processing $$$a:=b_i$$$ and let $$$c:=b_j$$$ for some $$$j>i$$$. There are two possible cases that previous operations influence our current choice:

The first case is impossible because, before $$$a$$$ moves to the border, the number between $$$a$$$ and the border must be deleted and thus $$$a$$$ is added to $$$b$$$, but numbers in $$$b$$$ are unique, so it's impossible. The proof for the second case is similar.

We need to choose the elements in b[] in given order. So, foreach the coresponding a[i] we can choose the left or right neighbour if it exists. Doing so does not change the number of chooseable neigbours of other elements. Because the removed one is replaced by the choosen one. Because of this the 0, 1 or 2 is invariant.

your comments always makes sense!

I have an easier solution for Div2F — Div1B: Go through the elements of b, look the position of the current number in b. If there is only one possible neighbour to delete (either on edge of list or one neighbour is a future number in b) take it, if there is no possible neighbour then the answer is 0, and if both are possible you can take either one since the result is in each case the same (the other not taken numbers are equal to the other two possible not taken numbers, each of those numbers can be taken in the future and which two we take doesn't influence the indexes of future takes). You can maintain this with a linked list, nodes have two pointers for neighbours, EZ O(n). Here's my submission: https://mirror.codeforces.com/contest/1443/submission/97489269, it's ugly cuz I didnt have much time left, should have made some Node classes instead of just keeping it in an array but thankfully I didn't make any mistake while implementing it (unlike on most tasks in the contest lmao).

nvm the solution in the editorial actually isn't really different, I just thought it must have been cuz it was nlogn. The problem was really easy for a F type.

In problem B, I used memoization. int memo[1e5+1];

I do a memset(memo, -1, sizeof memo); at the beginning of each test case.

There are 10^5 test cases, and i do memset at each one of them. yet my solution was accepted !!?

any explanation?

https://mirror.codeforces.com/contest/1443/submission/97508001

It looks like the answer could be weaker test cases — even though the limit is given as 1e5, the max value in the test cases seems to be about 11000. Whilst this would still result in many operations, my understanding is that 1e9 of the very simplest operations is achievable in the time limits. You could try a custom invocation with 1e5 test cases and I suspect it might fail. I’m not certain, though.

Maybe the test data is too weak...

I even saw that someone use an $$$O(n^2)$$$ algorithm to pass a problem that $$$n\leqslant 10^6$$$. It worked successfully and accepted the problem :)

Your code passes T = 1e5 in 900 ms :)

How to solve Div1B — 1442B - Identify the Operations if the resulting array $$$b$$$ is not distinct?

I thought I'd share my solution for 1A as I think it's way more interesting than the editorial's solution.

Let's assume the input array $$$a$$$ is the prefix sum array of some array $$$b$$$. Then it's obvious that $$$b_{i} = a_{i}-a_{i-1}$$$ for all $$$i \geq 2$$$ and $$$b_{1} = a_{1}$$$. Now we simply check to see if the absolute value of the sum of negative elements in $$$b$$$ is strictly greater than $$$a_{1}$$$. If it is, the answer is "NO" otherwise "YES"

This boils down to the fact that an operation on the prefix decreases $$$b_{1}$$$ by $$$1$$$ and increases $$$b_{x}$$$ by $$$1$$$ where $$$x$$$ is the length of prefix chosen. An operation on the suffix simply decreases $$$b_{y}$$$ by $$$1$$$ where $$$y$$$ is the length of suffix chosen. Because of the 2nd operation, we can always make the entire array $$$0$$$ if array $$$b$$$ consists of all non-negative numbers. In order to make negative numbers $$$0$$$, we have to "move" a $$$1$$$ from $$$a_{1}$$$ without letting $$$a_{1}$$$ becoming negative itself.

97513072

Perfect. but it is hard to come up with a solution like this At least for me in contest time or may be after that :).

In DIV1C, for the second part, when we know that B > log2(m), I used Dijkstra where distance is a pair where the first part of pair is B and second is A (B and A are same notations used in Editorial). Instead of splitting the graph into two different graphs, I used the number of transpositions till now to decide whether I can traverse the edge or I need to transpose it again. I ensure the minimum value of B, and if B is same, then I checked the value of A. But this approach is getting wrong answer on test 7, and I'm not sure whether there is something wrong with my approach or I can't implement Dijkstra in this way. Please help me understand my mistake. I really appreciate any help you can provide. Link to my submission.

Consider 3 vertices a, b and c. You are currently in a, but you need to reach c, and the only way to do that is through b. To reach b you can either transpose and go to a short path to reach b, or you take a long path to reach b without transposing. But once you reach b you need to transpose to reach c, so it would be better to have transposed earlier (in a) so you could take this shorter path. Thats why you need to duplicate the graph, you cannot transpose lazily.

It took me some dry runs to understand what you are saying, but I finally understood it. Thanks a lot.

I have a solution that is different from 1443A: You can preprocess the first 100 prime numbers and, when you print the answer, times 2 for each number and that could be fit for the request of the problem :)

It will run into an issue for n=6 (it gives 4, 6, 10, 14, 22, 26). Here, 26 exceeds the limit of 24 (4*n). I started solving it that way and ran into this issue — had to improvise. However, the editorial solution is cleaner (i.e. take multiples of 2 starting backwards from 4*n, you'll be okay every time — since their gcd will be at least 2 and they won't divide each other).

I tried that but it had some problem. Like when n = 5, then your answer is 4, 6, 10, 14, 22. But 22 violates the range [1, 20]

Oh I forgot! I didn't pass using the algorithm :(

Why didn't you post analysis for 1441F - Matching

Fixed

I still don't see it. Also, could you open up that contest (or at least that problem) for practice?

This is apparently a classical problem. This 2001 paper has the solution: https://collaborate.princeton.edu/en/publications/unique-maximum-matching-algorithms

The main observation is a theorem of Kotzig: Consider any graph with a unique perfect matching. Then, that perfect matching contains a bridge of the graph. Intuitively, any biconnected graph has either 0 or at least 2 perfect matchings, because there are enough cycles to find a second matching. I found a short proof here: https://arxiv.org/abs/1402.0949.

Now, to solve the problem, we just need to repeatedly identify bridge edges, decide if the two components it connects are odd-sized, and if so, use the edge and delete both endpoints. We can do this with merge-smaller-into-bigger or parallel-BFS type algorithms on the faces.

I had different solution for problem C. I searched for the minimum number of steps that we should make if we are allowed to make up to $$$T$$$ transpositions. To find such value we can duplicate all nodes, assign cost 1 to regular edges, and cost $$$X$$$ to edges that make transposition. Then, with binary search we can find such values. To avoid several binary search, we can run a single binary search that looks for all values at the same time.

I didn't put too much thought about what was the complexity of this solution during the competition (lucky me). The complexity is $$$O(|V| \cdot \log |E| \cdot |C| \cdot \log |C|)$$$ where $$$|C|$$$ is the total number of distinct target paths that exist. Target paths are those such that a value $$$X$$$ exists where $$$T \cdot X + steps$$$ is minimum among all paths. During the competition I thought this number was bounded by $$$O(n^{\frac{1}{4}})$$$ but it turns out that there are graphs where the number of distinct target paths is $$$O(n^{\frac{1}{2}})$$$.

I managed to hack my solution with one such graph.

I was solving div2B, and found this unexpected runtime error in the below piece of code, can anyone explain what's going on?

while debugging, I found that even after

`prs.size()==0`

,`for`

loop is getting executed and then giving the error. Pls help.here is the full code for div2B- https://mirror.codeforces.com/contest/1443/submission/97530452

I had to use

`if else`

to get ACprs.size() is unsigned type, so prs.size()-1 is unsigned, too.

What is the proof for Div1B?

Let's say the answer to the problem is not $$$0$$$. Then how to prove that in the case $$$(3)$$$ while choosing any of the $$$a_{i-1}$$$ or $$$a_{i+1}$$$ will always lead to the solution in the end rather than ending up in a contradiction later on.

First, we can notice, that the actual values are not very important. Let's use

`|`

to denote something that we will use later, and`.`

to denote something removable. You should note, that the order of the`|`

chosen is still important, though not represented here.So our array looks like

`..|...|...|...|...|....`

Now we can see that one of the

`|`

will be next. After we add it to the array b, it is useless, and removable like a`.`

, because all values in "b" are distinct. So using either`|.`

and`.|`

in`.|.`

yield a`..`

. So the next state is the same regardless of whether we choose left or right.Can someone Pls suggest some more problems like div2D/div1A.

it's the easiest pblm in this contest! A was way harder for me! -_-

Don't know who needs this counter test case in div 1C but I definitely did, so I'll share it:

Expected Output: 8

I need! :D Thanks ;)

I think the test data of Div2D/Div1A is not so strong, here is an accepted $$$O_{(n^2)}$$$ solution.

About Div.1 D, I have another solution with complexity O(nklgn)，the idea is that some of element will never be choice.Then we calculate the prefix sum and sort the column，for the j-th column the last n-1-k/j element will never be choice. here is code. https://mirror.codeforces.com/contest/1442/submission/97548953

Someone can explain Div2E task. How we generate a permutation with the corresponding number?

And why only the last 15 elements need change, if there may be such a situation when the last 15 elements are initially in descending order and the 16th element needs to be changed

There are n! permutations of {1,2,3,...,n}. But how do they look in lexicographic order?

Let's look at first 6 permutations (n >= 3): 1: {1,2,...,n-2,n-1,n}, 2: {1,2,...,n-2,n,n-1}, 3: {1,2,...,n-1,n-2,n}, 4: {1,2,...,n-1,n,n-2}, 5: {1,2,...,n,n-2,n-1}, 6: {1,2,...,n,n-1,n-2}. As you see, only last three elements were changing their positions. Why? Because 3! = 6, so first 3! = 6 permutations only permute last 3 elements. In general, for given 1 <= k <= n first k! permutations of {1,2,...n} only last k elements change their positions, the first n-k elements are always {1,2,...,n-k} in that order.

"And why only the last 15 elements need change?" - Let's notice that we have x <= 2e5 and q <= 2e5 and we start from X=1 permutation index. Therefore at the end maximum possible index is X <= 1 + 2e5 * 2e5 = 4e10 + 1. Just because 15! > 4e10 + 1, we know that only last 15 elements can change. In fast it is sufficient to look at 14 last elements, as 14! = 87178291200 > 4e10 + 1.

"How we generate a permutation with the corresponding number?" - We can enumerate all permutations of {1,2,...n} with integer numbers from [1,n!]. An example algorithm of retrieving permutation from its index is explained here: https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/. However, this code returns string and assumed an integer index, but in our case it can exceed integer range, remember about it. My code (https://mirror.codeforces.com/contest/1443/submission/97579828) uses this approach to retrieve permutation from index, you can look at it.

In editorial of problem Div2 D : How to prove that " maximizing each element of the decreasing array" is the best way to construct the increasing and decreasing array and can people tell their train of thought while arriving at above during contest.

Please help me to find what I did wrong in my code.

https://ide.codingblocks.com/s/367339

In my Approach, I simply created two partial sum arrays. The first from the beginning called pre and the second from the end call sum.

D <= C <= B <= A <= F <= E for div2 -_- A ruined my whole contest!

Did anybody solve div2D using segment tree like me :v

Here is LimitBreaker's submission with segment tree, just in case.

someone please explain how third statement is correct? According to me array should become [2 1 0 -1 2]

1.decrement from the first two elements of the array. After this operation a=[2,1,2,1,4]; 2.decrement from the last three elements of the array. After this operation a=[3,2,1,0,3]; 3.decrement from the first five elements of the array. After this operation a=[2,1,1,0,3];

Can someone tell me how the divide and conquer works in Div1 D?

Basically, we are aiming to solve knapsack problem (precisely, calculate entries of dp array) for $$$n$$$ elements but $$$i$$$-th one for all $$$1 \le i\le n$$$ mentioned in the editorial.

Here, we will divide $$$n$$$ arrays into two halves ($$$A$$$ and $$$B$$$), and then calculate the dp array $$$dp_l[]$$$ (resp. $$$dp_r[]$$$) if we take the first half (resp. second half) elements into account， i.e. we are free to choose any subset of the first half(resp. second half) elements. With auxiliary array $$$dp_l[]$$$(resp. $$$dp_r[]$$$) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way.

btw, you may check others' implementation to get a better understanding. (That's how I understood above approach... I was confused by editorial as well)

I understand , thank you very much:)

Can you more explain what does it mean?

"With auxiliary array dpl[](resp. dpr[]) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way."

For problem C, why does Accepted one works while this almost identical one Wrong One gives memory limit exceeded . The only difference between the two solution is that I copied the contents of the loop from the wrong one and pasted it in a function, then called it instead in the loop to solve, and now I don't get memory limit exceeded using the function. Why is this happening ?

Problem C

Can anyone please explain me problem D of div 2. I am not getting it

We can decrement any suffix by 1. We can decrement any prefix by 1.

Now we are asked if its possible to make each element of given array as 0 by performing above 2 operations.

thanks but i am not getting how taking difference and subtracting it from first element and checking that it is greater than or equal to 0 give yes. Please can you explain it.

Honestly I myself couldn't understand the editorial solution. I solved using a different approach about which you can find here

thank you for your help.

Welcome.

I've written a blog post to explain the solution to 1443D (D1A / D2D)

I think your blog has been removed.

Nope it's still there?

It shows me you are not allowed to view the requested page.

That's bizarre, likely some bug in the site. cc'ing MikeMirzayanov as I'm not sure where else to post site issues

Squeezed $$$O(n k \sqrt n)$$$ solution in D1D. With pragmas submission

Good evening, this is our solution for problem C with explanation.

In C I used multimap and it was ac,then i used map and for multiple same courier delivery time i kept summation of all the pick up time at the index of that courier delivery time.Rather than this one difference everything else was same.why it isn't working? Example 3 3 5 5 / 2 2 2 2 I kept 4 at index 3 and 4 at index 5.

Here are my submissions: AC:https://mirror.codeforces.com/contest/1443/submission/97495754 WA at TC2:https://mirror.codeforces.com/contest/1443/submission/98000111

I'm retarded

Div 1C is just pure genius (the making copies of graph part). Never seen this before. Just....wow.

300iq This page is not linked with the contest problem page neither is the announcement page .. Can you please look into it

memory efficient DP approach for problem B: https://mirror.codeforces.com/contest/1443/submission/101710030

Hi, I didn't want to make a new blog for this, so here I am. Regarding problem D.

SpoilerPlease correct me if you see a mistake. Any help is greatly appreciated.

So, basically, for each i, we have a range of $$$[L,R]$$$. For all ranges of all element, could we choose a number $$$X$$$, such that if we create an array which will stores the value $$$X$$$ for all $$$i$$$, the array could be non-increasing ?

In problem D, why is it

`check that there are increasing and decreasing arrays`

? why not`check that there are decreasing and then increasing arrays`

? Isn't the problem basically boils down to whether we could make the the array decreasing and then increasing ?