- Contest was held like every year in
INPT
, with over 50 teams qualified to finals
- Author: Youssef izikitne
- Description:
- Given an array of numbers determine if it's increasing
- Solution
- This was the easiest problem, you can do a linear scan, checking each integer with previous let's call it
last
and iflast > a[i]
then the sequence is not increasing, otherwise it is .
- This was the easiest problem, you can do a linear scan, checking each integer with previous let's call it
- Complexity:
O(N)
- Author: Morthada touzi
- Description:
- Given an array find the number of elements that are different from the min and max
- Solution
- Another easy problem, just find
min
andmax
of the array, than have acounter = 0
and scan the array, if ana[i] != min && a[i] != max
thencounter++
. - make sure to take only distinct values .
- Another easy problem, just find
- Complexity:
O(N)
- Author: Youssef izikitne
- Description:
- it's a classical problem called
josephus problem
withk = 1
- it's a classical problem called
- Solution
- You have to solve the math problem so you can come up with the recursion
- Complexity:
O(log(N))
-
Author: Issam baskati
-
Description:
- Problem statement is pretty clear, given a list of subjects with their difficulties, hourly volume and allowed number of hours to absent, and number of hours that miller wants to absent, you need to find the minimum sum of difficulties of exams that he have to retake .
-
Solution
- This problem can be seen as the standard
Knapsack
problem . - To eliminate the case where the minimum sum is
0
, just do the sum of the allowed number of hours and if it's bigger thanM
, then the answer is0
. - otherwise you can define a function
f(i, m)
where i is the index of the current subject, and m is the number of hours left, so we can define a recurrence like this:
// base case being m <= 0 ? 0: INF ans = INF; ans = min( ans, f(i + 1, m - a[i]) ); ans = min( ans, f(i + 1, m - h[i]) + d[i] );
- This problem can be seen as the standard
-
Complexity:
O(N * M)
-
Author: SGATS
-
Description:
- Given a set of classes and dependencies between them, and
Q
queries each query is in the form ofu v
meaning add a dependency betweenu
andv
, for each query output the number of unreachable nodes from node1
- Given a set of classes and dependencies between them, and
-
Solution
- The problem can be seen as a graph of dependencies, where each class represents a node, an each query can represent the addition of a new edge in this graph.
- To simplify the answer, we will find the number of nodes reachable from
1
and since the total number of nodes is fixed the answer will be simplyN - count
. - Now the problem is pretty standard, we can use
Union find
datastructure to compute the size of eachConnected Component
, and we have to keep track of the size of the component containing1
.
-
Complexity:
O(Q * log(N))
-
Challenge: Can you solve the problem with the addition of another type of queries:
u v
remove edge between u and v ?
-
Author: Morthada touzi
-
Description:
- Given a string containing lowercase characters, and value of each alphabet character, find the biggest value of a palindromic subsequence
-
Solution
- The problem is just straightforward Dynamic programming, you can build a function
f(i, j)
that computes the answer for array betweeni
andj
, the recurrence is quite easy to get
// try skip right, and skip left ans = max( f(i, j - 1), f(i + 1, j), ); // try to include the palindromic subsequence containing i and j if (s[i] == s[j]) { ans = max( ans, 2 * val[s[i] - 'a'] + rec(i + 1, j - 1) ); }
- one interesting thing to notice was that the answer can never be smaller that
0
, as the empty string is considered a palindromic subsequence, and thus this makes our base case to be.
if(i == j) return max(0, val[s[i] - 'a']);
- The problem is just straightforward Dynamic programming, you can build a function
-
Complexity:
O(N^2)
-
Author: Mehdi
-
Description:
- Given an array, you need to perform 2 types of queries on it:
- Change the value at a given index
- Compute the number of values that are strictly smaller than a given value
v
- Given an array, you need to perform 2 types of queries on it:
-
Solution
- This problem can be solved with different ways, i'll explain the easiest .
- We can split the array into
buckets
of sizeX
and precalculate the answer for eachbucket
. every update operation will only change the answer for one givenbucket
, and for the query, we will need to traverse at mostN/X
bucket to know the final answer. only question left now, is how to chooseX
? SQRT decomposition - For each
bucket
keep an array of sorted items in it so we can usebinary search
to find the number of elements strictly smaller than a valuev
inO(log(sqrt(N)))
time . - each update, we will need to find the element with the given index in the
bucket
and update it, and then do a sort inO(sqrt(N) * log(sqrt(N)))
or simply do swaps to put the element in his position because we only change one element at a time, with a complexity ofO(sqrt(N))
.
-
Challenge: find other ways to solve it ๐
-
Complexity:
O(sqrt(N) * log(sqrt(N)) * Q)
-
Author: Khaled Sliti
-
Description:
- Given an tree, where each edge have a number assigned to it, you need to answer
Q
queriesL R u v
can we traverse along the simple path bewtweenu
andv
where all edges in the path have numbers betweenL
andR
- Given an tree, where each edge have a number assigned to it, you need to answer
-
Solution
- You can solve the problem in 2 ways:
- The first way is using HLD to decompose the tree into heavy and light edges, and have a
Segment tree
for each path, and with that we can answer the queries inO(log(N) ^ 2)
, but that would be overkill ๐ - Since we don't have updates, we can solve it using regular old
sparse table
like approach . - compute 3 matrices:
parent
,min
andmax
- each matrix will contain : information for level
2^i
for vertex u, an example would beparent[1][u]
is the ancestor of u at level2
, same thing withmin
andmax
, but they will contain the maximum encountered edge value for nodeu
at level2^i
. - Now for each query we do the same procedure for finding the
lca(u, v)
, but for each jump we keep themin
andmax
over all jumps. - if the min and the maximum are bounded by
L
andR
we say that we can, otherwise we know that there is an edge that is bigger or smaller theR
orL
accordingly .
-
Complexity:
O(log(N) * Q)