In problem D (n + (n - 1) - sum) / 2

I think it should be (n + (n - 1) - p) / 2

Pardon me for a stupid question.

In Div2B, the 13th test case is the following:

21 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 28 31 30 31

and correct output is "YES"

Doesn't this show two consecutive leap years? year 1: 31 28 31 30 31 30 31 31 30 31 30 31, next year: 31 28 31 30 31 ... this should not be possible right?

I solved C by just making two set and giving element to the smaller sum set in a reverse sorted order.I don't know why this works though. Can anyone help me with proving this method's correctness or tell where it could fail?

Can someone please explain solution to problem E. I don't understand the editorial.

A much easier solution for C : My solution link... 1. Just take the sum of the numbers= N*(N+1)/2.

1. If sum is even, then logically you can divide it into two equal halves. Keep giving the largest numbers possible till you form half of the sum.

3.If sum is odd, then logically one group will have one more sum than other group(g2). Let G2 sum be x. Keep giving the largest numbers possible to form x

Can someone explain D? Why we are adding those numbers etc..

难得有一次cf这么适合Chinese。。。

Easier way to solve problem C . The sum of the first N numbers is N * ( N + 1 ) / 2, let's call it tot.

If you have a number X less than or equal tot, it is possible to represent it as a sum of first N numbers. ( Iterate from N to 1, and subtract when possible), call that function represent(X). This is very well known.

Now .. if tot is even, we can obtain a difference of zero which we obtain by represent(tot/2). If tot is odd, we can obtain a difference of one which we obtain by represent(tot/2).

In even case, we get the best possible answer, in the odd case it's easy to see that the best we can obtain is a difference of one, and hence the algorithm is optimal.

Another way to solve F is keeping a treap for each character. However, it is overkill in my opinion. But if you have template ready to be copied and pasted, then it should be fastest solution.

Why crash?

http://mirror.codeforces.com/contest/899/submission/33344155

Существует другое решение задачи D, основанное на бинарном поиске, вот оно 33359972

Пусть нам необходимо посчитать количество различных пар чисел (a, b) из отрезка [1, n], таких что a < b и a + b = sum, где sum — некое заданное число. Найдем подотрезок [left, right] отрезка [1, n], все числа на котором будут иметь такую пару из этого отрезка.

Границы бинпоиска на left должны удовлетворять условию: для low не существует пары, для high существует. Тогда, после того, как будет выполнено условие high - low = 1, ответом для left будет high. Необходимо также проверить left = 1 перед бинпоиском.

Границы бинпоиска на right должны удовлетворять противоположному условию: для low существует пара, а для high- не существует. Тогда, после того, как будет выполнено условие high - low = 1, ответом для right будет low. Необходимо также проверить right = n перед бинпоиском.

Ответом для фиксированной суммы будет длина отрезка пополам: (right - left + 1) / 2

Тогда задача сводится к тому, чтобы сгенерировать наибольшее число, состоящее только из девяток и не превосходящее n. Пусть это число sum вида 9999...999. Затем посчитать количество пар по всем ответам для сумм вида digit·(sum + 1) + sum, где digit — разряд, дописываемый слева от числа sum (от 0 до 8).

Это решение имеет асимптотику O(log(n)) на ответ для одной суммы, а описанный подход может быть применен к другим задачам.

In problem D we can use a binary search for counting the number of pairs with a fixed amount on a interval: 33359972

Hey anyone got the solution of E by simulating the process using stacks, as i am getting stuck somewhere in this implementation.

Hi guys! Can anybody help me with problem F ?! I tried to solve it using a Multimap and a Fenwick Tree for building the initial positions but I'm getting "Wrong answer" on test 7 :(( Maybe I omit something. Thx in advance!

I have a doubt in Problem E.

While merging the two nodes, I can see how we are deleting the right and the left element from the second set(called segments), and then inserting the merged set. I don't understand, how can we perform the same operation in the first set(called lens) ?

Hey guys! Here are some of my thoughts on problem E this round, using priority queue and linked list! Have a glance! Use of Linked List and Priority Queue in CF Round 452, Problem E

In 899F, I didnt understand how would change the current l,r to positions in initial string using segment tree?

Hello guys, Happy Coming New Year to everyone! Can somebody help me, why do I keep getting TL7? Thanks in advance. Solution

Божественный разбор по D, в частности последний абзац — всё логично и всем сходу понятно.

Problem C

Can be solved greedily:

Start with putting N on the left pile and N - 1 on the right one. Then by placing N - 2 on the right and N - 3 on the left we got left - right == 0 and we reduce the problem to the one of the size N - 4.

At some point we end up with one of four possible problem sizes: 0, 1, 2, 3.

In the first case the difference was 0 and it's the best we can do.
In the second case we get 1 which is also the best solution because in than case N = 4k + 1 and the sum = N * (N + 1) / 2 = (4k + 1)(2k) is odd.
In the third case we end up with two numbers: 1 and 2, the best diff of 1 and 2 is 1 again and again it is optimal since N = 4k + 2 and sum = (2k)(4k + 3) is odd.
In the last case we have numbers 1, 2, and 3, we can place them so diff will be 0 which is optimal.

The code

import sys

n = int(sys.stdin.readline())

g = []
ls, rs = 0, 0

for i in xrange(n, 0, -1):
    if ls <= rs:
        g.append(i)
        ls += i
    else:
        rs += i

print abs(ls - rs)
print '{} {}'.format(len(g), ' '.join(map(str, g)))

This tutorial is not attached to the contest (I can see only Announcement link from there).

Problem F can also be done using sqrt decomposition.

Don't you think the editorials should be more elaborate(eg they can include one example).

Can anyone please explain why in problem D we are adding P/2 to the answer when P <= n+1 ?

I've been stuck for ages... anyone know what test #33 was on div2E? http://mirror.codeforces.com/contest/899/submission/33345602

My answer is 1 + the correct answer. :(

Another solution for F :

Store the positions of every character in an array of Sets (like the tutorial)...

Then after each query we can find the original position which has the Kth order after the previous updates by storing original positions in a Binary Search Tree, such as Treap which I used and delete them from the tree while applying the query. Therefore you can get the range query according to the original positions then you can remove positions from the corresponding set using lower_bound like the Tutorial..

(Sorry about my bad English)

in C for 5998 the answer should be 0

bcoz if n is even then we can always keep all the numbers whose %4 gives 1 or 0 in the first group, while others in the second group. This always give us an absolute difference of 0.

plzz correct me if I m wrong?

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

Жесть я даун

I think Binary Search tag is missing in Problem F.

Problem E is tagged with flows , i wonder how can we solve this using max flow ?