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
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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
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
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 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 :)
Name |
---|