tejustiwari's blog

Strange Behaviour : TLE in Problem B— Kill `Em All ( Educational Round 74 )
By tejustiwari, history, 4 years ago, In English

Can Someone Please Tell Me Why is this Happening ?
Problem : 1238B - Убей их всех
83162183 This Submission gives TLE
83162136 This Submission gets Accepted

The only difference in both the submissions is shown in the picture
i added one single line of code and got TLE
if i remove this green highlighted line of code the solution gets Accepted ,
Even if I am removing the if condition , the solution gets accepted 83161695

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tejustiwari (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tejustiwari (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

One thing I realized is that the size of template is inversely proportional to the rating of person. At the end you only used basic stl and manipulation, so what was the need of such long template??

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

    That makes no difference kingkong1 & that is not the reason for getting a TLE verdict. Unrated people talking about ratings HUH ! You better Give some contests then we'll talk about ratings and proportionality.

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

    MiFaFaOvO, Um_nik, tourist (occasionally), maroonrk, Benq, and Radewoosh all use templates. These are just a few Legendary Grandmasters that do.

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

    hmm yes so u must have a mega long template, get kong'd

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm not sure, but declaring int val[100005] = {} for every test case might cause TLE. I guess maybe modifying val means that it has to be reinitialized every time. There's no use for val anyways, since set automatically removes duplicates.

In general, try to avoid declaring large constant-length arrays for each test case.

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

    thanks qpwoeirut but have a look at the accepted solution in which i am doing the same . I am declaring int val[100005] = {} for every test case still the solution gets accepted .

    Using val[] { the highlighted part } inside the if condition is the reason behind TLE which I suppose is an O(1) operation and must not be the reason behind TLE but sadly it is the only reason

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

      Here are some interesting observations:

      1. Changing val from int[] to bool[] gets AC even with val[a[i]] = 1 operation enabled.
      2. Declaring val global doesn't help.
      3. Most interestingly, commenting the if statement gets AC even with val[a[i]] = 1 operation enabled. 83166543

      It's some peculiar behaviour. It will be interesting to see if somebody can explain this.

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

      It's definitely not the operation costs.

      Below code gets AC and it does everything.

      fo(i,n)
          {
            cin>>a[i];
            if (val[a[i]] != 1) {   // Always check the condition
                int x = 1, y = 2;
                assert(x + y == 3);
            }
            s.insert(a[i]);     // Always insert a[i]
            val[a[i]]=1;        // Always set val[a[i]]
            maxi=max(maxi,a[i]);
          }

      Submission 83167312

      TLE occurs only if the statement val[a[i]] = 1 is inside the if (val[a[i]] != 1) condition and val is an int[] array;

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

        Thankyou Grey_Matter for your Great Observations .
        Yeah val[a[i]] = 1 is the only reason behind getting TLE .
        And i guess assigning val[a[i]] = 1 inside the if condition is no more than O(1)

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

If u change int val [ ] to bool val [ ] .. your solution will work.

your edited solution

my solution

found something : )

bool vs int comparison (time)

Which value is better to use? Boolean true or Integer 1?

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

    Thanks Anadii it helped a lot

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

    I use bitset everytime instead of declaring an array of bool.

    instead of bool vis[MAXN] ={0);

    I write bitset < MAXN > vis; // By default every bit is set 0.

    Now you can use this just like you use array by this operator []. Also when you want to clear all the bits of vis array to 0 you can use memset or do it manually taking O(MAXN) time. While in case of bitset you write vis.clear(); And this takes O(MAXN/32) time.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

If you do not modify elements of val[] array, the compiler knows its values (all zeroes btw) and optimizes code accordingly.

You can analyze it here: https://godbolt.org/z/NQBf32

→ Reply