There can be multiple edges. For instance:
1 2
2 1

Using a set will give WA. Try multi-set or some other data structure in c++.

Edited by author 07.09.2020 15:22

Edited by author 07.09.2020 15:22

WA8
Please, explain, what is the reason? Is this just a problem of input/output or this is just such test case?

Let c[i][0] = a[i], i = 1..n
    c[i][1] = c[i+1][0] - c[i][0], i = 1..n-1
    c[i][2] = c[i+1][1] - c[i][1], i = 1..n-2
     ....
    c[i][d] = c[i+1][d-1] - c[i][d-1], i = 1..n-d.

   if hardness of a[i]  is d.  so all c[i][d] = const.

    1. Find minimum d, that  all c[i][d] - is const.  (example:  binary search).
    2. build b[n+i] from c[i][d].


There can calculate c[i][j] through a[i] sequences:

    c[i][1] = a[i+1] - a[i]
    c[i][2] = c[i+1][1] - c[i][1] = (a[i+2] - a[i+1]) - (a[i+1] - a[i]) = a[i+2] - a[i+1] - a[i+1] + a[i] = a[i+2] - 2*a[i+1] + a[i].

   c[i][3] = c[i+1][2] - c[i][2] = (a[i+3] - 2*a[i+2] + a[i+1]) - (a[i+2] - 2*a[i+1] + a[i]) = a[i+3] - 3* a[i+2] + 3*a[i+1] - a[i].

   ..
   c[i][d] = SUM( c[i + d - j ] * Binom(d, j) * (-1)^j, j = 0..d)

    where Binom(d, j) - Binominal coefficients , or  coefficients of (x+y)^d .

  if d - is known,

   c[1][d] = c[2][d] = ... = c[n-d][d] = W - constanta.

  b[n+1] = x

   c[n-d+1] = b[n+1] + SUM(a[n + 1- j] * binom(d,j)*(-1)^j, j = 1..d)  = W

   b[n+1] = W - SUM(a[n+1-j] * binom(d,j)*(-1)^j, j = 1..d)

   and so on.


  Only one problem,  how fastest calculate SUM(a[i + d - j] * binom(d,j)(-1)^j, j = 1..d)   ?

You might want to study this article: https://www.elcamino.edu/faculty/gfry/210/DistributeDifBallsDifBoxes.pdf

Please, give me test 18

Pigeonhole principle: It will always be possible and the answer will always be a continuous sequence.
How to solve:
Consider N = 7:
1 2 50 3 4 0 0
The sum of the segment 1, 2, 50 is 53 and that of 1,2,50,3,4 is 60
53 % 7 = 4
60 % 7 = 4
if a % x = 1
and b % x =1
then (a-b)%x is always 0
So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7

this

3 1
1000 90
1000 90
1000 90
2 5

helps me

I've noticed that the solution is always the number of walls we encounter*9 (excluding the first and last boxes). Why is this working?

If you pick n-1 as l then the second player will always win, so answer can never be 0
0 means  picked up the first player and 1 means picked up the second;
Case 1: 3 buttons
for i = 1 //doesn't make sense to solve for 1 since its asked to choose >=2
1 2 3
0 1 0 //first player won
for i = 2
1 2 3
0 0 1
0 1 1 // first play wins in each case
Case 2: 4 buttons
for i = 2
1 2 3 4
0 1 1 0
0 1 0 0 //first player wins in both these cases
for i = 3:
1 2 3 4
0 0 0 1
0 1 1 1
0 0 1 1 //second player wins in each case
case 3: 6 buttons (5 and 6 are similar)
1 2 3 4 5 6
for i = 2
0 1 1 0 0 1
0 0 1 0 0 1
0 1 1 0 1 1 //second player is  winning

It's clearly seen that the minimal choice to win is k such that n %(k+1) == 0
since n%((n-1)+1) is always 0, n-1 is always an answer in case no smaller answer exists.

import itertools
surprize =[]
x = int(input())
while x > 1:
    x -= 1
    surprize.append(x)
print (len(list(itertools.permutations (surprize))))

It's very easy to calculate this integral. But if you don't know what's integral, there are solution

In-first, i calculated a k
k = (a^2 * b * pi / 8) (or a*a*b*0.39269908169872415480783042290994 :) )
In-second, you should calculate y (or other symbol) from 1 to -1 with division (if n = 5: 1, 3/5, 1/5, -1/5, -3/5, -1)
In-third, calculate F(y) = y*(1 - y^2 / 3). (F(1) = 2/3)
in-fourth, print k*(F(yi) - F(y(i-1))) in loop
example:
if n = 2: first calculate should be k*(F(1) - F(0)), second k*(F(0) - F(-1))
if n = 3: 1) k*(F(1) - F(1/3)); 2) k*(F(1/3) - F(-1/3)); 3) k*(F(-1/3) - F(1))
etc.

[code deleted]

Edited by moderator 02.09.2020 19:58

If you want to get AC for a Kotlin solution, you should probably use java.util.Scanner instead of readLine() and try multiple times. I was able to get AC only on the second try with the same code, got TLE first time.

Read tasks and deadlines from the programmer's handbook. similar greedy approach will work in this one.
Also, why is this tagged dp? my dp soln is giving tle

Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую.
Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%)
Удачи.

hm.ok



Edited by author 25.08.2020 03:14

Why WA#8?

How to solve this problem using c++ ? My pick is  #MLE 14. I use (10^5 + 1000)*4 + 10^5 * 2
 = 589,84375 kilobytes of memory. I have no idea how to optimize it even more(

Edited by author 20.08.2020 02:34

Edited by author 20.08.2020 02:34

My AC code gives "No" on the following testcase due to the overflow
1000000000 1000000000 1000000000
0 0 0