Блог пользователя LashaBukhnikashvili

Автор LashaBukhnikashvili, 12 лет назад, перевод, По-русски

Контест доступен с 16 по 19 ноября 2012 года. Участие открытое, 3 дивизиона.всем удачи!

UPD: Контест окончен.Результаты будут опубликованы один или два дня спустя.

UPD: Результаты здесь.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

ссылку?

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

For all those who have problems with finding link..

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

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

just I wrote contest and results why not?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать b и c в bronze div ?

»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Pretty balanced problems in Gold division :)

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Никогда до этого не приходилось писать USACO в последние сроки, поэтому хочу уточнить — вот таймер Open for считает до 20.11 11:59 UTC, при этом написано — "as long as you start during the larger contest window ... ending Nov 19 at 23:59 UTC-12 time". То есть — если я начну писать скажем 20.11 11:00 UTC, то у меня будет время 11:00 — 14:00 или 11:00 — 12:00?

Если первое, то тогда надо заметить, что контест заканчивается в 15:00 UTC, а не в 12:00 UTC, и только тогда можно обсуждать задачи. Если такая система на USACO была всегда, то теперь я кажется понимаю почему тесты и резалты выкладывали где-то спустя 3.5 часа после "конца" соревнований.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Результаты, кажется, обычно в четверг-пятниицу появляются, если не позже.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я имел ввиду личные результаты. Которые года 2 назад таки появлялись во вторник, только они были предварительные. Не знаю как теперь.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, это ж еще при Колстаде было. Хз, почему сейчас убрали эту замечательную рассылку...:(

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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]
            }
            
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      This solution is totally wrong by the way :D

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Как решать B в bronze?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I hope it is;)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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