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

Автор Bidhan, 10 лет назад, По-английски

The round statistics are nicely put by DmitriyH.

427A - Police Recruits ( Author : Bidhan )

Maintain a variable, sum. Initially sum=0, it keeps the number of currently free police officers. With every recruitment operation, add the number of officers recruited at that time to sum. When a crime occurs, if sum > 0 then decrease the number of free officers by one, otherwise no officers are free so the crime will go untreated.

Model solution : 6546268

427B - Prison Transfer ( Author : Bidhan )

The severity of crimes form an integer sequence. Find all the contiguous sequences without any integer greater than t. If the length of any sequence is L, then we can choose c prisoners from them in L - c + 1 ways.

Model solution : 6546272

427C - Checkposts ( Author : Bidhan )

Find the strongly connected components of the graph. From each component we need to choose a node with the lowest cost. If there are more than one nodes with lowest cost, then there are more than one way to choose node from this component.

Model solution : 6546275

427D - Match & Catch ( Author : msh_shiplu )

O(n2) dynamic programming solution : Calculate the longest common prefix ( LCP ) for each index of s1 with each index of s2. Then, calculate LCP for each index of s1 with all the other indexes of it's own ( s1 ). Do the same for s2. Now from precalculated values, you can easily check the length of the shortest unique substring starting from any of the indexes of s1 or s2. Suppose i is an index of s1 and j is an index of s2. Find the LCP for i and j. Now, the minimum of the length of LCP, length of shortest unique substring starting from i, length of shortest unique substring starting from j is the answer for i,j. Now we need to find the minimum answer from all possible i,j pair. This problem can also be solved in by suffix array and in O(n) using suffix automaton.

Model solution : 6546277

427E - Police Patrol ( Author : Bidhan )

Trying to place the police station on existing criminal locations is the best strategy. Calculate the cost from the leftmost criminal location, then sweep over the next locations. By doing some adjustments on the cost of the previous location will yield the cost of the current location.

Model solution : 6546283

Разбор задач Codeforces Round 244 (Div. 2)
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

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

Есть ли желающие рассказать, как найти сильносвязаные компоненты в задаче С?

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

      О, я это видел в курсе на курсере с Roughgarden'ом. Но чтобы сразу из головы его написать — не сообразил.

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

    Задаёшь сильносвязанный компонент состоящий из одной точки — начало, потом делаешь DFS и каждый раз, когда натыкаешься на точку в компоненте — добавляешь в компонент весь путь. Если после этого процесса остались точки — повторяешь для второго компонента.

    Но я провалил один из тестов, так что где-то логика (или реализация) подкачала.

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

427B — is it solvable in compiled languages without any tricks — straight search for max on each iteration? Or do we need to do some interval trees or something like that? Python solution times out.

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

    You just have to sum L — c + 1 to ans on each iteration that finds a value greater than t. The pseudocode:

    answer := 0
    L := 0
    for v in values do
      if v > t do:
        if L >= c do:
          answer := answer + L - c + 1
        end
        L := 0
      else do:
        L := L + 1
      end
    end
    
    // Test for last L
    if L >= c do:
      answer := answer + L - c + 1
    end
    

    By the way, I don't get what you mean by "without any tricks".

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

      Super. After first time-out I tried to figure our something like this, but not exactly — mine failed, most likely on situation when all numbers are equal. Hope tomorrow at CJ I will do better :)

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

      Without any tricks — meaning just taking max() of system. O(N^2) solution. The thing you showed — this is what I call "trick" :)

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

В Е еще можно было тернарник написать

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

    А разве нельзя на первом прогоне просто поотрезать куски слева и справа по (m) (сколько влезает в машину), пока не останется мало заключенных в центре, и уже центр прошерстить поосновательней? За крайними всё равно ездить и если убирать по m с каждой стороны, то общая дистация всегда будет расстояние между крайними умножить на два.

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

