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

Автор NALP, 14 лет назад, По-русски
Доброго времени суток всем.

В этот чудесный летний день приглашаю вас принять участие в Codeforces Beta Round #19. Сегодня авторами задач для Вас буду я и Артем Рахов.

Также выражаю благодарность всем, кто помогает нам в организации этого соревнования: Михаилу Мирзаянову, Эдварду Давтяну  и Юлии Сатушиной.

Надеюсь, что вам понравится.
Всем успехов!

P.S. После начала соревнования вы сможете скачать условия на русском и на английском языках.

UPD. Контест окончен, всем спасибо за участие. Поздравляем победителя, единственного участника, который решил все предложенные задачи - kalinov
Вы можете посмотреть результаты и задачи.
  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Если я правильно понял, дополнительные копии условий выложены на случай если сайт упадёт. Но если он таки упадёт - никто не узнает адреса ( по крайней мере на первых порах). Мне кажется, на будующее будет неплохой идеей дать возможность учасникам заранее скачать архив с условием, а потом выложить где-то ( к примеру, там же) пароль к архиву.
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Новый рекорд по количеству участников
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это же только зарегистрированных, а в результатах -- количество принявших участие. Разве не так?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да так, и все таки это рекорд по кол-ву зарегавшихся, даль что ниже психологической границы - 1000.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I just missed registration, could you allow us to register just for a couple more minutes, please?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
To late... The contest started.. Ohhh...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I can't log in. They are saying about a broken link just as I try to enter the contest :(

Can anybody help, please!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что из себя тест 46 по задаче E представляет?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Цикл из 9999 ребер + одно рандомное ребро
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      рандомное ребро внутрь или наружу? В любом случае я не понимаю, почему у меня там WA...
14 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
I don't like this contest at all. Second task shouldn't be dynamic programming.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good problems. I'm using hashing on C, but still get TLE on test 21.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
with KMP i guess ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    No :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Well, main trick - it is not string problem :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I used Suffix Arrays, Longest Common Prefix and Range Minimum Query to solve this problem.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      i've find all intervals between all same digits, then sort it, and just moved the left border of string
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Yes, that part is the same in my solution, but I used all that stuff to get the intervals. I suppose there is an easier way.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      It is ok to use map as hashing,since n is no so large(<10^5).
      And because each number occurs at most 10 times,record the nearest position of number a[i] after position i,then you can use an optimal brute force to find the shortest repeat length s_rep[i] that begins at i.
      So the rest is just a loop.
      But this seems not a good solution.Are there any better solution?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        I did something similiar, for each pair of equal numbers, see if there is a repetition beginning at the first with the second at the middle. To check that all the interval numbers are equal, I used suffix array and RMQ to do that in O(1).
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Yep,if each number occurs arbitrary times,my solution will absolutely TLE.And your solution can be implement in O(n).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин... Обидно, поздновато допер до 2 задачи... Минут бы на 10 пораньше...
Ну ладно, зато из 2 дивизиона легче выбираться)))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А когда будет разбор задач?
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Thanks for the great contest! Problem A is a typical implementation problem. Problem B is simple but not really obvious DP. Problem C is a very interesting problem with a lot of ways to solve it.
Well, I've solved problem C without hashing. Also, I didn't use KMP or Z-function. DP is the answer :) Lots of memory to store everything I need, lots of precalc operations and AC as a result. Was really pleasured to solve this problem.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Well, maybe my solution is not the most popular one. So I should better describe it.
    Possibly I wasn't correct when I said that I didn't use Z-function. I didn't use the typical linear algorithm to find classic Z-function. The idea was to find for two given positions X and Y the length of the longest string starting from this positions.
    I've used classic DP(X, Y) to find a value of DP-function. But it is no use to store the value of DP-function for any values of X and Y. We should store it only for positions with the same letter. It's mentioned in the statement that the number of such positions is strongly limited.
    Then it's quite obvious how to use the value of DP-function to solve this problem in O(N) time.
14 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
@admin , can u provide me the testcase file for problemA?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

no delete option....i clicked so many times..as my internet is slow...

