hello there

this problem is a classic dp problem and it's not so hard to come up with the solution

but i keep getting WA ... my code works on every testcase i throw a it

if someone could help me find my error it would be great :D

here's the code

Hello there

I'm trying to solve this problem

I've thought alot about it and have no idea

Any clues would be appreciated

I'm trying to solve this problem

getting denial of judgement

what is the reason for this ?

here's the code

Hello there

I know that minimum vertex cover is equal to maximum matching

My question is about how to find the vertices that form the cover

any help would be appreciated

Hello there

I've been trying to figure out how to turn this problem into a game of nim but with no luck

if anyone could help it would be really appreciated :D

extra question : i've been thinking the game of turning turtles for a while and the logic behind it

it's a game where we have a row of turtles some on their backs some on their legs ... in each move you can turn a turtle that's on its back and put it on it's legs and u can optionally turn a turtle with position on it's left from any state to the opposite state ... he who can't make anymore moves loses ... any help with that would be really appreciated :D

Hello there

I'm trying to solve this problem where i have to find the minimum shortest path spanning tree from vertex u

I'm trying to solve it with dijkstra where i take the shorter edge when two paths are equal to the same node ... and i found that what i've been doing is the intended solution from the editorial

but i keep getting WA on test 8 and it says duplicate edges ... but i can't see where my code could do that

here is my submission

please help :/

I was trying to solve this problem

and calculating the GCD for two double variables i put eps = 1e-8 and i got WA

wondering what was going on i looked at other codes and all they did that was different was put eps = 1e-4

i tried it and got AC, and tried every value upto 1e-8 and all of them got right answers

it got me wondering about the reason

here is my submission

any clarification would be appreciated

Hello there

I'm trying to solve this problem on LOJ

It's about finding minimum path cover in an acyclic graph that are not vertex disjoint (paths can share vertices)

what I'm doing is calculating the maximum independent set on the graph's transitive closure

I keep getting tle and i thought my approach was too slow but then i found this Chinese blog that uses the same approach and gets accepted on the problem

now i wonder what am i doing that's too slow

here is the code.

specific code steps are :

1- turning graph to dag with computing SSCs (tried using both kosaraju and tarjan)

2- calculating transitive closure of new dag

3- using hopcroft karp on bipartite graph constructed from dag

any help would be really appreciated

Hello there

I've always been scared of a problem when i read the phrase They Both Play Optimally

with no background or basis on game theory, any help regarding where i should start, books to read, courses to watch would be really appreciated :D

Hello there

I'm trying to solve this problem D div1 from round 345

if you haven't read it it's about finding LIS for each query where each query we change the value of a number independently

doing just like the editorial said and using persistent segment trees i keep getting MLE

i tried optimizing the memory usage but no use

if anyone could find the reason for memory leak it would be really awesome

here's the code

Hello There

I came across this problem on spoj

we're given a tree and we have to find two paths that don't share vertices and which sum of their length is maximum

no i got an idea where we compute the longest path for each subtree rooted with vertex u and there answer is the max sum for each node where for each node we sum the longest path in the subtree rooted with u and the longest path in the entire tree minus the sub tree rooted with u

the latter was a bit confusing for me and i couldn't come up with the solution

any advises or hints about how to compute the longest path in the tree minus the subtree rooted with u for each vertex u would be greatly appreciated

Hello there

i came across this problem on spoj

we have 500 people where some believe a bird can carry a coconut and some don't (N<=500)

now each person has friends, and we want the sum of people who change what they think and the conflicts of opinions between friends to be minimum

i googled and found that it's a min cut problem ... but i failed to understand the reason

any explanation would be greatly appreciated

Hello there

so i found this problem on spoj

we have a tree where each node has an integer weight and two types of queries

1- print sum of weights in subtree of given node

2- change root to given node

now first type of queries is no issue if the root is fixed ... i would solve it with segment tree, but changing the root kinda ruins everything

