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.me/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.me/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.me/contest/1443/submission/97508001

How to solve Div1B — 1442B - Восстановление операций 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 - Паросочетание