In fact at E you do not need to find the spot where you place the center. You can go with 2 pointers , one which comes from left and one from right and at every step add (a[right] — a[left]) * 2 to the solution. This is right because at each you go from the center once to right and return and then once to left and return.

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

    I did that solution, but it failed — probably some corner case. I'll investigate today. I think you should cut m items from each head and tail until you have just a few criminals left.

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

    There is also an elegant solution by Vladyslav that I could not understand. Any idea on how this works ?

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

      I didn't believe at first, but it seems that it is always best to place the police station at n/2 (0-based index) to minimize the overall distance. Nobik_Glem is making use of that fact.

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

      Vladyslav's solution is based on noticing that (one) best position to place the police station is on the [n/2]-th criminal's position. (I've tried to explain why in a comment below). I think DanAlex's 6533273 is more elegant.

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

Some elaboration on 427E would be very helpful. Could someone please explain the solution to me?

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

    My solution for E: If we simplify the problem for m = 1, then (one) best location is the [n/2]-th criminal's position (if n is even there are multiple best locations). If we move it by one point further from any direction, we would be farther from n/2 + n%2 criminals and closer to n/2 criminals..

    Does something change when m is higher? Not at all.. We want to collect the furthest criminals together (so the total distance we travel is smallest), so we just look at the positions 0, m, 2*m and n-1, n-1-m, n-1-2*m (until these two sequences cross each other) and so on and we solve the problem for these positions and m = 1.., so the solution is still the same..

    when we know the position of the police station it is easy to calculate the result. Even easier is to notice, that there is equal amount of points when we turn the car and start returning on the left and right from the police station and noticing that right — middle + middle — left == right — left, so we can calculate right — left for the interesting points (sequences 0, m, 2*m, ... for left and n-1, n-1-m, n-1-2*m, ... for right) until they meet..

    i think that the hint stated in this short editorial is actually for a harder version of this problem which does not occur on a straight line but on a tree, there we have to calculate "how many nodes am i getting closer to" and "how many am i getting farther from " by traversing this path for each path (using two DFS for example), calculating total distance from every node to root of the tree and then traverse through each path and re-calculate the total distance from it by looking at the pre-calculated information. On a straight-line we know how many nodes we are getting closer and farther from so we can minimize it (by placing the optimal position to the middle straight forward)

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

    My solution works with ternarySearch , in fact when you fix a point for example if x = -10^9 the answer is very huge , if x = 10^9 then the answer is very huge , then we can see a function that decrease first then increase.

    You can see Yeputon's picture.

    Tutorial for ternarySearch

    My solution

    In the contest my solution fails in test 10 because i have overflow in my variables lo , hi. I fix it and i got accepted.

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

      Do you have any proof (formal or informal) that the function will just decrease and then increase?

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

D можно сдать и бором, а в Е точка, куда ставить станцию это всегда a[(n + 1) / 2]. По крайней мере тесты такое решение прошло :)

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

    По-моему там целый диапазон, где можно ставить.

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

    Это правда потому что : стоим мы в искомой точке, теперь попробуем перейти на некоторое расстояние влево или вправо, если влево : то у нас справа больше вершин чем слева, значит мы ухудшим ответ, аналогично для перехода направо

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

Я новичок на сайте — тесты тут после соревнования дают скачивать или надо гадать, где ошибка?

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

    Дополнение — тест слишком длинный, не помещается в экране "Посылка"

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

I solved D in O(n^2) differently — for every suffix s of s1 one can calculate in O(n) the shortest prefix of s which appears in s1 and s2 only once. You do that by computing the shortest pref-suff tables for words s+#+s1 and s+#+s2 as if you wanted to search for s in those strings. If the desired prefix of s has length t then after some drawing it turns out that t is simply the smallest value appearing in both tables exactly one.

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

I have another way to solve 427B — Prison Transfer Let count the invalid value (a[i] > t) in first c numbers. Every time move to the right, we just need to check 2 numbers: the old number (the left most number of old segment) and the new number (the right most number of new segment). If invalid number is 0, that 's mean this segment is valid.

Sorry for my english, this is my AC solutions: http://codeforces.com/contest/427/submission/6526709

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

Can someone explain 427C ?

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

    Fist you have to learn Strongly Connected Components SCC

    Wiki

    There have two famous algorithm that solve :

    -Kosaraju Algorithm

    -Tarjan Algorithm

    MySolution (I used Tarjan)

    Knowing SCC then the solution is pretty easy , for every SCC choose the nodes with the min cost.

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

      Thank you but can you explain why do we need to go for SCC? and is tarjan is efficient than kosaraju?

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

        1.the definition of SCC is that for each pair of nodes x,y,there exist one path from u to v and a path from v to u,which is exactly the requirment of the problen. 2.asymptotically these two are equivalent in efficiency.while in practice,tarjan is faster and more space-saving than kosaraju。

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

Is 427C solvable by using Kosaraju's algo and color the vertices belonging to same SCC wit h some color? Or is there a better way to solve this? Please post a link also to your submissions. Thanks :)

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