but there should be delete option..   :?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good contest! I had a lot of fun solving problem B :-)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто-нибудь рассказать, как решать задачу D?
14 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
I didn't use neither Suffix Arrays nor hashing, nor DP. I've just stored all distances between equal numbers and then performed exactly the same thing that is written in the statement, i.e. tried to remove repeats in the increasing order of their lengths. The main observation is that the distance between the numbers from the first half of the repeat and the respective numbers from the second half remains unchanged.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can anyone show me a good method to solve Problem E ? my alg is O(m*m), but sill TLE.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Well, if you look at standings you can easily understand that O(m*m) will definitely fail, since a lot of people have TLE. It can be solved faster. The main observation is that if the required edges exist then there is an odd cycle and all edges in answer belong to this cycle. So the first thing to do is to find some odd cycle with DFS. Then you can delete this cycle from graph. If the resulting graph is not biparate, then answer is zero. Otherwise you can run dfs from each of the nodes on cycle marking the colors of nodes. The goal is to understand which cycle nodes have the same color and which opposite. So, you will get some statements like "Nodes x and y of cycle have the same color" or "Nodes x and y of cycle have the opposite color". Obviously each statement is equivalent to statement "Edge to be removed is on segment [x,y] of cycle" or "Edge to be removed is on segment [y,x] of cycle" (depending on (y - x) % 2). Number of statements is linear because they are generated by DFS, so we have problem to find which cycle edges are on all generated segments of cycle, this problem can be solved by usual methods (sorting etc.). I don't know if this problem can be solved in a less complicated way, but even this solution can be coded on contest.
    PS: sorry for my terrible english.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    There is an O(n+m) solution based on DFS graph analysis.

    Run a DFS to create a DFS forest. For each node x let color(x) be depth(x) mod 2.

    Now, the only edges that could violate this coloring are back-edges in this DFS forest. 

    If colors on two endpoints of a back-edge are the same, we call this back-edge BAD. Otherwise we call it GOOD.

    If there are no BAD back-edges at all then the graph is bipartite and you have to output each edge and we're done.

    If there is exactly 1 BAD back-edge then that back-edge is a part of solution because removing it causes the resulting graph to be bipartite. However, if there are more than 1 BAD back-edge then none of them is in the solution.

    Now we covered back-edges, but what about tree-edges.

    Observe a tree-edge u--v such that u is a parent of v in a DFS tree, and imagine that we swap colors for each node in a subtree rooted in v. 

    Obviously a tree-edge u--v is now invalid and has to be removed, but some of the back-edges have also changed states. If a BAD back-edge led from a node in a subtree rooted in v to a node higher than v, then that edge became GOOD back-edge and vice versa.

    So a tree-edge is a part of solution if all BAD back-edges in the graph and none OK back-edges connect a node from a subtree rooted in v with a node in the rest of the graph.

    It's possible to keep track the number of such BAD and GOOD back-edges as you do the DFS. For each node add-up back-edges from it's children, add back-edges that go from the node up the tree and subtract back-edges that go down the tree.

    That's it. I hope it helps.

    I liked the problemset too, especially this problem. Thanks to problemsetters!
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Люди добрые напишите разбор пожалуйста
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    написать разбор может только один человек, который все решил. 
    тогда "добрый человек напиши разбор пожалуйста".
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Или тот, кто придумал задачи ;)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      И он не русскоговорящий, так что этот вопрос надо задавать на другом языке. 
      Или реально напиши в личку Артему Рахову или Коле Кузнецову
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Problem -A
I am getting WA. I am not able to sort the "teams" properly . Though in the below code i have used sorting using #3 defined basis.

My  
<A HREF="http://ideone.com/djbUe">Code</A> 
is here. Can anyone tell where i am wrong.
Thanks for ur response.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
sorry  the link i provided for my code is
http://ideone.com/djbUe
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Around lines 126-127... Shouldn't you be swapping v2 and v3 as well? You want to make sure all the data stays together. Every time you swap two teams, you'll want to swap team, v, v2, and v3.

    A few notes... if you use a structure that has all of this data, you won't have to worry about only swapping parts of the data. Also, if you use a built-in sorting method, it'll run in O(n log n) rather than the O(n^2) sort you have here, and it'll take you less time to code.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem C is wonderful!
