biranchi's blog

By biranchi, history, 9 months ago, In English

Hello, codeforces I was doing D of ACL contest 2 today. Before diving into the issue I want to specify that I know the basic use of segment tree, like finding max range query and update. It seemed to me similar with LIS. After scratching some time, I came up with segment tree idea. Here I am writing about my idea.

  1. taking x as input
  2. Finding the maximum range query of x-k to x+k i.e. maxh
  3. updating the index of x with the value of maxh+1.
  4. Atlast finding maximum range query from 1 to n

I am pretty sure that this method should solve this problem but in the contest, submission gave 6 correct and 26 wrong results. I want to know your feedback and suggestions.

I copied the code of the segment tree from gfg and modified as per the requirements. Here is my code link Here is problem link

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By biranchi, history, 9 months ago, In English

Hello, I was recently coding a problem and my approach was correct. But I was using all variables in the form of long long int. I had used #define int long long.

In this problem, it was not necessary to use long long.

I submitted code and result was TLE. And I observed that the time taken was above 3200 ms in cp editor. Then after scratching my head for 1 hour, I atlast went for other users' solutions. The only difference was they used int and approach was the same. I did the same. I deleted this line #define int long long. The time taken was now slightly above 2500 ms. I submitted the code and it was accepted.

Bonus questions : My second successful code was taking time above of 2500ms in my local machine(in cp editor). But the time constraint of that problem was 2 seconds. Why was the code accepted? The problem was from cses problem set. Are there any relatively similar incidents that occurred to you? I would be happy to know some, especially in codeforces platform?

Read more »

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