Intel Code Challenge Elimination Round (div.1 + div.2 combined) editorial

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
45:30:52
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя vepifanov

Intel Code Challenge Elimination Round (div.1 + div.2 combined) editorial

Автор vepifanov, 8 лет назад, По-русски

Tutorial is loading...

Разбор задач Intel Code Challenge Elimination Round (Div. 1 + Div. 2, combined)

vepifanov
8 лет назад
46

Комментарии (39)

Показать архивные | Написать комментарий?

vepifanov

8 лет назад, # |

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

→ Ответить

pavel.savchenkov

8 лет назад, # |

← Rev. 2 →

Альтернативное решение F (не использующее, что НОК(1, ..., 40) помещается в long long) за $\text{[math]}$ :

Для каждой позиции в массиве i найдем за K² ближайшую справа j, что система из двух таких уравнений не будет иметь решения, обозначим nxt_i = j - 1. Тогда нужно найти максимальный отрезок, где минимум не меньше правой границы. Это можно сделать за $\text{[math]}$ с помощью разделяй-и-властвуй.

UPD: как пишут ниже, можно посчитать nxt за $\text{[math]}$ и $\text{[math]}$ на предподсчет

→ Ответить

Nezzar

8 лет назад, # |

← Rev. 4 →

+51

(Probably) easier method for last part of F, as k ≤ 40 :(

While moving right pointers, we can put the system of questions apart and instead we want to check if there is a conflict between the newly added element and any old element we added before (i.e. those two cannot appear together in same time). Let k_i and p_i be the length of cycle of position of the element in cycle of element i. Two element i and j conflicts iff there exists integer d so that d divides both k_i and k_j and p_i mod d ≠ p_j mod d. As k_i is so small, we can just enum all possible d and record the only possible value p_d (if there are two values for same d at the same time, some pair of elements conflict and bad things happen). This algorithm is O(N log f(k)), where f(k) is the maximum number of factor of integers from 1 to k.

I wonder if you reduced the difficulty of this problem as if k ≤ 200000 this solution will TLE, and also your solution seems more beautiful than mine :(

→ Ответить

pavel.savchenkov

8 лет назад, # ^ |

I think this part could be done in $\text{[math]}$ since it is enough to check contradiction with k = p^a₁·...·p^a_m for each p^a_i.

→ Ответить

haleyk100198

8 лет назад, # ^ |

If k<=200000 wouldn't handling the lcm in the sparse table become a fierce task for the author's solution?

→ Ответить

ed1d1a8d

8 лет назад, # ^ |

How do you show that if there is not pairwise conflict, then there is a solution?

→ Ответить

gongy

8 лет назад, # ^ |

If k ≤ 200000 wouldn't the LCM get insanely big (requiring big int) for editorial solution? Is there a trick I'm missing for this?

→ Ответить

NirShalmon

8 лет назад, # |

← Rev. 2 →

Edit: I was wrong. In D you can have O(n*(logn+log10^9)) if you keep a priority queue and a hash set of the same values: In each iteration get the max Y_i from the priority queue in O(log(n)) and check for the min value one by one from the hash set in O(log10^9)

→ Ответить

vasanthaganesh

8 лет назад, # |

Can someone please explain the C problem's solution, I don't understand the editorial's solution.

→ Ответить

Sandip_Jana

8 лет назад, # ^ |

← Rev. 3 →

The main idea behind the solution is actually we can process the queries offline . That is instead of traversing from i=1 to n and deleting every element we can actually revert the task and start from i=n to 1 and insert the element into its corresponding set. Everything is 1-indexed :)

Like the example n=4 , a={1,3,2,5} and p={3,4,1,2}; We have a boolean array ok to check if certain element is in set or not. Also keep a sum(long) array to keep track of sums of a set Initally all elements have parent[i]=i;

we start from i=4 and intially we have all sets as null so current ans=0 ( beacuse at last all elements are going to be deleted ). Now print 0 and let x=p[4] so update sum[x]=a[x] , as in our case a[2]=3 . we check both left and right of 'x' and we can see that neither 1 nor 3 is visited so simply find parent of 'x' which is 2 itself, so ans is updated to be max(0,s[parent[x]]); =>ans=3 and mark visited[2]=true; Next we have i=3 and p[3]=1. So we again check for left and right . In our case we only check for right side(1-indexing) so 2 is visited so we merge both set having element 2 and set having single elememt in 1 in such a manner so that the parent of the resulting set has suppose index as "parent_index" then sum[parent_index]=sum_of_all_elements_in_set; next we update our ans and as its either max sum from merging our current set or from previously merged sets and then we mark the element we processed as visited.

Continue for rest elements and Bamm its Accepted.

FatalEagle 's code in c++ : http://codeforces.com/contest/722/submission/210747661

my submission in Java : http://codeforces.com/contest/722/submission/21097209

→ Ответить

kraskevich

8 лет назад, # |

← Rev. 3 →

+40

There is a simple O(S * K)(where S is total length of all sequences) solution for F. The idea is as follows:

Let's assume that we have a fixed subsegment [L, R] of the given sequences and a fixed number x.
Let pos(x, i) be the position of the number x in the i-th sequence and len(i) be the length of the i-th sequence. Then the [L, R] segment will be filled with x at some point if and only if:
- Each sequence contains x
- for all L <= i < j <= R, (pos(x, i) - pos(x, j)) mod gcd(len(i), len(j)) == 0
The first condition is trivial. The second one follows from the Chinese remainder theorem.
It implies that if len(i) == len(j) then pos(x, i) == pos(x, j). Thus we have at most one unique position of the element for all sequences of a specific length in a valid segment.

This criterion leads us to a solution that uses two pointers. Let's fix the value of the element. We need to keep track of the position of this element for each distinct length of a sequence. When we try to expand the segment by one to the right, we check that there is no conflict (by iterating over all distinct lengths (from 1 to K) and testing it with the position and length we're about to add) and add a new position and length if we can. When we move the left border, we just delete the corresponding position and length.