For 2 same letter Ai and Aj(i < j) , we call it a "match":
M[i].x = j - i , M[i].start = i.
It can be found that there are no more than 10N "match"s.
We sort them by x first , if equal , by start.
And just to consider each match and keep the left-bound.
If there are some i that:
for all i <= j <= i + u - 1 , M[j].x = u , M[j].start = M[j-1].start + 1
and M[j] >= left-bound
We make the left-bound to i + u - 1 + u.
The algorithm is O(10NlogN).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
somebody can explain me what exactly does
" in decreasing order of the diference between scored and missed goals "
means?

I don't understand what missed goals are you refering to. .
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone explain how to solve B?
I´ve seen, that it is a DP problem with N*N state space, but what exactly is the state and what is the dynamic optimality of the problem?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    dp[m][s] = the minimal cost of a subset of items that you choose among the first m items so that the sum of (t_i+1) >= s (here i runs over the indices of the chosen items).
    The answer is dp[n][n]
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Thanks, this looks logical once you´ve stated it.
      It still seems, however, somewhat unobvious (or rather indirect). Quite a lot of people solved it during the contest, I´ve spent about 1.5 hours without success.
      How did you come up with it during the contest? Could you, please, describe your thought process? (I´m trying to fix mine) :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Yeah, me too, I often fail on this kind of DP. can someone change our thought process. Thx
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        My thought process was something like this:

        OK, this looks like DP or greedy. It's problem B so it might be greedy.

        How should I sort items? Should I always pay for the cheapest item? No, doesn't work. Should I pay for the item with largest time? No. What about items with t=0. 

        Well, I guess it isn't greedy.

        How would I write a recursive solution?

        For each item I should either pay for it or steal it. If I pay for it then I can steal some other items. Yeah, state should definitely contain the position in sequence and the sum of ti. 

        Well I guess that's it, I just keep track of amount of items I have bought and the amount of items I can steal. In fact if I add 1 to each ti then it's even simpler.

        That's it, more or less. It's hard to recall and describe exactly. 

        A lot of experience with DP and memoization helps ofcourse, but I think the best advice is to write or think about writing a simple recursive brute force solution and then figure what the state is.

        When thinking about recursive solution you should try to make it as iterative as possible, that is scan elements in order and decide what to do with it.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Very nice, thanks.
          Knowing how successful contestants approach the problems is both interesting in itself and educating as well. I thinks it´s underrated as a means of teaching:)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Can you explain your solution for problem D too?
          Thanks in advance.
          • 14 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            Collect points from add and remove commands and sort them first by x and break ties by y.

            Each point in a sequence can be active or inactive, and initially every point is  inactive.

            For each query "find x y" we have to find the first (because of the way we sorted the sequence) active point P in this sequence such that P.x > x and P.y > y

            To maintain this sequence we have to build interval tree on it. For each interval we keep track of the largest y of all active points in the interval. If there is no active point in the interval than this value is -inf.

            Updates (add and remove) are quite simple, just find the point in the sequence and update the value of the leaf (value becomes P.y on add commands or -inf on remove commands) and then go up the tree and update the value as a maximum of two children nodes.

            Find x0, y0 command is also quite simple, but it might not be so easy to understand why is it O(log n).

            Start from the root and do the following recursively:
            If the x coordinate of the rightmost point in the interval represented by this node is not greater than x0 then none of the points in the interval are good and so we cut this branch.
            If the topmost point in the interval represented by this node is not greater than y0 then none of the points in the interval are good and so we cut this branch.

            Search for a solution in the left branch.
            If no solution is found then search for a solution in the right branch.

            My source code for further details.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
       why t_i + 1, why not ti?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        because we also get item we bought
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          so what is the s mean?
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Number of items we stealed or bought
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              so dp[m][s] means in the first m items, (m - s) iteams can't be decide to be bought or stealed.
              and but what is the  transfer equation is? i can't write it.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              yes, i know, every bought item can count (t_i + 1) item, so the dp[m][s] means buy some items in first m items, the transfer equation is: dp[m][s] generate dp[m + 1][s] and dp[m + 1][s + t_i+1] + c_i.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Let M be the set of items we choose to pay for; then we need n-|M| seconds to steal other items; it means that sum of t_i >= n-|M|, that is, sum of (t_i+1) >= n.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
As of problem B, printf("%lld\n", ans); fails in test case 11.
But cout << ans << endl; is accepted.

I'm new at codeforces and don't know why printf("%lld") failed.
Do you know why?