Какая будет разбалловка?

Все, вижу...

When you decide which type of score distribution to choose, what do you base your decision on?

Популярный будет контест — за 40 минут — x2122 зарегистрированных!

Всем счастья ^^

Надеюсь задачи будут решаемы для меня ! Всем удачи)

Немного надоели радостные посты о всеобщем счастье на контесте, созданные для прокачки вклада. Не по понятиям поступаете, господа.

20 деревьев отрезков авторское решение или мне надо отдохнуть? (Задача D) UPD Даже прошло...

Растолкуйте остолопке, отчего в задаче В div2 -1 -1 — это правильное решение, а 60 60 — нет? Ведь сдвиг и так и так получится 0.

В Е была 2-SAT?

У меня одного были проблемы с претестом №11 в B?

First off, great problem set. Seems like many people managed to solve E (grats), I would like to know the trick!

I reduced the problem to finding a sequence of nodes (with repetition allowed) that by using XOR, and including the initial state, would yield only ones. If i'm on the right track you probably understand what I mean, if im not please ignore. Anyway, can somebody hint for the solution?

Как E решалась.Скажите пожалуйста.

Lame...I totally ignored the alert that an all white fractal and an all black fractal are valid fractals.

И все-таки, надо признать, авторы жестко ошиблись с разбалловкой и сложностью задач. Самая жирная Е решается в разы больше, чем С... Мир встал с ног на голову

Привет 43 тест! :)

Regarding the rule: "_He divides the sheet into four identical squares. A part of them is painted black according to the fractal pattern._", I think the example for C is not illustrative enough...

I thought "a part of them" means one of the 4 parts... And it takes me quite a while to understand why a "2x2 black" square is a valid fractal pattern.

В задаче С есть анти-хэш тэсты, или у меня кривые руки?

I am bit confused about sample given for Problem E(probably I am misreading problem).

example had

4 4 1 2 1 2 4 0 4 3 1 3 2 0

if road build go to first city 2 and then to 1, it would asphalt all roads?? after it go to city 2=> 1st road would unasphalt and 2nd/4th road would asphalted after he go to city 1=> 1st road would be asphalted

hence after 2 step it should get asphalted, can someone help me where I am misinterpreting the problem

I hope editorial will be available soon.

научите писать дфс, а то Е упала потому что написал

for (int i = 0; i < n; ++i)
    if (!use[i]) dfs(0);

My solution to task E First we notice that doing the operation (asphalting) on town X will XOR all the roads coming out of it, so it's obvious that you don't need to do the operation (asphalting) on the same town more than once. (XOR-ing a road 2 times, is the same as XOR-ing it 0 times) So as we know that, we know for every town, we either asphalted the roads coming out of it once, or we didn't at all. Now let's take a set of connected towns (you can reach each town in the set from each town in the set) , Now if we know for one town if we asphalted it, then we can find out if we asphalted for each of the towns in the set. Example : We take a random town in the set and say we didn't asphalt it, we check every town he is connected to with a road that is not asphalted, obviously the other town must be asphalted if we want the road to ever be asphalted, and we check every town he is connected to with a road that is asphalted, obviously the other town shouldn't be asphalted. This way we repeat for every new town we find and because it's connected graph, we will find out for all of them. Now if we get for a town, that it should be asphalted and at the same time not asphalted, we got impossible situation. Then we repeat the whole thing but saying we asphalted the random town we took. So if both cases return impossible, we print impossible, in other case , we stop looking at this connected graph and say we managed to do it , then we proceed and take another connected set, doing the exactly same thing. If we end up doing all the sets without problems, we print the towns we asphalted from (we memorize them). Since we said a town can be asphalted at most once, the limit, to asphalt at most n towns, doesn't really do anything (asphalting all towns will result in n asphalts).

Sorry if i didn't explain it quite well, just thought i'd share my idea with you, it worked and i got 54th place :)

Nice problemset, but one question. How did you define a "fractal pattern"? naturally thinking, why a pattern with 0 or 4 blocks in black grids is vaild, with exactly 1 also works, but doesn't for exactly 3 black grids? It has just gone beyond my imagination..

Can you update the rating please so I can sleep well ?

контест два два восем рулит.два два восем есле в архиве

Мне в Е на ум сразу только кинулась система линейных уравнений. Там вроде все просто — обычный Гаусс по модулю 2. У меня зашло. По времени — отлично.

Did anybody model the problem E with 2-SAT my solution failed in test case 43

if c == 0 then either of a or b can be taken but not both so i did this: (a or b) and (!a or !b)

if c == 1 I initially did (!a or b) and (a or !b) and (a or b)

It gave Impossible in first case

Why it did not work?

For those who are seeking for non dfs/2SAT solutions in E:

Actually it is a system of Boolean equations with 2 variables each, the condition is to set the edge connecting i and j to be colored, with given color condition k (either 0 or 1). So we get for each edge, an equation like

and can be rewritten as

You will get m equations for n variables. Note that there is no unique solution (if it exists) since there are no two different equations with the same pair of variables with different coefficients on LHS (it's just 0 or 1 anyway). It means that if solutions exists, there is at least one slack variable, and the solution size is always less than n.

Solving the equation can be done using Gaussian Elimination in O(mn²) time. A faster approach is to utilize the property that each equation has exactly two variables. when doing elimination, the row being update always contains exactly two variables as well. Suppose we pick the equation

with i < j. Now we want to eliminate

where i < k. WLOG assume j < k. You get

Steps to consider.

(1) We saw an equation being set with (x_j, x_k) such that

(i) if w = w', this is a redundant equation, we forget it and process next edge.

(ii) otherwise, contradiction occurs, no solution.

(2) If we haven't seen such pair (x_j, x_k), and there is no equation with pairs (x_j, x_p) with j < p, we set up this new equation (that x_j relies on x_k for backward substitution).

(3) If we have an equation with pairs (x_j, x_p) with j < p and p ≠ k, we eliminate the obtained equation with it to get a new one with pair (x_p, x_k) (assume p < k). Then go back to step (1).

Hence we see that step (1) to step (3) would go at most n times, so we obtain at most n - 1 equations after processing m edges, and do backward substitutions. It takes O(mn) time.

Can anyone help me find the wrong in my submission?Because it's right when running on my own computer.thx.2261761

Why hasn't the editorial yet been published???