Introduction

Yesterday I participitated in 100th Educational Round on codeforces I performed decently but not satisfactory. I am able to do only ABC Problems and due to that got only +5 in rating which took my rating to 1893.

Now lets jump directly to Explations/Solutions

Solutions

Problem A :- Dungeon

Problem Link

I tought like if we xth enchanced shot as the last one than total reduction will be

TotalShotsFired = 7x // as every 7th shot will be enchanced

TotalDamageCaused = 6x (normal shots) +3x (there is x enhanced shots with each doing 3 damage in total) = 9x

It implies

1. Total Health of all monster (A+B+C) has to be a multiple of 9

As each enchanced shot will cause damage to each monster so

2. x>=min(A,B,C);

Code

Codeforced Solution

Problem B :- Find The Array

Problem Link

Just by reading the problem we can get the intution that it will have a constructive solution. By looking at the first test case I thought may be we can always form a solution containing a single element.

So I tried element a[0] and a[n-1] and check condition three given in Problem but its not the case.

Now, I am still struck on the idea that solutoin contain a single element so I tried to take any a[i] and tried to come up with some condition on basis of which I can choose ‘i’ but its still wrong

I wasted quite a lot of time on this idea

Then I thought of making absolute difference between array ‘a’ and ‘b’ as less as possible implies making array ‘b’ equals to ‘a’

Now only problem is to satisfy condition 2 which can be satisfied if every alternate element is 1

Hence Solution is

a[1] 1 a[3] 1 a[4] 1 ...

or

1 a[2] 1 a[4] 1 ...

Code

Codeforced Solution

Problem 3 :- Busy Robot

Problem Link

Now In this questions, First we can notice that it we can simulate the movement of robot and get which command is Good/Successfull. We can also store for each good command that during its execution it will move from X1 to X2.

I have a poor implementation that took me a lot of time penalty.

Code

Codeforces Solution

Problem 4 :- Pairs

Problem Link

In this problem, Let’s say we represent the problem as

S = OXOXOXXOXOOX where { S[i] = ‘X’ -> ith element is present

                          S[i] = 'O'   -> ith element is not present }

Now Lets try :-

x=0, means we need to take maximum from each pair that is every 'X' must be paired with a previous 'O'

x=1, means we need to take minimum from exacty one pair that is ( one 'O' must be paired with a previous 'X'  + exactly n-1 'X' must be paired with a previous 'O'. 

x=2, means we need to take minimum from exacty 2 pair that is ( 2 'O' must be paired with a previous 'X'  + exactly n-2 'X' must be paired with a previous 'O'. 

x=n-1, means we need to take minimum from exacty n-1 pair that is ( n-1 'O' must be paired with a previous 'X'  + exactly 1 'X' must be paired with a previous 'O'.

x=n ,means we need to take minimum from exacty n pair that is ( n 'O' must be paired with a previous 'X'  + exactly 0 'X' must be paired with a previous 'O'.

Means maximum value of x will be the maximum “OX” subsequence that we can get

And

Means maximum value of n-x,meaning minimum of x, will be the maximum “XO” sub subsequence that we can get

ans = Xmax-Xmin+1;

code

Codeforces Solution

Problem 5 :- Plan of Lectures

Problem Link

This Problem also looks more of a inplementation problem.

Taking care of requirement 1 is easy we just need to form a directed graph and find topological sorting for requirement 2, if T1 is supposed to be followed by T2 then ordering T1,T2 is fixed, now suppose T2 is to be followed by T3 then ordering T1,T2,T3 is fixed means we will chains of fixed ordering.

so we can just compress these chain, then form graph based on prerequite, find topological sorting of graph and then decompress the nodes.

code

Codeforces Solution

Discussion

I think I did A nicely.

I took to much time on B, I completed at 33rd min which is too bad, actually I got struck on one idea and wasted lot of time on it I guess whenever sum/2 term comes we can think it in terms of Seven and Sodd or dividing sum in 2 groups. I should have looked at Sodd and Seven earlier.

I also took a bit more time to implement C.

I could not do D in contest, One thing to learn from this is whenever possible try to form Hotvector encoding and then think. Paranthesis should also be kelt in mind here. Also keep making cases and then think

During upsolving E looked easy to me and idea came quite easly to me. Though I took quite a lot of time to implement.