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

Автор wilcot, история, 7 лет назад, По-английски

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

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

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

L: We construct tree greedy , then solve problem with centroid-decomposition code: https://ideone.com/kzZmuP

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

L: Once we have the shortest paths tree, computing the answer can be done using centroid decomposition.

The tree can be computed with Dijkstra's algorithm, modified to prefer parents with a smaller path from the root (with respect to the lexicographical order). Checking if a path is smaller can be done with binary lifting, in a way similar to the computation of LCAs.

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

    You can build tree without comparing pathes. After Dijkstra algorithm you can use DFS using only edges related to some shortest path, one thing you need before DFS is to sort edges by destination.

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

H. Let p = x - y, q = y - z, r = z - 1. Then, in pqr-space, a subhill is of the form p ≥ const, q ≥ const, r ≥ const, p + q + r ≤ const.

Fix the value of p + q + r (try all O(N) possibilities). Now the task is a standard 3D-sum problem. In total it works in O(N4).

I believe it's also possible to solve it in O(N3) but looks quite messy.

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

H: Let's split each 3d update/query into <=100 2d updates/queries. For fixed y, we get update/query on some rectangle. First do all updates using inclusion/exclusion (adding +-1 to points (X,Z) to denote adding +-1 to all x>=X, Z>=z and then taking partial sums to find value at position (x,z)); now you can answer each 2d sum query in O(1) using partial sums once again.

K: Kind of divide-and-conquer. Let's assume that each query contains element n/2. In this case we can calculate dp for each suffix of the left part of the array and for each prefix of the right part; now in order to answer a query you can combine corresponding suffix of first part and prefix of second part in O(D). Now we are left with queries which are completely contained within left or right subarray; OK — let's solve them recursively. That gives us O(D * M) to answer all queries and O(N * D * logN) to calculate all DP values at each level of recursion.

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

Is there any new upsolving? When I access upsolving system, the last problem is old -> "O-17 Sphenic Numbers".

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

    Can you give the links of old problems? I don't understand what is Grand Prix. I see blog of its discussion on codeforces but there is no link to the actual problems. Is it a private contest?

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

      It is private, but very good contest. Site is p̶r̶i̶v̶a̶t̶e̶c̶u̶p̶.̶r̶u̶ opencup.ru You can participate if you are registered in team, and your coordinator (in my case he is a lecturer in my university) gave you credentials.

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

      Yes, it's a private series of ACM ICPC-style contests called Open Cup (website is in Russian only). Problems are private, participation is restricted to "sectors" only (it's basically a multi-site contest).

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

    Finally, upsolving have apear!

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

Where can i find problems?

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

F?

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

B?

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

    Find the rightmost '(' that can be paired with some ')' in the range, and the leftmost ')' that can be paired with it, and remove them.

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

D?

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

    We can get digit D as answer if all non-null digits in N are not less than D and all digits after first occurence of D in N are equal to 9. Find the biggest D we can get.

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

    Lets compare digits by parameter 'how much this digit meets in the range 1..N'. How to make this comparator: The base observation is an each digit meets equal amount of times in numbers in the range 1..10^x-1. So lets process digits of number N from left to right, suppose current digit is X, there are three cases (suppose lhs < rhs):

    1. if x > rhs or x < lhs just continue, because it means that lhs and rhs occured equal times in numbers, in numbers with this prefix.
    2. if x == lhs, than lhs is better
    3. if x == rhs, than lhs is better, excluding the case if remaining suffix contains only '9', in this case we should just continue as we did in the first case.

    If lhs not better than lhs, we can take rhs. So as result we can find maximum D where D have the same amount occurences as 1.

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

Does anybody know when (approximately) contest will be unfrozen? Just curious.

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

Вброшу немного:

1) Ребята, очень у вас агрессивный кеш в таблице результатов до сих пор. Она отставала на 1/4 на несколько десятков минут, на опенкапах на 10-20 минут стабильно. Приходится смотреть ее на главной opencup'а, там она гораздо свежее. Сегодня плюс она во времени у нас прыгала на несколько часов иногда.

2) Я на 1/8 еще баг сдал, до сих пор не поправили: вы компилируете и запускаете на разных машинах. С этими pragma'ми почти любой исходник получает RE:

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx,tune=native")

Это очень грустно, потому что не получится написать такой код: "если платформа поддерживает SSE/AVX, используй нужную инструкцию".

Пример посылки: #5461274

3) Нельзя ли компилятор обновить еще? Либо, хотя бы, c++14 разрешить на опенкапах посылать. На 1/8 и 1/4 такая возможность была, сейчас ее нет.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    1. тормоза с четверти уже почти починены, а вот агрессивное кеширование увидели только сегодня, изучим.

    2. Конечно на разных машинах, одна машина не справилась бы с нагрузкой пользователей. Все компы одинаково поддерживают/не поддерживают определенные инструкции. Главное же воспроизводимость? Продолжим в обратной связи контеста?

    3. А вот выбор компилятора всегда лежит на авторе соревнования.

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

Problem A is copied from this one.

And I think problem F is also copied from problems of Multi-University Training Contest in China. In my mind, I have solved this problem before.

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

how to solve C??

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

    Consider all 4! permutations, after left,right,top,bottom fixed, you can fix horizontal & vertical offsets between left & right. After that you can find answer using dp (hint: for fixed horizontal offset precalc cnt[i][j] for top/bottom strings — count positions p, that s[p]=i and s[p+offset]=j).