KiZamaDo17's blog

Very Peculiar Problem in Think Cell Round 1 A
By KiZamaDo17, history, 10 months ago, In English

So this was the question 1930A - Maximise The Score at think-cell Round 1. We simply had to sort the array and add the odd entries.

And so I did except that it gets accepted or TLE rejected just cause of Variable name.

I chose the loop variable i here and it TLEd 250123631 I chose the loop variable j and the exact same code as above and it got accepted 250123236 There are two loops in my program and I named both as j and it still got accepted 250123505

So why the particular hate for "i"? satyam343 And I lost 15 extra minutes and valuable points in that question as well.

I would love to know the reason if someone could explain or if it is a CF issue.

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

»
10 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Because:

  • Java is slow.
  • Constraints were tight.
  • Your luck was bad.

I submitted your 250123631 again as 250126959, and it's accepted with 998 ms (Ouch).

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Java programs usually take that much time and I don't know much about the internal working of CF but I think they alot more time for different languages. I've never faced a problem before because of Java and to face one in something so trivial is this doesn't make sense. And why the variable name change works then. Same code for different people with different results don't make sense to me

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Time limit is same for any language you choose.

      If they keep constraints loose:

      • C++ users will be at advantage as their unoptimized solutions might get accepted.

      If they keep constraints tight:

      • Other languages will be at disadvantage as their optimized solutions might not get accepted.

      Therefore they tend to find a middle ground. In this case constraints were tight.
      250166204 This C++ submission I made got accepted in 639 ms.

      So why the particular hate for "i"?

      Now you must've understood that variable names don't matter.

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

      Also, as the constraint are tight, sometimes same solution can get accepted and sometimes it might get TLE. (Execution time can vary)

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

    Java's Scanner is known to be very slow for large inputs. All the solutions using Scanner for the problem you mentioned took > ~900ms, and I think most of the running time of those solutions is consumed just for parsing inputs.

    Some participants have custom input parsers, which can reduce the running time to ~300ms. I think all Java coders should use them in CF -- I assume they are equivalents of C++'s ios::sync_with_stdio(false) and cin.tie(nullptr).

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

      can you please refer some article or template where I can learn more about it?

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

        I think it's a good idea to start looking at a few solutions that run fast; you can sort solutions by execution time using a button available in the bottom of the "Status" screen.

        (I don't regularly use Java -- I only know the fact that Scanner is slow and I don't know what's the best practice)

        → Reply
»
10 months ago, # |
  Vote: I like it +25 Vote: I do not like it

First, It's not the variable name that changes the time it takes. It changes because in the for loop that you made with i you wrote i < 2*n, so you make the multiplication again in every iteration, but in the AC code, you put j < array.length. That's the difference in between AC and TLE.

And your code may be slower than you think because, as far as I am concerned, Arrays.sort(array); may have a complexity of n^2 which can make your code slower than expected.

Anyways, you still had bad luck

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    I've used j variable here with the constraint as 2*n abs it still got accepted. 250123363. It's definitely because of the loop variable I believe. And arrays.sort uses merge sort so the complexity is nlog(n) for sure. Anything else you may think could be the reason for it?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      for primitives if you use Arrays.sort(), it has worst case time complexity of 0(n^2), as it uses quick sort, to avoid that either create arrays using Objects from Wrapper Class or use Collections.sort(), they both use merge sort and are guaranteed to work in 0(nlogn). And use fast I/O in your template :)

      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used the loop variable I with array.length and it still TLEd. 250123142

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

      You forgot to change the loop before sorting too. AC

      (Still, it's very close to tle.)

      → Reply
»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

add special tl

→ Reply