ByteRace 2k19!! Results and Editorials

Revision en3, by Nightmare05, 2019-11-16 17:05:25

Hi guys,

I would like to thank all participants for making this event a grand success and specially thank ck98, darklight13, LightYear, kunj017, scameeer, leviOosa and hackcyborg for the problem setting and testing efforts and specially for actively managing the queries during contest!!

So, without wasting more time I'd like to congratulate our winners:

  1. nuip

  2. Amoo_Safar

  3. Prashant Shishodia

  4. kimden

  5. scopeInfinity

Based on the leaderboards following people have qualified for prizes:

Overall top 3:

  1. nuip

  2. Amoo_Safar

  3. fugazi

Top 5 Indians:

  1. fugazi

  2. scopeInfinity

  3. cerberus97

  4. _shanky

  5. hitman623

Top 2 from IIT Patna(presently studying):

  1. intruder_p

  2. DeepThought42

Editorals!

Is It Some Space Cakewalk?

The main idea for problem was pigeon-hole principle i.e in worst case we pick all the different type of cakes first and then any additional cake would make a pair repeat. So the answer to the problem was number of different types of cake in the list + 1.

Time Complexity O(n+max(T)).

Author Solution

Kunj Destroys Asteroids in 13th Dimension

This problem can be solved in many ways like prefix sum , window sliding or even binary search.

I will discuss one with partial sum. The equation of the rhombus can be represented by |x| + |y| = X. Thus we only need the manhattan distance of the points. We make a prefix array that will store number of points less than or equal to manhattan distance i for each i. We calculate the points lying between X and X+K using prefix sum for each X where X is prime which can be computed by sieve. For each X the number of points lying between the rhombi would be pre[X+k] — pre[X-1]. Maximum of all such iterations will the answer.

Author Solution

1-2-3 Subsequence

The naive solution of iterating from l to r for each query will give TLE. Thus we use segment tree. At each node in the segment tree we store 6 values. 1. Length of maximum subsequnce strating from 1 and containing only 1. 2. Length of maximum subsequnce strating from 2 and containing only 2. 3. Length of maximum subsequnce strating from 3 and containing only 3. 4. Length of maximum subsequnce strating from 1 and containing only 1 and 2. 5. Length of maximum subsequnce strating from 2 and containing only 2 and 3. 6. Length of maximum subsequnce strating from 1 and containing only 1, 2 and 3. Now when building the segment tree you can maximize these values at each node to get the answer. At each node combine when with possible combinations like 1+(2-3), (1-2)+3, 1+(1-2), (1), (2), (3), (1-3)+3, 1+(1-3). The answer to each query will be the maximum of the above values. This can be better understood in editorial code. A much clean solution can be: https://codeforces.net/blog/entry/71357?#comment-558146 Thanks to fugazi

Universe is random, but is it?

Divide the Country

Will You Win The Prize?

The question is given as if it has to be solved online, but actually it is an offline question. Take all the characters given in all queries in sequence to make a string (S1). The given string is named as (S). Make string (T)=S1+#+S. Now apply “KMP” on this string (T). In the array obtained by KMP take the answer from (n+1)th index to (2n)th index. This is our required l(i). So, ans(i)=l(i)*2^i. It’s easy to calculate the binary representation of ∑(i=1 to i=n) ans(i). Refer to the solution code for better understanding.

Yet Another Permutation Array!

Binary Matching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Nightmare05 2019-11-16 22:53:41 3 Tiny change: 'ions will the answe' -> 'ions will be the answe'
en6 English Nightmare05 2019-11-16 22:38:32 0 (published)
en5 English Nightmare05 2019-11-16 22:35:51 78 (saved to drafts)
en4 English Nightmare05 2019-11-16 22:31:06 3265 Tiny change: '18df/)\n\n#### **Problem ' -> '18df/)\n\n**Problem ' (published)
en3 English Nightmare05 2019-11-16 17:05:25 3413
en2 English Nightmare05 2019-11-16 16:53:39 56 Tiny change: 'x(T)).\n\n`Author Solution`\n\n[`Auth' -> 'x(T)).\n\n[`Auth'
en1 English Nightmare05 2019-11-16 16:47:54 1700 Initial revision (saved to drafts)