practice_has's blog

CSES Coin Combinations II
By practice_has, history, 7 months ago, In English

Can someone tell me what is the difference in logic between the two solutions?

The first solution is accepted by the CSES

Code 1

The second solution is giving TLE

Code 2

The only difference in code is the order of nested for loop

Someone please help!

  • Vote: I like it
  • -6
  • Vote: I do not like it

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

Even I faced the same issue, I think the problem is that it is faster to make n vectors of size x than x vectors of size n, as n has goes up to 100 and x upto 1e6.

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

    I get you but even if you make n*x vector and use x loop before n loop then only 1 more test case is passing and 4 are still giving TLE, perhaps row-major order address calculation

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

even if it didn't TLE, the second one would be wrong because it counts the same ordered way multiple times

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

    It's not true brother, since you need the previous state to be calculated before the current state, you can do any order, the answer will be correct! Suppose :- x = 7 and coins = {2, 5} According to you it should give 2+5 and 5+2 that is 2 ways but it's giving only 1

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

      my bad, i did not notice that your vector was 2-dimensional

      i think this is an issue with the CSES grader, on my device it runs at almost the same time and the if statements trigger the same amount of times

      that being said, for this problem, i would recommend using a single 1D DP array instead of a 2D DP array; it saves a lot of time and memory.

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I also found the TL to be too tight on this one. I usually use arrays instead of vectors in such cases

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

    I tried with arrays too, in both the order of the loops, it gave TLE for the code similar to 2nd and got accepted for the code similar to 1st

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

    TL isn't that tight if you use a 1d DP

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

there i a very easy solution using 1D dp i also had this problem when using 2d arrays so i just changed the space complexity to 1 dimension too (by the way the time complexity was O(n*k) still got tle with the 2d pretty expected cses grader is known for being slow)

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

It's because your first implementation has more cache hits than the second one. In C++, when you make a std::vector<std::vector>>, the outer vector may look like (v[0]. v[1], v[2] ... , v[n-1]), but the std::vectors are not contiguously allocated in the memory. Try doing this a few times:

vector<vector<ll>> z(5, vector<ll> (6, 0));
cout << &(z[0].back()) + 1 << " " << &(z[1].front()) << endl;

You will not always get the same memory address for consecutive vectors. However, all its elements are allocated contiguously for one particular 1-d std::vector.

In the questions n < 100 and x < 1e5. So, it's faster to access x elements of a vector consecutively.

Hence, in the first implementation, you accessed longer contiguous memory segments and got more cache hits than in the second implementation, which is why you got TLE for the second case.

→ Reply