Introduction

Few days back, I participitated in UWCOI 2021 contest on CodeChef. I am able to do only first 3 problems during the contest and upsolved 2 problems later on .

Now lets jump directly to Explations/Solutions

Solutions

Problem - Hidden Numbers

Problem Link

We can just output A 1

code

cin>>A; cout<<A<<" "<<1<<"\n";

Problem - Array Swaps

Problem Link

In optimal case :-

'A' array will be sorted in ascending,

and

B will be broken into 2 pieces, 
- piece 1 will contain all element smaller than A[0] in increasing  order  and
- piece 2 willl contain all element greater than or equal to A[0] in increasing order

So answer will be sizeof(piece1)*N

code

CodeChef Solution Link

Problem - Organisation

Problem Link

Firstly, I thoght if ducks of any color, let N1 , is >=k then its always better to fill $ N1/K $ boxes full of K ducks of one color. This claim is false as

For ex:

N = 2, K = 5
ducks :- 7 1 2

According to the above approach, Box will be contain 5 ducks of color 0 and we are left with 2 1 2 ducks of respective colors and 1 box.

But one possible ans is Box 1 : 0 4 1 1
Box 2 : 0 3 2 2

Now, Its clicked my mind it’s better to choose to color that has smallest number of ducks and combine that with the color with most number of ducks, This ways we will eleminate one color.

So we can first choose color with minimum number of ducks , Let it be N1 , and

untill N1 >= K but K ducks in one boxes

Now, We have N1 < K

Put all the ducks in a box along with ducks of color which has maximum number of ducks.

After 2nd step, maximum number of ducks may change so we need to maintain set to get color with maximum and minimum number of ducks

code

CodeChef Solution Link

Problem - Efficient Delivery

Problem Link

Here, We need to make one road highway to minimize time over whole journey.

For each road, We can maintain that if we make this road highway how much we will save and then we can choose the road with most saved time

———————————— Saved Time

——————————– D(x) - 8

——————————– D(x) - 4

——————————– D(x) - 0 – y1

——————————– D(x) - 0

——————————– D(x) - 0

——————————– D(x) - 0 – y2

——————————– D(x) - 4

——————————– D(x) - 8

where dx is abs(x1-x2)

Now, Its a better of implementation using segment or fenwick tree which I unfortunately couln’t do.

code

CodeChef Solution Link

Problem - Binary Puzzle

Problem Link

It’s clear we need to form cycles with number of set bits of every second number differing from each other.

  x1 ---> x2 ---> x3 ----> x4 ----
   ^                              '         
   '----------------------------- '      

   bitCount(x1)!=bitCount(x3)
   bitCount(x2)!=bitCount(x4)
   and so on

So I made a single cycle of the form

  b1 ---> b1 ---> b2 ----> b2  ----> b1 ----> b1 ----> b3 ----> b3
   ^                                                             '
   '-------------------------------------------------------------'      

   bi is any number with 'i' set bits

We need to take care of a case when last element has 1 bits.

Though, Editorial has a much better solution where after forming solution for K = 4 to 8 other solution can be exploited from there.

code

CodeChef Solution Link

Discussion

Problem A,B are quite simple

In problems like C, I guess it’s better to thing something like how could I get rid of one color. So, colors with less number of ducks create problems. we can club such a color with any other color. something like that

In problem like D, Its more of a inplementation problem. We can create ranges we in range

[L,R]    we need to add 4, 8, 12, ..., 4*(R-L+1)
we can add 1 at each index from L to R and -4*(R-L+1) at R+1 now PF[i] is the required value

In problem F, Always try to solve problem for smaller values and then use results to form solution for bigger constrainsts. In questions dealing with bits, its may be possible that smaller results get multiplied by something.