### Motarack's blog

By Motarack, history, 17 months 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.

Code
Code
Code
Code
Code
Code
Code
Code
Code
Code
Code
Spoiler!
Code

• +32

 » 17 months ago, # |   0 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 .
•  » » 17 months ago, # ^ |   +3 I also did the same:)
 » 17 months ago, # |   +3 Need help in I Can we do this by using stack? 56522390
•  » » 17 months ago, # ^ |   0 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
•  » » » 17 months ago, # ^ |   0 Ohk, I got it nowThanks for the help
 » 17 months ago, # |   +3 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.
•  » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # |   0 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.
•  » » 17 months ago, # ^ |   +1 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}$).
•  » » » 17 months ago, # ^ |   +8 Actually, this solution, even if the limits are made smaller, will be wrong because we want the sum of matrix[0][0] for all powers from 2 to min(m,k). so using matrix exponentiation has a complexity of $O(m^3min(m,k))$
•  » » » » 17 months ago, # ^ |   +4 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).
•  » » » » » 17 months ago, # ^ |   0 yea sure that works.
 » 17 months ago, # |   0 For Question F, we can also find the answer by applying dfs and taking the post order traversal of graph, right?
 » 16 months ago, # |   0 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)?
•  » » 16 months ago, # ^ |   0 That's another way to solve it, the intended solution is for people that don't know much about the log function.