Motarack's blog

By Motarack, history, 7 weeks ago, In English,

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
 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Need help in I Can we do this by using stack? 56522390

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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}$$$).

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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))$$$

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Question F, we can also find the answer by applying dfs and taking the post order traversal of graph, right?

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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)?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's another way to solve it, the intended solution is for people that don't know much about the log function.