A few details: gcd's can be precomputed. We need to take into account only positions of those sequences that actually contain any fixed element.

Here is my code.

→ Ответить

TsReaper

8 лет назад, # ^ |

+10

"For all L <= i < j <= R, (pos(x, i) - pos(x, j)) mod gcd(len(i), len(j)) == 0"

Please explain this in more detail. I mean, if we know that

$\text{[math]}$

And for all 1 ≤ i < j ≤ 3, $\text{[math]}$ , how can we prove that there exists an x which satisfies all these three equation? Thank you.

→ Ответить

kraskevich

8 лет назад, # ^ |

← Rev. 2 →

This criterion clearly works for two equations (it follows from the fact that any linear combination of two integers with arbitrary integer coefficients is divisible by their gcd. Moreover, the gcd can be represented as a linear combination of these numbers). For three equation we can go like this:

Let's solve the first two. The solution is x = x0 (mod lcm(m1, m2)). Now let's show that for the system of two equations x = x0 (mod lcm(m1, m2)) and x = a3 (mod m3) the initial criterion holds true.
Let's consider an arbitrary prime p. Let p^a, p^b and p^c be the maximum powers of p that divide m1, m2 and m3 respectively. The initial criterion means that
x0 - a3 = 0 (mod p^min(a, c)) and x0 - a3 = 0 (mod p^min(b, c)). The power of p in lcm(m1, m2) is max(a, b). Thus, its power is min(max(a, b), c) in gcd(lcm(m1, m2), m3). The two equations above imply that
x0 - a3 = 0 (mod p^min(max(a, b), c)).
Now let's use the fact that if a | x, b | x, a and b are coprime then ab | x. It allows us to prove 2. for all powers of primes and conclude that it's true for
gcd(lcm(m1, m2), m3).

We've just shown that we can reduce the number of equations by one and the criterion stays true. If we have more than 3 equations, we can use induction.

→ Ответить

dreamplay

8 лет назад, # |

+29

Problem D: It should be choose maximum element that does not exist in Y from yi/2, ...., 1. Choosing minimum element gives WA on 1, 2, 9, 17.

→ Ответить

tenshi_kanade

