BladeRunner's blog

By BladeRunner, history, 7 months ago, In English

You can now find the contest in the public gym, ICPC-de-Tryst 2024 (the ghost submissions can still be accessed in the older mashup).

Top 15
IITD Top 3
First Solves
Tutorial is loading...

Setter: BladeRunner

code
Tutorial is loading...

Setter: 33_arsenic_75, Preparation: islingr

code
Tutorial is loading...

Setter: sahilkumar_1

code
Tutorial is loading...

Setter: ajmeraraghav99

code
Tutorial is loading...

Setter: Azm1t

code
Tutorial is loading...

Setter: PROELECTRO444

code
Tutorial is loading...

Idea:PROELECTRO444 , BladeRunner Preparation: PROELECTRO444

code
Tutorial is loading...

Setter: islingr

code
Tutorial is loading...

Setter: Surver

code
Tutorial is loading...

Setter: BladeRunner

code
Tutorial is loading...

Setter: MridulAhi

code
Tutorial of ICPC-de-Tryst 2024
  • Vote: I like it
  • +51
  • Vote: I do not like it

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

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

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

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

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

Why is this giving TLE for G : link. The logic is quite similar to the editorial and time complexity is N.log^2(N) .

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

    It is because of using map in the binary search function. Simply push $$$(a[i]-(pw-s),1)$$$ and $$$(a[i]+(pw-s)+1,-1)$$$ in a vector and sort it and rest is same.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Does using map change the time complexity ? Because even after putting intervals in a vector, we are sorting it. Also this map solution got accepted : link

      Also, one more thing I would like to bring to your notice. Even O(N^2) solution got accepted for Problem E.link. I feel the test cases were weak for the problem.

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

        For your first question, it doesn't change the complexity but map has a higher constant factor so that might have caused issue, the solution that you attached of map creates some less map entries due to the min/max operation so got passed for that particular bottleneck test case (where $$$n$$$ achieved its largest possible value)

        For the second, we apologise for that and hope that not many teams got affected due to this and would ensure stronger test cases in future.

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

          Nevertheless, problems were amazing and fun to solve :)