D — easy O(n) suffix automaton solution. 6536429

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

    suffix automaton

    easy

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

    Thank you a lot for great clue. I think this was the only solution which worked for Python. I am still wrapping my head around the whole thing. It is not "easy" :) I finished course on Automata at Coursera website and I had previous exposure to Knuth–Morris–Pratt algorithm, so I think I was ready for the idea, but it is still difficult.

    This is solution in Python: 6546632

    Now I want to rewrite the whole thing as reasonably convenient class and add it to my toolbox. Thank you a lot!

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

      Could you share the parts of ideas of automaton solution? : ]

      BTW, are you sure your solution is also O(N)? I have spotted some sorting there.

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

        No, it's not O(N), I do have sorting. It is possible to avoid this sorting as was done in submission above (Bugman). As for description of algorithm — this comment is good:

        http://codeforces.com/blog/entry/12082#comment-168324

        I just implemented suffix automation (almost straight from the book). Actual solution part starts with line "best = 10e10"

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

    Can you explain how to solve this problem with suffix automaton?

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

      Here's how I solved it using Suffix Automaton. First construct the string $$$s = a +$$$ '@' $$$+ b$$$, ($$$a$$$ and $$$b$$$ are the input strings) and construct the SA for it. Let's define two notations:

      1. $$$terminal1$$$ nodes: These are the nodes that have an outgoing transition corresponding to the '@' character.

      2. $$$terminal2$$$ nodes: These are the nodes which have been marked as terminal nodes of the string $$$s$$$ by the SA.

      Now, for a string to be a common substring of both $$$a$$$ and $$$b$$$ also to be unique in both $$$a$$$ and $$$b$$$, the state corresponding to the string must have exactly $$$1$$$ reachable $$$terminal1$$$ node and $$$2$$$ reachable $$$terminal2$$$ nodes.

      Proof

      Let's call it a good state. The no. of nodes of each type reachable from a particular state/node is easily computed using dp. Now, we can simply iterate over all states and for a state which is good, we know that all substrings ending at this state are common substrings in $$$a$$$ and $$$b$$$ and are also unique. The length of the smallest substring ending at the current state($$$i$$$) = $$$len(link(i)) + 1$$$, where $$$link(i)$$$ is the node being pointed by the suffix link of $$$i$$$, and $$$len(link(i))$$$ is the longest substring ending at $$$link(i)$$$.

      Code

      P.S.: I wanted to write the dollar symbol instead of '@', but wasn't able to do so in markdown. If you have any idea how to write a dollar symbol, please tell me.

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

Hi guys. I used java to write the solution to problem C. And I also used the SCC way , and its O(m) implementation (Tarjan algorithm). Can anyone please tell me why my solution timed out on the final tests:

https://gist.github.com/anonymous/7c8ce4e7d76f7015424d

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

    Probably because Scanner is slow. You can see this for more information: http://acm.timus.ru/help.aspx?topic=java&locale=en

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

      Thanks for your suggestion. I really didnt know that before. However even after replacing Scanner with StreamTokenizer as mentioned in the page you sent me, I still have the same time limit exceed on the same test case (test11)

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

        I got TL11 too: 6537605.

        I used Kosaraju algorithm to find strongly connected components. This algorithm consists of following parts:

        1) Do DFS to find out time of leaving for every vertice. (dfs1(int) in my code)

        2) Reverse graph.

        3) Do DFS in reversed graph to find out SCC. (dfs2(int, int) in my code) DFS should be started from vertices sorted in descending order by leaving time in non-reversed graph.

        I was sorting them in O(n^2). So when I replaced this with O(nlogn) sort, I got AC: 6537714.

        I hope this information will help you. And sorry for my english.

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

          You don't need to sort anything — simply add vertices to a new list when you leave them in the first DFS. Then visit the vertices in this list starting from the end.

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

Finally I got my Python to run below 2 seconds for 427C. Reading (and creating graph) took around 0.7s from the beginning (referring to largest case with 100,000 nodes). My own solution based on algorithm described here:

http://e-maxx.ru/algo/strong_connected_components

