Analysis : Codechef Starters 99 Division 3

  

 Starters 99 Division 3 (Rated)

 

Mindlessly strolling through the question set while watching THIS movie. Its getting cold in haldwani. Possibly the Starters 99 was a fun distraction. The movie was good too. 😍😎

 1. Endless Appetizers

Formula = ceil((LB_sticks + extra_sticks)/num_of_sticks_in_singlePlate) 

 2. Card Swipe

This was pretty simple ones. Taking into account the insertion of duplicate elements could easily solve this. For this, using a set would be the best approach.

 

for i in data:

    if i not in checker_set :

        checker_set.add(i)

    else:

        checker_set.remove(i)

       

    max_so_far = len(checker_set)

    if max_so_far > answer:    

        answer = max_so_far

 3. Exclusion-Inclusion

Simple but tricky one. The only trick is to take the sum of the array and sort it. Once you have done that, keep subtracting the elements from array with the sum and print the answer.

 4. Segment Three

Possibly the most challenging question of the contest. It was a Dynamic programming problem.

The problem can be simply divided into 9 different finite states, which is simply following state (0,0), (0,1), (1,0), (1,1), (2, 0), (0, 2), (2,1), (1,2), (2,2). 

For each state we basically check whether adding that state (a, b) to (A[0],A[1]) of the Array will make it divisible by 3. Taking the (a+A[0])%3 say A_2 and (b+A[1])%3 say A_1 of first 2 elements as anchor point, we loop through the array and select the Ai element and check minimum number of additions required to make changes in A2 such that (A0, A1, A2) gets divisible by 3. Similarly for (A1, A2, A3), (A2, A3, A4).

Repeat this for remaining 8 states. The State with the minimum number of changes is the answer. 

 

for a, b in ((0,0), (0,1), (1,0), (1,1), (2, 0), (0, 2), (2,1), (1,2), (2,2)):

    suma = a + b

    A_2, A_1 = (A[0] + a)%3, (A[1] + b)%3

    for c in A[2:]:

       inc = (3 - (A_2 + A_1 + c)%3)%3

       suma += inc

       A_2, A_1 = A_1, (c + inc)%3

       ans = min(ans, suma)

Hope you had fun reading the blog. Thank you. Have a great one. 💓

 

Read More