Fixed, thanks.

He creates new problem and solves it.

I think he doesn't sleep!

Isn't div.2 pretty much that already?

Guys It was a joke why do you minus that?

Именно поэтому у меня есть договорённость о тестировании раунда студентами Саратовского ГУ (не финалисты ICPC, другие ребята). Но вот отмечу, что от тестирования сильными участниками было много пользы — реально помогли найти интересные тесты, сделали серию улучшений условий.

Это, кстати, интересный вопрос: кто будет более успешен в придумывании плохих решений — участник с рейтингом 2600 или участник с рейтингом 1500 :)

wata???

thank him for rigging it up so we lose? no thanks

ha, some guy at the top said almost the same thing and he got a bunch of downvotes. funny

It is real to do this, and if this fails, you can always complete tasks after the competition

well it obviously isn't but do they care? no, they don't care about us

I go TLE. i tried to avoid it but got TLE in different test cases.

This is my Code

any hint ?

You are given essentially a difference array, so if you compute the prefix sum array you should get the original elements offset by some number. You keep track of minimum and maximum of this prefix array, and the first element should be 1-minimum. While constructing the original array you also make sure each element from 1 to N is seen once only.

Hello! Let's write our array as: p2-p1, p3-p2, p4-p3, ... , p(n) — p(n — 1).

Now let's find the prefix sum of this array. Then we will have following: p2-p1, p3-p1, p4-p1, ... , p(n) — p1.

I think it is obvious that if we have two same elements in the prefix sum array then answer is -1.

Otherwise let's take element n-p1 (it is the maximum). Let it be equal X. Then n-p1 = X -> p1 = n-X. Now, using this p1, we can construct our array. If such answer is valid, we can print it. Otherwise answer is -1.

You can assume the first element be x. then the second element is q1 + x third element is q1 + q2 + x. the fourth element is q1 + q2 + q3 + x and so on. the sum of all elements is (n*(n+1))/2

so you can find the value of x.

after finding x you can easily find entire permutation

I solved using prefix sums and some basic maths.

Approach:

$$$(q_1) = (a_2-a_1)$$$

$$$(q_1+q_2) = (a_3-a_1)$$$

$$$(q_1+q_2+q_3) = (a_4-a_1)$$$

And so on. Summing all the above equations we get:

$$$\Sigma ($$$prefix terms of $$$q)=(a_2+a_3+...+a_n)-a_1(n-1)$$$

$$$\Sigma ($$$prefix terms of $$$q)=((n*(n+1)/2)-a_1)-a_1(n-1)$$$

Find $$$a_1$$$ from the above equation. Once you find $$$a_1$$$, you can easily find the rest terms using the given values of $$$q$$$. Finally, check if all terms are present in the range $$$1$$$ to $$$n$$$ and also check if all terms are distinct or not. If not, print $$$-1$$$ and exit. Else print the numbers.

I'll leave the implementation part for you to try. Hope this helps. Happy Coding.

Think of it as plotting n points on a 2d grid where the index of the array is the x coordinate and value at that index is the y coordinate, start from (1,0) (assume the value of the first element to be 0) and use the given array q for calculating the position of next points. a[1] = 0 a[2] = a[1] + q[1] a[3] = a[2] + q[2] and so on. Now find the minimum value in this array, let the minimum value we get from the constructed array be min_val. Now add min_val+1 to all the elements of the array (shifting the whole plotted figure up so that the lowest point is 1).Now check whether the array is a valid permutation or not and print the result. Here's the implementation of above mentioned approach. 51508498 Hope this helps.

My approach i wrote the O(n ^ 2) approach to find a sequence. let's assume that the first element is a1 = n, so we get sequence a1, a2, .., an if we decrease the first element by 1 all other elements also decrease by 1 so i assume that the first element is n and i make sure that are elements are distinct and if i increase or decrease my sequence the min and max element inside the sequence is 1 and n. 51541819

Listen to twice and you will solve problems faster.

Your display picture perfectly describes your reaction.

In this problem 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths, input ensures that there is only characrer a-v.

I fail to solve this problem, just because I missed it :(

This complexity is too high I think you should learn from others' code.

The number of all permutation is $$$O(n!)$$$, and for each permuation, you need $$$O(n)$$$ to check it.

So your solution is $$$O(n\cdot n!)$$$, quite large :(

You can try an array $$$n, n-1, n-2,\dots,1$$$, and n is $$$10^5$$$, your solution will get TLE :(

When n is quite small, your solution can get the answer.

Just use map<int,vector<R,L>> store the sum of every l and r,after that you can sort the vector and get the answer.

$$$n \le 1500$$$, so you can use a map to store each block with the same sum.

For each sum, there are many segments, and some of them may intersect. so you need to calculate the maximum number of disjoint segments, and this problem an be solved using greedy algorithm.

There are only O(n^2) many (L-R) pairs. You can generate all of them, and group them by their sum. Then find the maximal non-overlapping subset of each group. This can be done greedily (by sorting first appropriately).

"It is guaranteed that a_i = 0 for at least one i"

The Universe will explode!

How to solve your blindness? There is not H problem in this round.

I'm pretty sure that your solution also gives the wrong result on your computer. Check again.

You can see it after the hacking phase.

Edit: Sorry, I forgot they show all pretests during div 3 rounds.

I checked your code earlier but I gotta admit I was to lazy to understand it. Can you explain your solution?

Write a brute-force program and make some small scale random input to check whether your algorithm is correct.

If you can't kill the monster in round x, it doesn't mean that you can't kill it in earlier rounds.

why i am dwnvted. have i asked anything wrong

So, I haven’t submitted this solution yet, but I think I have the idea.

Generate the degree sequence for the tree. The k nodes with the highest degrees will be bad nodes. Then the (k+1)th highest degree (call it c) will be the number of colors needed so that (n-k) nodes are good and k are bad. That is, with c colors, we can color edges so that (n-k) nodes have edges of all distinct colors. This will work because (n-k) nodes will have degrees <= c.

We can then choose a root, and greedily color the tree from the top down.

Your binary search borders are so high they cause long long overflow in min hp calculations.

yes.. i solved it.. see my solution and if doubt dm or tag me in announcement

Meh, that's the boring hack. Check this solution 51538168! $$$cp$$$ gets equal to $$$-2^{31}$$$, then $$$x$$$ becomes $$$2^{31} + 1 = -2^{31} + 2$$$ and thus no $$$-1$$$ checks are hit because the conditions are too weak.

You are already very good, I only solved 3 problems.

Great contest, I learned a lot of ways to think about the problem.

Same thing happened with many people(including me).

Not sure those are final, as an unrated before taking part in the contest, I'm already rated, but seems final standings are yet to be shown.

The segments should be sorted by the right end, so you greedily take always the one that ends the earliest.

Just think simple!
We know that ? will make compatible pair with anything!
So first we make pairs that doesn't have any ? and after that pairs that has exactly one ? and at the end pairs that are both ?.
It is clear that the algorithm is the optimal.

Look, the boots are for the left or for the right foot.
You want to match these boots (make pairs of left and right boots).
And "You can't use one boot in two pairs" means that you can't match a boot with two other boots.
For example you have two boots of left foot numbered 1 and 2, and two boots of right foot numbered 3 and 4. you can't match boot number 1 with boots 3 and 4, you can choose at most one of them.

that is for div2 and div1 contests (expect educationals).
hacks in contest's that have hacking phase after the contest don't have any point.

most people did not check the duplicate elements they generated in permutation