Ты так говоришь только потому, что сам синий :3

А что за баг со сдачей задач?

• only "thanks all" writes
• and 15 Like :D

В этом есть что-то плохое?

Ну и что? Подумаешь. Может зеленый лучше приготовит контест чем фиолетовый. Главное что бы задачи были интересные)

Змей или василиск?

He's one the most popular heroes in Iran National Olympiad. I guess he's Shaazzz's brother, who is one the most popular and powerful heroes of Iran too :D.

It's somehow like "fool" in Persian, but in a funny way.

the quality of the contest cannot depend on the rating of the designer however if you remind MR HolkinPV he producted many constests that in that time his rate was under 1900!

выводи "GANSTA SHEET!"

Такое ощущение, что чем меньше у человека рейтинг, тем сложнее в среднем получаются задачи.

Самый лёгкий контест ведь Эксперт готовил:)))

И как решать E? Расскажите этот п...ц :)

Похоже на то, что константа большая. Код можно оптимизировать — например, этот перебор ~~~~~ for (int i = 0; i < n; i++) for (int j = 0; j < sz(g[i]); j++) ~~~~~ требует порядка 2*n времени, что в двое больше чем нужно.

First fix, the numbers of books with thickness 1 and 2. Then you can find the minimum width of the books at the top greedily.

I also used a DP solution, but since the constraints were so small, I used dp[N][MAX_WIDTH][MAX_WIDTH] array and did a knapsack on it for each value from i = 1 to (MAX_WIDTH — 1). MAX_WIDTH is the sum of width of all the books. If any of the values i were sufficient to satisfy all the constraints I considered that the minimum thickness solution. If not, I needed MAX_WIDTH. Could have used binary search to determine i as well if the constraints were a bit higher but didn't need to in this particular case. Here is my code. 3486021

You can do a greedy brute-force. Divide them into 2 arrays(one for thickness 1 and the other for thickness 2). Sort the arrays by width(biggest first) and than for every number of elements of array1 check every number of elements of array2(checking all combinations). And since they are sorted by width, it works.

See my solution: 3486814

It's not a real name in Farsi, it is sort of nickname for fool and stupid person :)

Because there are 6720 ways.. Try to understand smaller tests.

1 2 3 4 5 6 7 8 9 10 11

0 0 0 1 0 0 0 1 0 0 0

answer=C(9,3) x C(6,3) x C(3,3) x (2^2)

maybe this helps you

-

Мы всегда можем ничего не сделать одним способом, другого не бывает :)

Если все включено ответ 1. Так вроде всегда.

the idea is the following

lets take an example (* denotes lighted bulb)

1 2 3 * 4 5 6 7 * 8 9 10

you can divide this into sub problems. The idea here is to find the number of ways to switch on bulbs on both side of a * and merge the result. One more thing, for any sub problem like * 1 2 .. n *, the answer will be 2^(n-1) (i leave that to you).

Now, traversing the *s

1 2 3 * 4 5 6 7 * 8 9 10

for the first * , there are 3 bulbs And when treated independently, there is only one way to switch them all on. But for 4 5 6 7, the number of ways to switch them on when treated alone is 2^3 = 8. How do we merge this result? Notice that any solution for the sub problem {1 2 3 * 4 5 6 7 *} will be composed of a possible solution of {1 2 3} and a possible solution of {4 5 6 7}. To put it simply, if a solution is (3,2,1) and another (4,5,6,7), the final solution will be a tuple made from these two solutions with their ordering preserved (for two tuples of size n and m, there are C(n+m, n) final solutions). The ans = 1*2^3*C(4+3,3)

for the second '*'

we have the number of solution for the previous 7 bulbs, and there is only 1 way to switch on {8 9 10}. Thus

ans = ans*1*C(7+3, 3)

Why ..?

C++ is magic language. You should never try to hack C++ codes.

i also tried for a code to be RTE, and i was unsuccessful.

the things i learned is, from next time i won't try to hack any other code for RTE. :P

Data declared in the data segment (out of a function in C/C++) is page-aligned and initialized to 0. There is an offset before and after the array that is safe to work. The offset depends on the size of the array. It is a bad programming practice but most of the time works. See my B's solution: 3489441 I intentionally index -1 several times.

You should really read these two thread:

http://stackoverflow.com/questions/3473675/negative-array-indexes-in-c

http://stackoverflow.com/questions/671703/array-index-out-of-bound-in-c

I guess, GNU C++ compiler isn't so sensitive to RTE

Объяснить не могу, зато могу дать тест:

3
1 1
2 3
2 4

"Checkered" means "painted like a checkerboard".

That solution does the following: initially tries to put vertically some books with thickness equal to 1 AND some books with total thickness equal to 2, then tries to put horizontally all the books with thickness equal to 2 and some books with thickness equal to 1, then, finally, tries to put horizontally all the books with thickness equal to 1 and some books with thickness equal to 2.

An alternative solution with dynamic programming: Dp[i][j][k] — 1 / 0 if you can obtain from the first i books a total thickness of the vertical books equal to j and a total widthness of the horizontal books equal to k. When you want to add a new book, you can put it vertically or horizontally. In the end, you have to find the smallest i with at least one value equal to 1 from Dp[N][i][j], j <= i.

I think this probblem can use One-zero backpack. http://mirror.codeforces.com/contest/294/submission/3485742

Outdoors for example.

http://mirror.codeforces.com/contest/294/standings

Да в блоге и разбор должен появляться, но, похоже, в этот раз и то, и то съел Шаасс.