Блог пользователя tejustiwari

Strange Behaviour : TLE in Problem B— Kill `Em All ( Educational Round 74 )
Автор tejustiwari, история, 4 года назад, По-английски

Can Someone Please Tell Me Why is this Happening ?
Problem : 1238B - Kill `Em All
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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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??

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        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)

        → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks Anadii it helped a lot

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить