Edit: Nvm, it's showing up now

How does the interactor work for F?

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

Straightforward dp solution, where s(i,j) – max possible sum after j operations on first i arrays and transition in O(k), has complexity of O(nk2) or precisely O(k⋅min(nk,∑i=1nti)) and doesn't fit into the time limit.

Or does it?

97479244

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

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

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

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://codeforces.net/contest/1443/submission/97496785

What does engine editorial mean?

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 ?

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

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

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

Немного оффтоп: в статье Смита есть такая иллюстрация

Правда же, что $$$G(V_5)$$$ должно быть 1? Игра $$$V_5 + 1$$$ проигрышная.

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

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

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)

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;

• Connect $$$(i, u)$$$ to $$$(1 - i, u)$$$ with a 1 weighted edge.
• For each u->v edge in the original graph, connect $$$(0, u)$$$ to $$$(0, v)$$$ with a $$$0$$$ edge.
• For each 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)$$$.

• Connect $$$(u, i, j)$$$ to $$$(u,\ !i,\ j + base_{i, u} - base_{1 - i,\ u})$$$ with a $$$0$$$ edge.
• For each 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.
• For each 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 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.

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://codeforces.net/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).

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://codeforces.net/contest/1443/submission/97508001

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

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.

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

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

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.

for(int i=0; i<(prs.size()-1); ++i){
    int diff = (prs[i+1].first - prs[i].second -1);
    if((diff*b)<a){
        cost+=(diff*b);
        segs--;
    }
}

here is the full code for div2B- https://codeforces.net/contest/1443/submission/97530452
I had to use if else to get AC

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.

Can someone Pls suggest some more problems like div2D/div1A.

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

9 9
2 1
2 3
9 3
1 4
4 5
5 6
6 7
7 8
8 3

Expected Output: 8

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://codeforces.net/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

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

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?

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

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

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://codeforces.net/contest/1443/submission/97495754 WA at TC2:https://codeforces.net/contest/1443/submission/98000111

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://codeforces.net/contest/1443/submission/101710030

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

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

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 ?