Codeforces Round #228 (Div. 2)

This is my first editorial for the Codeforces rounds...please share your views....as to how it can be improved...the coding round was held on 3rd February form 9:00 pm IST to 11:00 pm IST

The contest was held on codeforces and the dashboard can be found here . I will now be discussing the algorithm that i used for each question and how did I implement the solutions.

A.FOX AND NUMBER GAME.

The question was really easy.However i thought of a little complex solution for it and thus wasted a lot of time debugging.Got only 458 points for it and wasted 21 minutes on it.

Question: 

The question was we were given and array of n numbers.let is be a such that of 1<=a[i]<=100.Now we had an operation to chose any two indexes of the array i and j such that a[i]>a[j] and do the operation a[i]=a[i]-a[j].We can do as many operations on a single element as we want.Now we were supposed to output the least possible sum of all such elements after application of all the operation.It can be found here.

example:

input
3
2 4 6



output
6

Explanation: we chose 6 and do a[2]=6-4=2

and then we do a[1]=4-2=2

so array becomes 2 2 2

and sum is 6 and hence the answer.

Idea:

The idea was very simple.I needed to subtract the largest number smaller than the given number from the given number in the array until such a subtraction wasnt possible anymore.So what i did was maintained a frequency array to maintain the count of all the number occurring in the array and then started from the max number  and kept on subtracting from the largest number smaller than the number in the array until the subtraction was possible i.e a smaller number than the result of the operation existed in the array.

C++ code can be found here.

B.FOX AND CROSS

Again the question was really easy.And it took less time to be completed than the 1st ques itself.I submitted it in like 14 after i submitted A and got 860 points for it.

Question:

Fox Ciel has a board with n rows and n columns. So, the board consists of n × n cells. Each cell contains either a symbol '.', or a symbol '#'.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.

Sample test(s)

input

5
.#...
####.
.####
...#.
.....

output

YES

IDEA:

Idea was again very simple.I checked for every # in the array if it was the center of any cross as shown above in the picture.If it was i removed all the '#' of the cross and replaced it by '.'.Now i again checked the 2-d array to see if there were any '#' left.If there were the answer was 'NO' else it was 'YES'.

Code can be found here.

C.FOX AND BOX ACCUMULATION 

Question:

Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i-th box can hold at most xi boxes on its top (we'll call xi the strength of the box).

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more than xi boxes on the top of i-th box. What is the minimal number of piles she needs to construct?

Sample test(s)

input

3
0 0 10

output

2

In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.

IDEA:

I struggled with this problem a lot.Initially i tried to put the largest strength box at the bottom and then put a box with either equal strength or a lower strength on top of it and then count number of such piles.However it was failing on this case

3

0 0 0 1 1 1 2 2 10

it gave the output as 5.However the output for this will be 3.The stacks or piles for the given test can be arranged as:

pile 1: 10=>1=>0

pile 2: 2=>1=>0

pile 3: 2=>1=>0

I tried various variants of my algorithm but almost all of them failed on pretest cases 10 and 11.Then a friend of mine suggested what if we did the reverse.Chose the lowest strength box and then put the larger strength boxes below it.I tried implementing it and it worked.All the pretests passed.The solution passed system testing too.

So for the above test case this would work as follows:

PILE 1: we will 1st use box of strength 0.Now we have to use a box of strength 1 or greater than 1 as the size of the pile is 1.So we put box of strength 1 below the 1st box.After that applying the same logic till I cannot not put any more boxes below the last one I get my 1st pile as 

10=>2=>1=>0

repeating the above algo we get

PILE 3:

2=>1=>0

PILE 1:

1=>0

so we get three piles and thus the algorithm works fine for the given test case.
The code to this problem can be found here.

RESULT: 

I was not able to do D and E questions .Also, i wasted a lot of time in A and C.I need to work on my speed and accuracy.Overall i was not happy with my performance but than it was not bad at all.Finished 666.I hope you guys benefit from this Editorial. If there are any mistakes please point out in the comments section below.This was my first such editorial and i hope you  guys like it.Till the next time bye bye!!