Took another 1.5s to find SCC. Then another 0.3s to finalize calculation — 2.5s total — hello TLE ! Adapting SCC calculation procedure (based on Tarjan's algorithm) from networkX dropped the time to 1.2s total — solved.

Should I continue to use Python? I don't know. I did C++ back in 90-ies (I was doing some DirectX programming) and Java in mid 2000-s. But for me it has always being hobby/recreational stuff and I am not sure that I wont to retrain in another language. But of course it is a little bit sad that solution does not pass only because of taking 0.5 seconds more then allowed because of scripting language.

I would wholeheartedly voted for using PyPy in Codeforces competitions. It is much faster, especially in Dynamic Programming tasks (really up to 10 times faster) and I think majority of Python problems would be solved immediately. PyPy has very good compatibility with Python 2. It has problems with third-party modules, but it is not an issue with Codeforces because Codeforces does not allow any third-party modules anyway.

So — can we start motion for taking on PyPy in Codeforces?

Just example — my solution above takes — at my local PC solution discussed above takes 1.64 with Python and 1.06 with PyPy. Remembering that 0.7 goes to reading the file, this is a huge difference.

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

    It's my first time here. I am used to topcoders.com where the programming language doesn't really matter. Numbers are chosen in a way that the only thing that counts is whether you got the right algorithm or not. I wish that codeforces.com will use the same strategy. It's pretty sad as you mentioned to see solutions refused because they require a split second more.

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

      Did you try PyPy? I use it for Google Codejam and it does miracles — I would say that if I am to use PyPy at Codeforces I would never again raise issue of Python being too slow :)

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

      I think that this strategy can be somehow limiting for problemsetters.

      A possible (but more "expensive") strategy should be writing solutions in different languages and set different TL value for each one.

      I agree that this issue is important (see editorial comment for 424D - Biathlon Track for example), but I cannot figure a possible, fair solution for that, and personally I wouldn't like to see CF setting TC-like problems...

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

        Thanks for your reply.

        But I still don't understand why it would be a limitation to the creativity of problem setters (for example to put n < 10^7 instead of n < 5. 10^7 even when the latter is enough for C++)

        My poor understanding is probably due to my modest experience in programming challenges.

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

          [In my humble opinion] I think that low constraint values force problemsetters to "live" with the fact that some solutions with greater asymptotic growth than the expected solution will get AC instead of a (possibly) desired TLE.

          Some programming tasks are non-trivial just because a naive method is too slow for a possible maximal testcase with the statement constraints. With small values it would be impossible to distinguish efficient solutions from the less-eficient ones. That's why I think this is somehow limiting for problemsetters and, consequently, I think this allows CF to have more problem variety than TC has.

          Quick example: Consider the problem 424B - Megacity. A quadratic/cubic/etc solution is clearly slow with these constraints, but now imagine the same problem with, let's say, 1 ≤ n ≤ 100. Almost every "dirty" solution would pass.

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

