Problem A - Bovine Dilemma

Problem Link

Area of triangle is $ (1/2)* Base * Height $

Height is a constant 1

Only variable is Base Length which is X[j] - X[i].

So we can simply do a O(n^2) brute force.

Code

Solution Link

Problem B - Last minute enhancements

Problem Link

we can simply notice that

if

1) A[i] > A[i-1] ----> Then its never better to increase A[i] as neighter it does any good for ith index nor it will be any good for futher indexex

2) A[i] <= A[i-1] ----> Then its always good to increase A[i] to A[i]+1.

Code

Solution Link

Problem C - Canine poetry

Problem Link

So any palindrome of

-> even length is of form

S1 S2 S3 S3 S2 S1 

=> It will always have a palindrome of length 2

-> odd length is of form

S1 S2 S3 C S3 S2 S1

=> It will always have a palindrom of length 3

=> We just need to make sure that we don’t have

 1) palindrom of length 2 i.e. S[i]!=S[i-1]
 2) palindrom of length 3 i.e. S[i]!=S[i-2]

Code

Solution Link

Problem D - 13th Labour of Heracles

Problem Link

Lets increase K from 1 to N-1

for K :-

k = 1 :- All edges will be coloured with one colour and ans will be sum of weights of all nodes let it be S

k = 2 :- Lets say we choose one edge 

          E1 connnecting N1 ----- N2

          and color all edge in subtree rooted at N1 with one color1 and color all edge in subtree rooted at N2 with other color2 and color edge E1 with color2

          And ans will be S + W[N1]

          S+W[N1] will be maximum when W[N1] is maximum 

k = 3 :- we can perform the same process we did for K=2

Code

Solution Link