### Motarack's blog

By Motarack, history, 7 weeks ago, , Hello,

The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.

Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Spoiler!
Tutorial is loading...
Code arab, gym, Comments (15)
 » omg I didn't notice that the input in problem B (primes) is always a prime number , I solved it by building sieve array :D :D .still waiting for F editorial .very nice problems , thank you so much .
•  » » I also did the same:)
 » Need help in I Can we do this by using stack? 56522390
•  » » yes, you can. I did the same but using vector instead of stack. but you have the same mistake I had done. when you see like this bracket "(" you push the next element, this is wrong. imagine 3(10(15)) so you push 1 instead of 10 and again 1 instead of 15. so you need to get the whole number. my solution if you want to check how I solve this problem 56524350
•  » » » Ohk, I got it nowThanks for the help
 » Can anyone help me in understanding the concept behind the O(N) solution of problem K. I know it is a fairly common problem but I cannot seem to grasp the idea behind it. Can anyone please help me? It will really help me out in solving other problems like this.
•  » » Well, the idea is pretty straightforward, we just ignore the numbers in the array which have their 'i' th bit as zero, because 0 ^ 0 = 0. And we subtract the subsets formed by these numbers from the total subset possible, and hence the formula.
 » Can we do J using matrix exponential? There is a trick which calculates number of walks of length k in a graph by raising the power of adjacency matrix to k.
•  » » Yes we can by taking the sub-graph that we're only allowed to walk on from the original graph, but it has worse complexity, $O(m^3 \log{k}$).
•  » » » Actually, this solution, even if the limits are made smaller, will be wrong because we want the sum of matrix for all powers from 2 to min(m,k). so using matrix exponentiation has a complexity of $O(m^3min(m,k))$
•  » » » » we can add another row and column to the adjacency matrix and let one of the new cells be responsible for the sum of cell (0,0).
•  » » » » » yea sure that works.
 » For Question F, we can also find the answer by applying dfs and taking the post order traversal of graph, right?
 » I'm new here but wouldn't ... int main() { long a, b; cin >> a >> b; double x = log(a)/log(b); long xi = x+1; cout << xi << endl; return 0; } ... be an easier way to solve C (Dolls)?
•  » » That's another way to solve it, the intended solution is for people that don't know much about the log function.