Problem A – Nearest Taller Girl

Category: Adhoc

Author: Saad Taame

Hint:

Starting from index i, look for the first girl j whose height is more than h(i) and print her index.

Reiterate starting from j.

Be careful, indexing starts from 1 !

Problem B – Flower Graphs

Category: Graphs,Combinatorics

Author: Saad Taame

Hint :

Let deg(i) be the degree of vertex i.

If deg(i)>= d then i can be the center of C(deg(i),d) flower graphs, where C(n,k) is the Binomial coefficient.

The answer to the problem is Sum C(deg(i),d)%mod.

Problem C – Shortest Route

Category: Adhoc

Author: Saad Taame

Hint :

The best strategy is to make min(N,M) diagonal moves toward (min(N,M),min(N,M)) and then to continue either right if N<M or down if not.
So the answer to the problem is min(N,M)+ (max(N,M)-min(N,M)) = max(N,M)

Problem D – Robot 

Category: Geometry

Author: Moncef Mhasni

Hint :

OP = OO1 + O1O2 + … + OnP = (0,l0)+(l1sin(t0),l1cos(t0))+(l2sin(t0+t1),l2cos(t0+t1))+…

Xp = Sum li*sin(Sum tj)

Yp = l0 + Sum li*cos(sum tj)

Problem E – Music identification

 

Category: Strings

Author: Moncef Mhasni

Hint :

Go over all the songs in the database.

If P is a substring of a song in the database, print its name. The songs may contain spaces, read by line!

Problem F – mdN Encryption

 

Category: DP, Combinatorics

Author: Moncef Mhasni

Hint :

To break down the encryption method, the cracking tool can guess C, C+1, C+i,…N-2 or N correct matching (Why not N-1? take a pencil a try to make N-1 matching).

To guess C+i correct matching, there is C(N,i) ways to choose a character (regardless of its encoding) and D(N-i) ways to encode it. Where C is the binomial coefficient and D(i) the derangement of i.

The number of ways to guess exactly C+i correct matching is C(N,i)*D(N-i).

First pre-calculate C(N,k) and D(k) for N < 10000 in O(N log(N)), then answer each test case in O(N-C).

Problem G – Leila and Coins

 

Category: Adhoc

Author: Khalil Ait Brahim

Hint:

Just store all numbers, and loop on the occurrences of the numbers in the rang and add them.

Problem H – Mountain heights

 

Category: Geometry

Author: Ahmed Tailouloute

Hint :

Let h(i) be the height of the mountain i, and g the gap between the mountains i and i+1.

if h(i)>h(i+1) then to see the mountain i+2, h(i+2) must be superior to h(i+1)-g = h(i+1)-(h(i)-h(i+1)) = 2*h(i+1)-h(i)

otherwise, h(i+2) must be superior to h(i+1)+g = h(i+1)+(h(i+1)-h(i)) = 2*h(i+1)-h(i)

In both cases, h(i+2) > 2*h(i+1)-h(i)

Problem H – Missing Episode

Category: Adhoc

Author: Ahmed Tailouloute

Hint :

While reading the episodes’ numbers, mark each one in an array of bools (for example, v[i]=1 if she watched the episode number i) . Then search for the unmarked episode and print its index.

Or just use the formula 1+2+..+n=n*(n+1)/2 and then m=n*(n+1)/2-Sum(read numbers)