8 лет назад, # ^ |

Yes, that's what I was thinking too. I tried solving it by choosing the minimum number and it doesn't pass pretest 3.

→ Ответить

wackloner

8 лет назад, # ^ |

Choosing minimum element also works longer :)

→ Ответить

vepifanov

8 лет назад, # ^ |

Thank you for pointing that, it should be fixed now.

→ Ответить

mrgrgr

8 лет назад, # |

Hey, i found another solution for problem C, i'm using segment tree, where the idea is just like the problem GSS or GSS3 in S.P.O.J, where each time an element is destroyed, i change its value to -1E14-10000000 because maximum total sum of an array couldn't be exceed 1E9*1E5=1E14.

The program might be complicated and hard to code, but hey, it's good to share an idea right :)

my code

GSS3 — spoj

→ Ответить

karansiwach360

8 лет назад, # |

← Rev. 2 →

-10

O(n) solution for problem C : http://codeforces.com/contest/722/submission/21107463

EDIT : Sorry, the link I posted was wrong. Now, it is correct.

→ Ответить

Chortos-2

8 лет назад, # ^ |

← Rev. 2 →

As far as I can tell, this uses a segment tree with one update and one get operation for each input number. This is O(n log n).

→ Ответить

fakeac

8 лет назад, # |

Can anyone explain solution to problem D ?

→ Ответить

Walid_Amin

8 лет назад, # |

+10

In problem F:

The editorial says "For each such subsegment we can find the solution of the corresponding system using O(1) time by solving a system consisting of two equations obtained from each of the halves of this subsegment. We can solve a system consisting of two equations using the Chinese remainder theorem.", So how can we solve Chinese remainder theorem in O(1) instead of O(logn)

I think this should add another log in sparse table complexity which makes complexity n*log^2(n)

→ Ответить

vepifanov

8 лет назад, # ^ |

Yes, you are right. But it will actually be log 10^16, since we need to find the inverse number (using f.e. extended gcd algorithm).

→ Ответить

gravity09

8 лет назад, # |

O(N) solution for problem C

C++ code : http://codeforces.com/contest/722/submission/21163148

→ Ответить

alooparatha

8 лет назад, # ^ |

Thanks a lot,

Could you briefly explain the below step of your code:

if(other_end[pos-1]!=0) { l = other_end[pos-1]; sum += seg[l]; } if(other_end[pos+1]!=0) { sum += seg[pos+1]; r = other_end[pos+1]; }

→ Ответить

gravity09

8 лет назад, # ^ |

← Rev. 3 →

seg[i] : Segment sum of the segment starting at index 'i'
other_end[i] : Starting/Ending index of the segment Ending/Starting at index 'i'
res : Maximum segment sum found until now
l : Starting index of segment of current element to be inserted
r : Ending index of segment of current element to be inserted
sum : Segment sum of the segment in which current element is inserted

While inserting the current element into the array at 'pos', we need to merge it with the neighboring segments if any.

Initially assume there are no segments adjacent to 'pos'.
  l = r = pos
  sum = A[pos]

if(any segment 'S' ending at 'pos-1' exists) 
   update 'l' with starting index of 'S'
   sum += segment sum of 'S'

if(any segment 'S' starting at 'pos+1' exists)
   sum += segment sum of 'S'
   update 'r' with ending index of 'S'
   
Update the segment sum of the new segment [l, r] in the 'seg' array
Update the Starting/Ending index of this segment in 'other_end' array
Check if 'sum' is greater than 'res' and update 'res' accordingly

→ Ответить

Ha_Nabil

7 лет назад, # ^ |

very very helpful , thank you

→ Ответить

mruczek

8 лет назад, # |

Can you give a proof that greedy algorithm for problem D is optimal?

→ Ответить

sur

8 лет назад, # ^ |

← Rev. 3 →

because any number can be DIRECTLY derived from only one number. This obviously means that set of numbers, that can be derived from number X consists of X itself and sum of sets that can be derived from 2*X and from 2*X+1

So:

If X can be derived from Y then SET_CAN_BE_DERIVED_FROM(Y) includes SET_CAN_BE_DERIVED_FROM(X)

