bro, just wait until tomorrow

Saudi Arabia:

• faresbasbas (Fares Basuni)
• DEDA (Mohammed Alrefaei)
• Mohammad-Alsaad (Mohammed Alsaad)
• Rayaabualjamal (Raya Abuljamal)

That's cool thank you very much, but actually in the real problem I don't have to do the range update, but finding dp[i] = max l <= j <= r (dp[j] — (i-j+1)*x) for log n values of x.

Which I found the it can be done in O(log n) using convex hull with li chao tree.

But I really appreciate it thank you very much :)

No it doesn't have to.

Lol then i think i didn't understand your approach :)

Actually sorry I didn't mention, but you have to solve the queries online not offline.

Actually that's the straight forward to think of the problem, But at least for me i am not able to add the lazy propagation to it, Because the maximum prefix will change.

Let's say that the maximum prefix in some segment is 10 and the length is 8 while there is a prefix of length 2 and value of 9, If we did a -2 query for the segment, The best prefix isn't 10 — 2*8, But 9 — 2*2.

So the best prefix isn't fixed, Hope you got the point.

How would you query in log^2(n) ?

Actually i thought of polynomial update in segment tree of prefixes, But i actually don't know how to find the max in range with the polynomial update, I just know how to get the sum.

Any ideas how to get the maximum with the polynomial update ?

Hey, you are giving me techniques, But not solutions.

how ?

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

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

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

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

ohh yeah i just got it all right now thank you very much :))

is it possible to explain the last 4 loops cause i am not used to python :)

ohh ok

is my point clear to you ?

take this for example

n = 4 , m = 2

1 2

2 3

you will connect 3 -> 1 then you will have 4 as a sink and source at the same time and you can add only 1 more edge what would you do in this case ?

Yeah it's very clear to me i did implement it and it looks to work for single component graph, but can you solution be generalized for several DAGs in the graph ?

Also how would you deal with it if the graph is made of multiple DAGs ?

so as i did understand

firstly:

for any source i will try to connect it to exactly one sink which it can reach if not i will add it to never_matched_sources

secondly:

i will find all of the unmatched sinks and put them in never_matched_sinks

thirdly:

strongly connect the never_matched_sinks to the never_matched_sources

fourthly:

i have to strongly connect the rest

is it this ?

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

Also thank you for the edge case lol

ohh ok i misunderstoond you sorry :)

but i appreciate you helping me :)

thank you very much

Actually, I've read this paper more than once but the idea isn't very clear to me. Also I tried to just implement it, And it didn't work, probably there is something I missed, But I am not able to figure it out.

the solution of this example should be 4 -> 1 , 3 -> 2 while your idea's logic say the answer is 3 -> 4 , 4 -> 1 which is wrong

i mean it's still not a SCC but i need to be an SCC

each vertex should be in a different SCC in the example 1,3,4 can't reach each other out only 1 can reach 3,4 but 3,4 can't reach anything

why ? won't you connect 3 -> 4 , 4 -> 1 which is wrong ?

Any other ideas of how to make it work :)?

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

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

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

Ok it looks very clear for me thank you very much except this part (cnkn,s1) which is the last edge, but how can we deal with it if we had multiple DAGs in the same graph?

lol it doesn't require digit dp it was just x = a^b which is xoring boxes 2..n , y = a+b , a is A[0] , b is A[1] , then you just have to find the a&b which is w = (a+b-a^b)/2 , then the answer at first is w then you have to iterate from left to right on x and if you can add this bit to the answer without exceeding a then just add it. this is the solution briefly but you have to add the -1 cases inside

Probably you have a memory limit, sometimes memory limit represent as runtime error

ohh okay thanks :)

nope

ok thanks

i submitted the code in oj.uz for problem C and i got 100 points but when i submit the same code in JOI submit i got 20 points + 2 wrong test cases in the last 2 subtasks , strange

it makes sense now thanks :)

• well, how will you differentiate between
• "100---" from right to left going toward 0
• "-001--" from left to right going opposite 0
• in both ways you will have "001" ?

a

i got a small problem in my code in problem F if someone can help me i just did dp[curr positions in s1][curr position is s2][diff between open and closed brackets] i will represent it as dp[curr1][curr2][val] i can made transitions just if after the transition the val will stay non-negative and then i know the length of the answer is less than or equal to 400 so if length > 400 or the val is > 200 i will just return inf that is my first submission 66726623 which just returned inf and that is my other submission 66727771 which i just return when siz > 1000 and it got accepted can someone explain the what is the problem please ?

cool theorem name XD

because the number of digits in the binary representation of the max value can be

in Problem E what is the best RSQ can be used with a few implementation cause i thought of segment tree so that we have n segment tree of base m and m segment tree of size n but it would be a lot of implementation so what do u think ?

the time limit in problem E was very strict so that recursive do doesn't work sadly there were no time to change the recursive version to the iterative version

yeah that what i thinked of i think it's possible to do it with 2d segment tree with lazy propagation and it will be q*log^2(n)

agree that was very sad that i already write the code but there were a tiny implementation error and i got -11 rating but not +100 or something like that

yeah cause if u have let's say x as divisor n times u can just take one from it cause the anyone from rest will not be coprime with it

prime divisor**

the number of divisor of gcd(a,b) + 1