Unoffcial editorials OCT17

A Balanced Contest

It is the easiest question in the contest. You just have to count the number of cakewalk problems and the number of hard problem .

So let hcnt be count of hard problems and ccnt be the count of cakewalk problems . So for each input denoting the participants solving the problem :

if(input_number>=p/2)

ccnt++;

if(input_number<=p/10)

hcnt++;

and then

if(ccnt==1 && hcnt==2)

printf("Yes");

else

printf("No");

Link to my solution : https://www.codechef.com/viewsolution/15624434

Max Mex

I this problem you have to find the minimum element in the complement set of the set we are given with respect to a universal set of whole numbers .

The additional task is to find the maximum of such value that are possible after adding some k numbers to the set.

For example if the set is {1,2,3}.

The MEX is 0

Let k=1

We have to find the maximum value of MEX.
So we can add 0 to the set such that the value of MEX becomes 4 which is the largest possible with this set and k .

So what we can do is to fill the holes (i.e. the numbers which are not there in the set) so that when no holes can be filled , the recent hole will be our mex because if then we make the complement of the number , it will be the least value and hence the MEX.

The approach that I used is to map the numbers of the set that we are given using hash table .

(1) First of all , I found the maximum value in the set and side by side kept on mapping all the input values to 1 .

(2) Then I ran a loop from i=0 to i<=max.

(3) In the loop , I we have to check if the number is present in the set . If it is not present and k>0 (We still have number left to fill) , we do k-- signifying that we have added the element .

(4) Meanwhile if k becomes 0 in the loop , we break from the loop , and the last element which was not present is our answer. We signify this by making flag=1;

(5) If outside the loop , flag==0 , our answer will be

ans=max+k+1;

where the k value is the value which remains after the loop. It is because , the remaining k value will fill all the holes in the set continuously upto mx + k . Then we add 1 to get first hole that is left now .

Link to my Solution : https://www.codechef.com/viewsolution/15625843

Counter Test For CHEFSUM

I request you to first solve the CHEFSUM problem .The answer is the minimum value in the array .

In this problem we have to somehow overflow the value of integer variable . The unsigned int data type has a size of 4 bytes or 32 bit . Its range is from 0 to 2^32 -1 i.e.0 to 4294967295 . Its solution can highly vary from person to person .

One observation that has to be made in this question is to look into constraints given in the subtasks. There , the range of n is

99991 <= n <=100000

**So actually we have to devise the test cases for only 10 values of n . ** And also for full score,

1 ≤ ai ≤ 10^5

So what I did was to divide the maximum value of int by n and print it n number of times with minor adjustment to satisfy the constraints on ai.

**Link : ** https://www.codechef.com/viewsolution/15649810

Chef and a great voluntary Program

In this problem , we have to divide the groups of apples and bananas / individual apples and bananas in such a way that no more than x number of apples are there copnsecutively and no more than y number of bananas are there consecutively.

If the group of one type still remain even after mixing of groups , we can break the previous groups that have their condition satisfied to be used as new separators for the other group .

If one type of group still are separated enough , we have to pace kiwis in between .

(1) So first , we have to determine the number of groups of bananas and apples . For that , we first have to count the number of apples and bananas(i.e. a and b) in the string.

The groups of a are :

//cnta is the count of number of apples

if(cnta%x==0)

ga=cnta/x;

else

ga=cnta/x+1;

Similarly goes for b.

Then we go on placing the fruit having less number of groups as the separator.

Until the number of groups of both the fruits are same , we keep on placing single character of the separator fruit between the groups of fruit having higher number of groups and keep on decreasing the number of each type of fruit.We calculate the number of groups in each loop after placing the characetrs of both type.

If then aslo , characters remain, we print them in groups alternatively .

If then also remains some group , we print each group followed by a star .

Link to my solution : https://www.codechef.com/viewsolution/15679608

Chef and Cycled Cycles

At first site , the problem looks like that of a typical graph problem but with careful observation , one can see that the problem is way simpler .

(1) For each cycle , determine the shortest path that one has to travel to cross that cycle . For it use the points , one in which the previous cycle connects to and the other in which this cycle connects tothe next cycle . It can have only two paths , one clockwise and one counter clockwise and we have to take the minimum path .

You can save this in an array with its ith element is the summation of paths upto that cycle plus it own path inside the cycle .This way you will save on calculation again and again .

(2) You can also make an array which sums up the path of intermediate connections between the cycles.

(3) Now for each query , do the following :

(i) Calculate the shortest path between cycles , not considering the cycles which are the end points.

(ii) In the first cycle c1, calculate the shortest path from v1 , to the point which connect it to other cycle. Similarly calculate the path from the v2 in c2 to the point which connects it to previous cycle .

There are two cases of above step , one path can be clockwise and other anti-clockwise . You have to take the minimum of it .

**Link : ** https://www.codechef.com/viewsolution/15847886

6 Likes

It is my first time posting these editorials . Feel free to suggest better methods and suggestions are always welcome.

bro upload editorials for rest of the questions too
you are very helpful please upload these unofficial editorials after every contest

Thanks man . It means a lot .

Unfortunately I was not able to do other problems . So these are the only ones I can give for now.

Hey trashmaster,Can u please explain your solution for “Counter Test For CHEFSUM”.

There can be multiple solutions to this problem . What I did was , after careful observation , I noticed that if we divide maximum value of unsigned int by n , we get a number less than 100000 . So I print the number (maximum value of unsigned int)/n , n times .

But then I noticed , that for one test case , it was giving a value greater than 10^5 , so I changed it a bit and voila , it was accepted .

Really nice bro!!

You could have provided a bit moe of explanation and examples for chef and cycled cyles…

Even then, they were good :slight_smile:

Thanks !

I will surely try to be more precise and give a better explanation from next time.

Awesome editorials bro…really helpful…
could you please help me with this “Counter Test for Chefsum” solution-
https://www.codechef.com/viewsolution/15891840
I don’t know why i am getting wrong answer…

Have a look at my solution . I will advice you to equally distribute the number .

thanks…it worked…

I made the mistake in Chef and Cycled Cycles to solve going in only one direction, but a nice trick to go backwards is to just go forward from the end to the start

Actually I was thinking the same in the beginning . But it was making the code complex unnecessarily . So after some thought process , I decided to go in clockwise only , no matter whether I started from c1 or c2.

hey trashmaster these editorial are awesome . can u make codechef long contest editorial in video format in hindi on youtube ?