Motarack's blog

By Motarack, history, 21 month(s) 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

»
21 month(s) 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 .

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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}$$$).

    • »
      »
      »
      21 month(s) 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))$$$

      • »
        »
        »
        »
        21 month(s) 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).

»
21 month(s) 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?

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

  • »
    »
    20 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.

»
6 weeks ago, # |
Rev. 7   Vote: I like it +10 Vote: I do not like it

In problem F, we wrote this code

Code

We are getting WA on test case 128, and we are unable to see if we have done a error in logic or if there is an error in handling precision.

We have written a very neat code so that you won't have trouble in understanding and debugging it.

Someone please have a look at the code and help us out.

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

    Are you sure this is correct:

    if (p2 > p3) { swap(p2, p3); }

    won't that give you the opposite of what you want?

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

      Yes we have realised that we were doing just the opposite. Now we have corrected our code but still we are getting WA on test case 133. What else do you think could be wrong?

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

        try this:

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

          Okay Thanks we understood where we are going wrong.

          Thank you very much for helping us out.