14438156

My code gives the answer right on my linux(ubuntu) computer but it fails at system testing. I believe it's something about vectors I use in the code (ans,tem) but I could not find the exact reason. Any ideas? (Also it could be nice if someone tests the code. Maybe it will fail on other computers as well. Who knows?)

EDT: Problem solved

525E - Anya and Cubes

On this problem before accessing an element in a map checking if the element is contained or not makes program faster. It doesnt make sense to me. Isnt both log(n) comp? Or is there an exception on accessing elements which are not in container?

TLE: 10498148

AC: 10498342

I only changed that part between these.

Also can someone tell how to use unordered map or give a code using it? Or any type of hashmap implementation i can use in c++.

UPD: It looks like when you use [] operator you create a node so tree size grows each time. Thanks for help everybody.

113B - Petr#

I know limits are big and no suffix array implementation is needed but i am trying to learn about S.A. so it would be nice if someone could help me about this problem.

My idea about the problem is finding each occurrence of the end string and mark these in a array with a 1. Then prefix sum that array for range sum queries. After that on the suffix array of t+'#'+Sbegin iterate over the sorted suffixes which have Sbegin as a prefix to find how many times Send occurs after beginning of each one(using the prefix sum thingy) and use lcp for not counting re-occurrences. I am not sure if this works but i have tried to code this and it failed on test case 24. It might have bugs i am new at S.A. coding. 10309125

Is it possible to solve this problem this way or with Suffix Array? (I didnt used counting sort but with counting sort this should have O(nlogn) complexity.)

516D - Drazil и утренняя зарядка

Hello everyone. I really need some help with this question. I have implemented 3 different solutions. And if there is a logical mistake in them i am ready to code another one from beginning so i will appreciate any kind of help. At each one of them my code calculates the far array from tutorial. That part is same in all of them.

1) 9946947

On this one i used maps for each node. This one having TLE(unfortunately) but at least i know the far array is correct because this code passed some cases.

2) 9946947

This one calculates when should nodes get popped out from groups with a binary search on a stack as said in tutorial. Then while in dfs3 function it increases a point for the node we find on binary search. And it sums all return values of each child adds one and decreases sum by the point of that node(because we are in the point where some nodes should be kicked out and for that nodes we added a point in this node). And the answer is the biggest return value it have found while dfs. This one gets WA but gives the same answer with the next one so i think they have a common mistake in a way.

3) 9969062

This one uses a segment tree on the tree we have using discovery and finish times. At each node of segment tree there is a sorted vector so i can binary search the number of the nodes which have far value lesser then far[root]+l. As i said this one gives the same output with the previous one so i think there is something common but only thing they have common is calculating the far array and that part must be correct(??) because of the first code. It might be about long long thats the only theory i have right now.

TL;DR: You can ignore the submissions if you want and give me another way to solve this problem.

Thanks!

I love the sense of humour in this sample test!!! Tell us your hack inputs. Mine was:

2

hacked

hack

the problem = http://usaco.org/index.php?page=viewproblem2&cpid=213

i am trying to implement the second idea on the analysis (the one with heaps).

analysis: http://usaco.org/current/data/sol_runaway.html

my code: http://ideone.com/2bjocS It is having segmantation fault on the tests 5 to 10. Array sizes are right and i have no idea why couldt it be having segment. Is it about recursion stack limit or something? Please help me out.

Is there any good explanation for the idea behind finding max area sub-rectangle in a histogram problem? And some tasks involving the same idea. It seems to be used in much harder problems as a sub-problem and i am having hard time about it.

Can someone expain the ofiical editorial or give me another solution. I cant understand how editorial code finds reoccurances on prefix arrays. Problem: http://usaco.org/index.php?page=viewproblem2&cpid=194