Mostafa_Alaa99's blog

About the last Div2 C :)
By Mostafa_Alaa99, history, 11 months ago, In English

Who saw Div2C today and then said "Ooooh, it is very clear.....segment tree/sparse table with Binary Search ^_^" Are there anyone other than me or am I an Alien? :) I even built the whole range query structure like I was preparing for war. (I have it in my template) Turns out… it was a simple loop with a few ifs and mins. But hey, at least my overkill solution was a bit fast!

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

»
11 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

can you explain how will you use sparse table with binary search? that will get you longest subarray s.t. gcd equal i while you want subsequence, im curious what's your approach!

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

    It was finding for each i

    binary search on the left side to get the element j from 0 to i such that all elements from j to i are equal to a[i], and to find that I was for each j I am trying I am checking if max from j to i equals to min from j to i and Sparse table can answer this query quickly (max or min in range) and once the j is working I am letting it go more to the left and if not go more to the right until u find the best one using Binary search, then add a[i] * j (a[i] times the elements before the j I found)

    same idea for the other side exactly but with very small changes and then add its score to the prev score and compare with my best score then print the best score (the minimal one), that's it, I thought everybody thought like that, haha

    → Reply
»
11 months ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

For me it was totally different... i just saw and felt like wtf how this question is so easy.... And then I went to D thinking that it would be as usual impossible question for me.... but boom... so simple solution that I wasted 2 minute thinking that there is zero chance of this being the solution(p.s.: still hacking stuff to go lol)

→ Reply
»
11 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Took me 1 penalty and 10 minutes to figure out the edge case (to check the last block as well)

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

The only thing I learned is I'm never doing a contest at school again :(

→ Reply