any hints about how i should think about this would be really appreciated :D

Hello There

So i found this Problem where i have to find the LIS of 10^5 pairs of integers

a pair is greater than another pair if x1<x2 and y1<y2 strictly

now finding LIS using a segment tree for such a large input is no issue ... but sorting the pairs kinda confused me

any ideas or hints how should i think about this problem ?

Hello there

so I'm trying to solve this problem

It's about finding the gcd of a set of numbers where i insert and delete numbers from the set

I already solved it with a segment tree, and after learning about treas i tried solving it with a treap but it TLEd on testcase 18

now my question is: aren't treaps on average Log(n)? if so ... shouldn't it pass where segment tree did with complexity of stable Log(n)?

here's my treap code for reference for maybe the error is in my implementation

Hello there

I'm trying to solve this problem with this code

Now what I'm doing is building a segment tree with a treap in each node that keeps the position of the next equal number in the array for every number in range

after numerous WAs i got TL and while testing my code on extreme cases i found out it really does take a very long time to execute for 50000 ... the extreme case

My code's complexity is supposedly N*log^2(N) which should be fast for this size of input

what am i doing that's so slow ??

please help :/

UPDATE ::

I used a different approach for insertion and deletion on treaps where if a node already exists i only increase its value instead of inserting a another node

that got the runtime to around 14 seconds on the extreme testcase that never ended with my previous code

but it's still too much for O(nlog^2n) complexity ...

what am i doing wrong and if that's not the way what is ???

here's my current code

Hello there

I'm trying to solve this problem with this code

I'm using a segment tree with a treap in each node and the trick from this blog

I keep getting WA on testcase 20 and i have rewritten the code a few times and debugged for hours looking for the reason

If anyone could find my error that would be really appreciated

Hello there

I'm trying to learn treaps and I've been stuck for a while trying to figure out how merge and split functions work

and I've read somewhere that reverse operations on arrays can be done using treaps

any help explaining these topics would be appreciated :D

Hello there

I'm trying to solve this problem but i can't seem to find the proper approach

I wasn't able to see the editorial's point of view either

if someone would kindly help me find a way to solve it that would be really appreciated!

Hello there

I'm trying to solve this problem

So i was thinking if i create a segment tree where each node has a segment tree that would do the trick

I've heard about 2D segment tree before but never implemented it

the only way i could think off would definitely get me MLE where i do an array seg[n*2][n*2]

if anybody has any tricks that could save memory or maybe the correct way for creatin a 2D segment tree that would be really appreciated :D

Hello There

I'm trying to solve this Problem using a persistent segment tree

I keep getting TLE for reasons i can't find

If anyone would so kindly explain the reason behind the memory leak it would be really appreciated

Here is my code

Hello there

I'm trying to solve this problem

I'm keeping a persistent segment tree from end to begin for the cnt[] array which keeps the number of results of indexes so far

and then for each elemnt in array i query on the tree next to the number and get how many indexes with smaller results

Here is my submission

is 10^6 too much for a persistent segment tree, or am i doing something wrong ?

Thanks in advance :D

Hello there I've been reading up on MO's algorithm and sqrt decomposition and i think i've figured out the concept

so i'm trying to solve this problem but i keep getting TLE and i can't seem to figure out what i'm doing wrong

Here's my code

Thank you all in advance :D

Hello There I was reading this problem and i noticed that it could be solved with a persistent segment tree which hold multiple of children and every tree is based on the parent's tree

the problem is in this problem we have two types of queries... the second one being update

so i was wondering if updates on a persistent segment tree are possible in log(n) ?

the way i see it updating a certain tree means i have to update all the trees based on it which could lead to linear time...any opinions ??

Hello There

I've been trying to solve this problem for a couple of days now and have no idea why it keeps getting WA

Here is my code

What I'm doing is compressing coordinated and using segment tree to see for each poster if the range has any non covered area, this works because I'm going from last to first poster

Here's to hoping someone finds where I'm wrong :)