The USACO 2015 February contest is available from February 20 through February 23. The contest is 4 hours in length, and can be taken any time during the larger contest window. More info: http://usaco.org/

Before contest

Codeforces Round 940 (Div. 2) and CodeCraft-23

10:00:58

Register now »

Codeforces Round 940 (Div. 2) and CodeCraft-23

10:00:58

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 150 |

7 | SecondThread | 150 |

9 | orz | 146 |

10 | pajenegod | 145 |

The USACO 2015 February contest is available from February 20 through February 23. The contest is 4 hours in length, and can be taken any time during the larger contest window. More info: http://usaco.org/

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2024 07:34:03 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

what does it mean "File name may only have alphanumeric characters, underscores (_) and periods (.)"? It is the first time I use C++ in an USACO contest?

Those rules are describing the source file that you submit. In particular you can name your solution things like "my solution.cpp", "naïve.cpp", "n^2.cpp".

4 hours left!Hurry up if you haven't participated yet.Is the contest finally over?

Yes we can discuss the problems now

I wish they'd return the old system with testing only after the contest, it was like the only competition besides COCI held this way(does COCI use this system now btw?), but COCIs aren't virtual and they often have ridiculous time limits for Java.

If they could also show your results right after your 4 hours(not 2 days after everyone finished), that'd be just perfect!

Well, I believe USACO's main goal is selection and training for IOI and IOI has full feedback, so their decision was quite logical.

Anything regarding results ? It's been 4 hours since the contest finished, but no news of results on the website...

They said the results would be out shortly after contest.

Usually it takes a day or two :)

Can anyone give me some hints on the second and third problem (Gold division, "censor" and "fencing") ?

For the second one you need an algorithm for multiple pattern matching (I used Aho Corasick)

I haven't known that algorithm. If that is the official solution, I had no chance in this contest.

For censor, you can precompute the hashes for each substring of the N censored words. Then when doing the deletion, you can maintain pointers so that you can recompute hashes. I didn't do this during the contest, I did a KMP which received 12/15

I used KMP+stack and get full point on censor (silver division)

Third problem can be solved using sqrt decomposition:

1) we should group all requests to about sqrt(n) groups,

2) before processing each group we should build convex hull with O(n) time (all points we can sort before processing requests),

3) before processing each group we should sort all lines by angle and process them with convex hull with pointers,

4) and finally for each line we should process new points from block of requests.

So solution has O(n sqrt(n) + n log(n)) complexity.

Hey! Can anybody explain the solutions for Silver 1 and 3 or give me some hints, please? For the first one I'm using hash to find a match and then I am deleting it in O(N). I thought about speeding the deleting operation up with segment tree but there was no time for implementing it. I've got 11/15 in total. After the contest a friend of mine told me that the idea with segment tree didn't help him. For the third problem I just use the brute-force solution. I tried to simulate the process 10000 times, every time taking two random teams but this received only 1/10(as the brute-force solution).

Update:Problem 1, Problem 3.Link to problem(s)?

For problem 3, consider the complete graph where the nodes are the teams and the edges are the potential scores if they play a game. Our result must be a subset of the edges of this graph. Notice that because after each game a team is eliminated, there cannot be a cycle in our subset so our subset is actually a tree (no cycles and every node), to get the maximum result just implement a maximum spanning tree algorithm on the graph.

Really? Why am I missing those things :@

Thank you very much! :)

For Silver 3, represent each team as a vertex. Then each edge represents a possible match, with the weight equal to the number of points scored. Note that every elimination tournament can be represented as a tree. The problem is now finding the maximal spanning tree.

Thank you too!

Silver division HINT:

1st problem: KMP+stack; complexity=O(|S|+|T|); memory=O(|S|+|T|);

2nd problem: DP; complexity=O((K+R^2)*C); memory=O(R*C); (Alternative solution: DP; complexity=O(R*C); memory=O((K+R)*C))

3rd problem: MST+prim; complexity=O(N^2); memory=O(N);

On problem 2 how do you do dp in O(R*C)?

It's just partial sum version of O((K+R^2)*C) DP so we can query sum of result from (0,0) to (i-1,j-1) with specific label or all label in O(1) time. 2D partial sum table size is actually R*C*K but we can reduce the table size to just C*K.

It's O(R*C) by assuming all DP table has been initialized to zero at program start. otherwise it's O((K+R)*C).

I solved the 1st problem using a linked list to store the text, and deleted each instance of S.

1) Are you silver?

2) Did you receive 15/15?

If the answer of those questions is yes, then I will feel really sad :D :D :D

I was silver and i received 15/15 with hash and linked list

Same here.

Results are out ! http://usaco.org/index.php?page=feb15results

Can someone check my code to Censoring(Silver) please!

It gives RE at 3 tests. I can't figure out where is mistake.

you must change it to

Thanks!

But I don't understand how my solution exceed bound of array.

If it is not hard, please explain why!

How have you solved Cow Hopscotch (Gold)?

My solution was

O(NMlogNM) but it used a treap and worked for 1984 ms (actually, it passed only after I 'd overloaded operator new).my solution was O(nmlgm).

I used fenwick for every a[i][j]. (I push indices of columns that have at least on square have a[i][j]), then a dp solve problem.

maximum time is 300 ms.

Alia, can I take a look at your implementation? Maybe with some elaborations please. I had a hard time understanding the official solution.

Finally I reached

GOLD DIVISION:))Congrats to everyone.

Guys, can anybody provide his code for Silver 1 using stack + KMP, please? I have tried for days, but I can't come up with a solution even if I know what I have to use.

here u go :) http://pastebin.com/bQvE4qFY

Got it, thank you so much!!!

Problem Censoring(Gold). My code getting RTE at test 8 ( Only at test 8 ). are there anyone knows why or facing with the same . Here is my code .

Your code is too awful because you wrote code by define.Primarily you will write code normal and ask again . Thank you for downvotes

thank you very much :D

horse > monkey

If anyone still monitors this thread, can you please tell me why my solution to Silver problem one (http://usaco.org/index.php?page=viewproblem2&cpid=529) times out a lot? Here is my code: http://pastebin.com/nUjySfMf I used the KMP algorithm with java, and I'm also removing at constant time.

Upon deletion, you are going back S.length() spaces and researching. At the worst case it's still O(TS). You need to find a way to memoize so that you don't have to go back S.length() spaces.

Sorry, can you tell me what S is and where in my code I go back S.length spaces after deletion? Thanks.

Oh on second glance, it would seem that it is linear time. It's probably because Java is way too slow. My code in C++ passes in 40 ms (at worst).