How to solve?

https://www.codechef.com/LICO2020/problems/PATTERNG

Can you please explain the third Question

I actually don’t know either. I just got lucky by noticing that if I take the max value of each row as array, that is the answer. Then I tried the bitwise OR value of each value in the row, and that worked.

ok, thank you

I can explain 4th if you want.

well i will try it first and if I am unable to solve will surely contact. THANK YOU ONCE AGAIN!

Hi. Can you explain the idea, please?

Also, do you know whether editorial wil be published or not?

Editorials will be published soon.

For 4th the idea is that, we want to know the number of triangles the line collides with. So, if we can for each triangle, have the extreme coordinates (xmin, xmax, ymin, ymax) then for xmin + 1 to xmax - 1 we can use a array and set the count to 1 so that all queries for this range will give answer 1, and similarly for all other triangles we increase the count by 1 for their respective ranges. But this will TLE as 10^5 we can’t iterate from xmin to xmax or ymin to ymax, so there is a trick using prefix array.

In this, suppose I want to set all elements from index 2 to 4 as 1 [0, 0, 0, 0, 0, 0, 0] => [0, 0, 1, 1, 1, 0] i can instead use => [0, 0, 1, 0, 0, -1] and then calculate prefix sum which gives me the same array.

Here you can read my submission:

https://www.codechef.com/viewsolution/34650059

First of all, there are X = 1 + 2 + 3 + ..... + (R - 1) = R(R-1)/2 characters before the R'th row.

Let S be the given string and i = {X mod |S|}.

Then the R'th row will start with the character S_i.

The remaining part is easy, just calculate how many C are there in R't row if we start from the i'th position using precalculated prefix sum array for each character.

Another problem is calculating X. It can be very big. I had to use 128 bit integer. But it can also be done by calculating i directly simply using modular arithmetic.

WIll be posted today, before 12.

Wooow! Your idea of prefix array is genius! I also observed what you said above but I couldn’t calculate the anwer efficiently. Thanks a lot for this great trick and especially for your effort.

If you know any, can you suggest some problems that could be solved with this amazing trick, please? Or is there any tutorial or paper that I can read further on this technique?