Motarack's blog

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

»
17 months 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 .

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    17 months 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

»
17 months 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.

  • »
    »
    17 months 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.

»
17 months 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.

  • »
    »
    17 months 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}$$$).

    • »
      »
      »
      17 months 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))$$$

      • »
        »
        »
        »
        17 months 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).

»
17 months 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?

»
16 months 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)?

  • »
    »
    16 months 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.