speedy03's blog

The USACO 2015 February contest

By speedy03, 9 years ago, In English

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/

  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (47)
| Write comment?
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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".

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

4 hours left! Hurry up if you haven't participated yet.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest finally over?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Link to problem(s)?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Really? Why am I missing those things :@

      Thank you very much! :)

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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);

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    const int MXN = (int)1e6 + 200;

    you must change it to

    const int MXN = (int)2e6 + 200;
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

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

      If it is not hard, please explain why!

      → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I reached GOLD DIVISION :))
Congrats to everyone.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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 .

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    horse > monkey

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

        → Reply