else if Y can be derived from X then SET_CAN_BE_DERIVED_FROM(X) includes SET_CAN_BE_DERIVED_FROM(Y)

else SET_CAN_BE_DERIVED_FROM(X) and SET_CAN_BE_DERIVED_FROM(Y) DO NOT INTERSECT

→ Ответить

Flaker

8 лет назад, # |

Вопрос по задаче C:

Чтобы найти максимальный по включению подотрезок, содержащий это число, нам нужно найти ближайшее слева и справа зачеркнутое число. Это можно сделать за O(log n), использовав, например, set.

Поясните, как это сделать?

→ Ответить

Sammarize

8 лет назад, # ^ |

Я мог бы рассказать Вам про lower_bound и upper_bound, но лучше почитайте сами: http://www.cplusplus.com/reference/set/set/?kw=set

→ Ответить

Sammarize

8 лет назад, # |

+10

А есть доказательство этого решнения D? Почему если в какой-то момент мы поняли, что не можем заменить число y ни на какое другое, это означает, что мы не могли получить ответ каким-то другим образом?

→ Ответить

kraskevich

8 лет назад, # ^ |

← Rev. 3 →

Если не строго, то можно как-то так:

По условию, есть последовательность замен x-сов, такая, что вытоге получаются у-ки. Понятно, что можно, наоборот, идти от у к x.
Последовательность замен не играет роли (потому что каждый y заменяется независимо. Неважно, кого мы поделим на два первым, а кого последним. Важно лишь сколько раз).
Давайте считать, что мы явно строим эту последовательность замен. Будем всегда заменять наибольшее (если можно как-то иначе, то можно и так, ведь порядок делений не играет роли). При таком подходе, если мы не поделим наибольшее на два сейчас, мы этого не сделаем никогда (тогда ответ уже готов).
Ну а раз мы обязаны делить попалам наибольшее, то делить надо как можно меньше раз. Почему? Пусть поделить надо было больше раз. Мы можем просто сделать это потом (т.к. порядок операций, опять-таки, не важен).

→ Ответить

Sammarize

8 лет назад, # ^ |

Ну вот по поводу четвёртого пункта, пусть мы доделили x до x', но пусть нам, действительно, в конечном счёте необходимо поделить больше раз, чем мы поделили, и мы, действительно, можем поделить больше. Но необязательно мы можем снова сделать это потом, потому что, когда мы снова к нему вернёмся, все места, куда его можно передвинуть, уже будут заняты.

→ Ответить

Sammarize

8 лет назад, # ^ |

Вроде доказал.

Пусть max(Y) — максимальный элемент в множестве Y. Будем называть валидной заменой замену числа $\text{[math]}$ на натуральное число $\text{[math]}$ .

Алгоритм заключается в том, чтобы делать валидную замену x = max(Y) на максимальное возможное x', пока какая либо замена вообще возможна.

Докажем индукцией по n, что на любом множестве Y, таком, что max(Y) = n, алгоритм даст правильный ответ. База (n = 1) очевидна.

Индукционный переход. Рассмотрим $\text{[math]}$ . Если мы не можем сделать валидную замену x на что-нибудь, то x является искомым минимально возможным максимумом, поскольку, чтобы мы не делали, эта возможность более не появится. Таким образом, алгоритм, сделав 0 шагов, отработал правильно.

Пусть мы можем валидно заменить x на какие-то числа {x₁, x₂, ..., x_k}, причём x₁ > x₂ > ... > x_k. Пусть, сделав валидную замену x на x_i, мы получим множество Y_i. Алгоритм сделает замену x на x₁ и получит множество Y₁. Заметим, что из множества Y₁ можно валидными заменами получить остальные Y_i. Поэтому, если какой-то ответ можно получить из множества Y_i, то можно и из Y₁, то есть, минимальный ответ, который можно получить из множества Y, можно получить из множества Y₁. При этом, по индукционному предположению, на множестве Y₁ алгоритм отработает правильно. Следовательно, на множестве Y алгоритм тоже отработает правильно.