WA on test 112 in problem E :(

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

    I had exactly the same problem.

    The way test 112 is different from any other is that m = 1, so basically you "cut" away prisoners by 1. My program had two indices, i and j going from different directions and meeting in the middle.

    Test 112 was the only case where left index overrun right index — after main cycle left index ended up being larger then right index. I didn't check for that and in final "adjustment" was just adding final distance between i and j. When i overrun j I ended up actually subtracting last distance from solution.

    Again — this happened only in case 112. If you algorithm is different, then my hint is still — think where it can breakdown if m = 1.

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

У кого нибудь z-функция проходит в D? Мое решение валится на 146 тесте

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

My solution for problem E is pretty simple.

The best place to build the poclie station will always be the median. So just iterate from pos 0 to the median and from last position to the median in m-to-m steps while adding the absolute value of the visited positions minus the median position (*2) to the final answer.

This is my code: http://ideone.com/H9W9tP

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

    Thank you very much, your answer really helped me, Just one question, I did this problem in java, and was using int, but some answers were wrong(I'm guessing overflowing), then changed to long and it was fine, why is this ?, int are supposed to be 2^32 which is greater than 10^9 , Sorry if my question is really dumb, I dunno much about these things...

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

      You're welcome :)

      About your question: I'm not 100% sure, but I think that when adding all distances total sum could exceed 10^9 so I it is preferible to use long, in order to avoid overflowing.

      Hope it helps :)

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

        Thank you very much for your explanation, guess you're right ! Another thing, and sorry to bother you again, why you take m steps, is it because you always will carry the m criminals in the way when you make one step ? and also how did you come up with the best position being the median, once again sorry to bother you, I'm just starting with all of these problems.

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

          There's no bother :)

          Yes, I take m steps because with that I avoid to go twice across the longest distances, so I always "pick up" criminals that are one next to other.

          I remember I read once that for going through a path with the shortest distance you have to start always in the median. So I checked it and it worked with the 'm' steps too, so I supposed I could get Accepted :D

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

For 427C, I used Tarzan algorithm on Java, but always get TLE on Test case 11 http://codeforces.com/contest/427/submission/6543050 Is it because I create a inner class Node (No)? Could someone please help?

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

I can't view the model solutions — it says "You are not allowed to view the requested page". Is that normal?

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

Who can explain me the algo with suffix arrays for 427D?

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

    We can sort the suffixes of both strings using a single suffix array (on the string s1#s2#). Note that later we can recognize which string does each suffix belong to: if its index is less than |s1| (0-based), than it belongs to s1, if its index is greater than |s1|, it belongs to s2.

    Now suppose there is some string t that is a unique substring of s1 and a unique substring of s2. Let's think of the corresponding prefixes of s1 and s2 where this string starts. Since only they have the common prefix t, they have to be adjacent in the suffix array, let's say at p[i] and p[i + 1]. Also, the longest common prefix of p[i - 1] and p[i] is less than |t|; and the longest common prefix of p[i + 1] and p[i + 2] also is less than |t|.

    So, this leads to a solution: iterate over all adjacent positions in the suffix array, p[i], p[i + 1]. Calculate:

    x = lcp(p[i - 1], p[i]),

    z = lcp(p[i], p[i + 1]),

    y = lcp(p[i + 1], p[i + 2]).

    Then each prefix of p[i] with length of at least max(x, y) + 1 and at most z is unique in both s1 and s2. So if max(x, y) + 1 ≤ z, we can update the answer with max(x, y) + 1.

    Check out my submission: 6538270.

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

      5 years later and this comment is still useful and helped me get AC. People like you make the world a better place.

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

Как решать задачу D через суффиксные массивы?

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

hello, i am very new to programming... could anyone tell me how to return multiple values in a recursive function in c++??

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

Am I very lucky? My E solution is simple. I just find if the capacity of patrol car is greater than or equal to the number of criminals, simply subtract two end-points and multiply by 2. If it is less than, I find the middle position and calculate from it to 2 end-points.

My submission's here: 6536182

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

    It is correct because if you change point to the left, you make result better for left side, but you make worse for right side, and vice-versa;

    My solution: 6556865

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

427D :

If I correctly understand the problem statement, isn't it possible if certain substring of input string occurs twice in return value? I mean applepp / pepperoni returns 2 when I run my accepted solution. But I think "pp" occurs twice in applepp so it should not be substring because of definition. Am I right??

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

подскажите что здесь не так 6559633?

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

427C - Checkposts : Wrong answer on test 72, my solution 6991595, any explanation?

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

Does anyone have a proof that the function (ternary search solution) for problem E will just decrease then increase?

I tried it on many samples, but can not fine any proof for this!!

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

Sorry, can anyone help me please.

Here is my submission for problem 427D: http://codeforces.com/contest/427/submission/26701755.

I got WA on test 17 and can't understand why. My solution:

  • f[i][j]: longest common string end at s1[i] and s2[j];

  • f1[i][j]: longest common string end at s1[i] and s1[j];

  • f2[i][j]: longest common string end at s2[i] and s2[j];

  • max1[i]: longest common string end at i with all position j in s1 except i.

  • max2[i]: longest common string end at i with all position j in s2 except i.

Then for all pair(i, j) have f[i][j] > max(max1[i], max2[j]): i update answer;

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

In 427E — Police Patrol this solution passes 69 test cases!! I am wondering now, sol1 and sol2 (appeared in previous comments) really works fine! I need a clear proof of that median approach. Can anyone give me a proof?

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

Someone please help me find the problem in the solution(in the part to compute the number of cases). Please check my code https://codeforces.com/contest/427/submission/76030254

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

Можете помочь с задачей 427A . У меня код работает , выводит правильно , но на первом же тесте выводит "Ошибка исполнения на тесте 1" с ошибкой RUNTIME_ERROR вот сам код

n = int(input())
s = list(map(int, input().split()))
c = 0
for j in range(len(s)):
    if s[-1 &mdash; j] >= 1:
        s.pop(-1 &mdash; j)
    else:
        continue
for i in range(len(s)):
    if s[i] == -1:
        c += 1
    else:
        c -= s[i] * 2
print(c)