LashaBukhnikashvili's blog

USACO 2012 Nov. Contest
By LashaBukhnikashvili, 12 years ago, In English

The USACO 2012 November contest is available November 16 through November 19.Good Luck to everyone!!!

UPD: Contest complete.Results will be posted within a day or two.

UPD: Results here.

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

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can you please give me the link to the contest gateway.. I cannot find it..Thank You.

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

    USACO & USACO CONTESTS

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

      I know these page.. What I wanted is the link where I will find problems and submit solutions . It used to be [link] before but I think they have switched from it.

      Edit : They have updated it here

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        The USACO admins will publish the link to the November contest gateway when the contest starts. The contest hasn't started yet.

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

        Please note — it will start in 4.5 hours

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

.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    .

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

    Starting from November 16 until November 19 you can choose any time , that is convenient for you and participate in a contest.

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

ссылку?

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

Link to the list of contests

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

For all those who have problems with finding link..

Go to this link , then login, and there are the problems ^^

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

I would not recommend to start now as it seems last task lacks input/output definitions and files

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

just I wrote contest and results why not?

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

    Results will be announced by the end of next week

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

Pretty balanced problems in Gold division :)

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

Let's discuss the problems. I wonder what is the solution for the second and the third one in Gold division.

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

    Second problem: Let's imagine that we have only one string. It is easy problem. For solving it we'll iterate our right edge of segment and summing number or indexes which have balance equals to current one and between them there is no such indexes i, that: balance[i]<balance[right]. Our problem is identical to this one. We only have to encode all balances of each column with some number. It can be done by using hashes or some tricky maps.

    Third problem: I only came up with solution with complexity O(n^2). But at contest I submitted another one, with O(n^3*log(n)).

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

    Another solution for second problem: if we have only one string, then for each closing bracket we can count the number of correct bracket sequences ending there(it's rather obvious how to do it), answer is sum of all these values. If we have multiple strings, we choose one of them and just use our algo for one string, the only difference is that when we look at bracket matched with our closing bracket, we check that corresponding substrings in all given strings are correct bracket sequences and if any of them is not, then we discard this ending position.

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

      Ok, this solution is mainly like mine... But i also think, that its time complexity is O(n^2 * k), isn't it?

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

        Well, i guess you check substrings for correctness in linear time, don't you? But there is a simple O(n) preprocessing that allows you to check if any substring of a given string is correct bracket sequence in O(1).

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

          No, its's not true, i check correctness of one substring in O(1), but i also think, that in every string of brackets there are potentially n^2 substrings, aren't they? And for each of these substring you have to check all other strings...

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

            Ok, full solution looks as follows: we maintain values endi — number of correct substrings(correct substring means that all corresponding substrings are correct) ending at position i, also for one chosen string we calculate opi — position of matching opening bracket for closing bracket at position i or -1 if it doesn't exist. Then,

            for i = 0 to n - 1 {
  if op[i] = -1
    continue
  if in some string substring (op[i], i) is not correct
    continue
  end[i] = end[op[i] - 1] + 1
  ans += end[i]
}
            → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      This solution is totally wrong by the way :D

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

It will be rather disappointing if the intended solution to the third problem is brute-force with a set of optimizations. Could anyone suggest anything better?

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

    I hope it is;)

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

      I have no doubt that a lot of quadratic-looking solutions will get full score on this problem, USACO usually have about 10-15 test cases for a single problem. But it will be also nice to see something with better complexity.

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

    There is O(n) solution — for each vertex and each incident edge let count maximum "open" balance of a path ending in this vertex through this edge and maximum "close" balance of a path starting in other end of this edge. It is fairly straightforward to do in O(n^2), there is well known trick how to do this in O(n). Then answer is maximum for vertice v of maximum for edges e1, e2, incident to v of minimum open(v, e1), close(v, e2)

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

      Could you please provide any other links of this trick? like problems or examples?

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

Results ready on RESULTS USACO NOVEMBER 2012

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

    Do you know how the score is calculated? Is it something like NumberOfSolvedCases/NumberOfTestcases * 1000?

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

      I think that they use this formula.

      → Reply