CodeCracker 2k18 editorials

Правка en2, от pandusonu, 2018-03-20 06:52:59

Thank you for everyone who participated in the contest :)

The winners of the contest are: 1. @SoMuchDrama 2. @achaitanyasai

Link to problems Qs: questions

Shreyy’s Birthday Gift

There are many ways to solve this problem. Given the solutions submitted by the users, here is an alternate way to think of the problem: For n sized array, the number of modulo operations are n - 1. This implies that you have to divide n - 1 additive and n - 1 negative signs among n items, with each item getting at most of 2 signs, and at least 1 sign each.

Now, we just sort the array, and if n is even, we can divide the array into [1: n / 2] and [n / 2 + 1: n] In the first partition, all elements get 2 positive signs each except the last element which gets 1 positive sign. In the second partition, the first element gets a single negative sign, whereas the rest get 2 negative signs

Aliens

A simple approach is to hash the possible distances. Then we could check each enemy base in O(N) time. However, this would yield an O(N2) algorithm which is too slow.

Let’s restate the problem and use binary vectors. S[i] is 1 if grenade can reach distance i and H[i] is 1 if there is an enemy base at distance i We want to calculate Possible[i] = S[k]∗S[ik] The Possible vector is actually the discrete convolution of S with itself. We can calculate it the same way we multiply polynomials using a discrete Fast Fourier Transform (FFT).

The discrete FFT of n values can be calculated in O(nlogn).After calculating the Possible vector, we just need to check in how many distances i, Possible[i] > 0 and H[i] = 1 Recall that the distances are up to 200000. Say the maximum distance is D, then the time complexity of this approach is O(N + M + DlogD) which will pass the time limits.

Mario and Browser

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en17 Английский pandusonu 2018-03-20 15:39:32 94
en16 Английский pandusonu 2018-03-20 15:20:31 0 (published)
en15 Английский pandusonu 2018-03-20 15:19:56 37
en14 Английский pandusonu 2018-03-20 12:01:27 212
en13 Английский pandusonu 2018-03-20 08:07:57 93
en12 Английский pandusonu 2018-03-20 08:02:20 2 Tiny change: '] = S[k] ∗ S[i − k]$' -> '] = S[k] * S[i − k]$'
en11 Английский pandusonu 2018-03-20 08:01:38 10 Tiny change: ' problems Qs: [Questi' -> ' problems Statements: [Questi'
en10 Английский pandusonu 2018-03-20 07:52:53 334
en9 Английский pandusonu 2018-03-20 07:48:36 143
en8 Английский pandusonu 2018-03-20 07:44:29 111
en7 Английский pandusonu 2018-03-20 07:32:31 638
en6 Английский pandusonu 2018-03-20 07:11:56 2 Tiny change: 'ib(2),……. $(i-fib(x))>=0 }$\n\nFor' -> 'ib(2),……. (i-fib(x))>=0) }$\n\nFor'
en5 Английский pandusonu 2018-03-20 07:11:18 228
en4 Английский pandusonu 2018-03-20 07:08:15 826
en3 Английский pandusonu 2018-03-20 06:57:49 108
en2 Английский pandusonu 2018-03-20 06:52:59 1480
en1 Английский pandusonu 2018-03-20 06:44:54 526 Initial revision (saved to drafts)