Автокомментарий: текст был переведен пользователем giraffeh (оригинальная версия, переведенная версия, сравнить).

D сильно проще решается.

Заметим, что расстояние от точки (p, p) до ближайшей точки пересечения одной из искомых прямых с прямой x = y всегда равно . Давайте тогда решать одномерную задачу на прямой x = y (как в первом абзаце разбора). Теперь мы знаем множество всех координат прямых, осталось только для каждой координаты понять, есть ли там вертикальная и горизонтальная прямые. Для этого возьмем любую координату, которой в нашем множестве ответов нет (назовем ее z), и будем проверять точки (x, z) и (z, x). Суммарно запросов будет не более 3(n + m).

25915181

123 0 21 4

543453 -123 6 1424

ответ жюри 0, тогда как q = 0 и в массиве нет числа 0? Или я чего-то не понимаю?

I did Div 2 C using another method for final iteration.

I sorted the skip array by their absolute value. So, the array will look something like this 2 -4 5 8 -8 10.

Then, in the progression loop, I use a pointer which points to the next element of skip array. I increment the pointer until abs(skip[pointer])>abs(elem). Then, check if skip[pointer]==elem.

I think div2 C, D and E are really nice problems

simple solution of div2C/div1A..http://ideone.com/SCmlJ2 using dp without pointer..

Can someone please explain how the graph is constructed in Div 2 E and why it helps in finding the solution of the problem?

I submitted some wonky solution for C which works in . Couldn't prove a tighter bound myself but it runs pretty fast.

Did anybody else do the same? Could you prove a tighter runtime?

The idea is that the more unique drinks you have the lower your total volume required

In problem Div1 D, there is no need to randomize. First I find, as explained in editorial, all points x such that there is a line (vertical or horizontal) that pass through (x, x). Then, to test if the line is horizontal or vertical (or both) I pick some y such that certainly no line pass through (y, y) and query the points (x, y) and (y, x). f(x, y) =  = 0 iff there is a vertical line in x, because we know there is not horizontal line in y, the same idea apply to f(y, x).

My submission here. 25933644

I used a different (and I think simpler) approach for Div1E.

Start with the same pre-processing as in the editorial, computing smaller_pref_i and smaller_suf_i for all i. Once we've done this we can forget about the assistants and concern ourselves only with ways to select the three players.

For each distinct skill value v, create a separate segment tree to count possible teams such that the players have skill v. The segment tree for skill value v should have one leaf for each soldier with skill v.

In the segment tree nodes we put 4-by-4 matrices m, where m_i, j indicates the number of ways to select players [i, j) from that segment. So for someone unable to play we should set his leaf to

and for someone able to play we set

Node combination is simply defined as matrix multiplication, and checking m_0, 3 in the root for the segment tree for skill value v tells us the number of teams that may be formed with players having skill v. To handle queries we just need to change the leaf associated with the enabled/disabled player, and update the total according to how the root of the modified tree changed.

The complexity is the same as the editorial, at the beginning, for handling queries, and O(N) memory for the segment trees.

В разборе С что значит:

"Можем построить граф, где вершины — это наша сумма."

I solved Div 2. C using very basic Kadane's algorithm. Used two arrays A1 and A2 to store the absolute difference of the adjacent elements of the actual sequence.Then changed the signs of values at odd positions in A1 and values at even postions in A2. Then used Kadane's algorithm to calculate the maximum subarray sum in both the sequences. The maximum of the two is the answer. Here is my solution. http://ideone.com/K75Mu4

For Div2 E, Div1 C: "Obviously, we'll have at most 1001 different concentrations, so there are at most 1001 edges from each vertex.". I coudn't get it, can someone prove or explain this statement?

it is first time i met prob with number and graph combined !! Thanks for nice prob !

It would be better if div-2 problem C was problem B. Problem B was not that hard but problem C was far more easy. Almost everyone knows how to find the maximum subarray sum using kadane's algorithm.

In Div1 B , I inserted all the nodes present in the edges in set to find the total number of nodes visited every time . And , for this my solution got TLE . I know I could do it in linear time , but I dont understand why it should get TLE . Link below .

http://mirror.codeforces.com/contest/788/submission/25916059

In problem C, why is "We need at most 1000 vertexes to each side (from -1000 to 1000)" true? Can't the value intermediately overflow 1000 and then decrease to n

div2 C why do we have to make two arrays with +,-. Could not find logical error in my code.where am i wrong?

my code

Isn't this submission O(10^9)? Why does it pass?

div2 B (789B - Masha and geometric depression)
I'm failing to understand the reasoning behind this in the tutorial:

|b1| > l — answer is 0.

Specifically, I think that test 45 (25944979) contradicts the problem description.

b1=2, q=0, l=1, m=1, a1=2.
Participant's output: inf
Jury's answer: 0

My reasoning:

• 2 is a "bad" number, so we skip b1 and move to b2.
• 0 is not bad and |0| < l, so we write b2 to the board
• 0 is not bad and |0| < l, so we write b3 to the board
• ...

I appeal to the problem description:

Masha writes [terms onto the board] while condition |bi| ≤ l is [satisfied]. There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

So, we must skip b1 and move to b2 regardless of |b1| value if b1 is "bad".
What am I missing?

In Div1 C, how we can make the graph ? I think there can be n^2 vertices and n edges connected to every vertex. I think it needs n^3 memory.

Hi, could someone please give a more detailed explanation of the idea behind Div2D/Div1B? Especialy the translation to finding a Euler path and regular edges. Also what does we "split into 2" mean?

I would be very grateful since i can solve Div2 A,B,C in contests for some time now, but can never come to understand D.

In Div2 D, for adding the number of pairs with loops, should we not be adding loop.(m-1) instead of loop.(n-1)? For each loop we select we pair it with any of the (m-1) edges, isn't it?

In 788B

Regular(not loops) edges that are not adjacent — graph has four vertexes with odd degree, so Euler path doesn't exist.

if two regular edges are not adjacent, our graph can also have two vertexes with odd degree. how to prove the answer is right?

Can anyone please tell what difference would it make if multiple edges are allowed in problem 789 D / 788 B ?

For Div2 E, why does it reduce to subset sum = 0 ? Aren't we allowed to choose any no of liters of a particular concentration? If a1,a2,...,am are the distinct given concentrations, and x1,x2,...xm denote the amount in liters taken from each type. We want to minimize x1+x2+...+xm

sigma(xi*ai) = n*(x1+x2+....+xm)

=> x1*(n-a1) + x2*(n-a2) + ... + xm*(n-am) = 0

What i dont understand is that why xi = 0 or 1 ?

I can't understand Div2 E, why 1000 vertexes to each side (from -1000 to 1000) ??

I understand why the answer must be bound under 1000 but why do there can be atmost 2001*(min(k,1001)) iterations that will run????..wont it be greater than it??..I mean its gonna check for all posiible combinations for which a particular number 'x' comes through sum of different numbers if we keep the structure of the graph in mind...

hi

in problem div2 C i use to <bits/stdc++.h> library but i got wrong answer and bellow error on test 4

Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\46035c1543108537f31faf5ce95ef250\check-81db4cd701e94f7f6059055741b7386c\run\output.fd0138e687.txt.

when i changed library into iostream i got accepted

can someone explain why? and when i can use from <bits/stdc++.h> library?

Can someone explain how build final graph in div1C?

i think test case 18 for D has some bug... someone please confirm