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

Автор vepifanov, 14 месяцев назад, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится  
  • +92
  • Проголосовать: не нравится  

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

Can you please elaborate soln. for problem C?

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

    The Ray will always move with a vector (1,1) or (-1,1) or (1,-1) or (-1,-1) because it always change its direction 90° and in a straight line. For every one of this lines, witch are all parallels to the diagonals, if you extend them to the infinite they only cut once the x axis. In fact, they cut the x axis in (x+y) if the vector is (1,1) or (-1,-1) and in (x-y) if it is (1,-1) or (-1,1). You can then calculate for every sensor this number for the both line that pass throughout it. You make then lists of sensors for each possible sum and difference of coordinates.

    You then simulate the ray, going from wall to wall in O(1), and checking and updating all the sensor that are in both lines that pass trough every point in the wall you touch.

    It's then O(N) with N being the number of sensors.

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

      It's also important to note that you only enter in a loop when you arrive to one of the other three corners (0,N), (M,0) or (N,M).

»
14 месяцев назад, # |
Rev. 4   Проголосовать: нравится -36 Проголосовать: не нравится

Another idea for Problem A without setting many conditions! 21324550

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

    Pretty cool! Could you explain for nubbie please)?

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

      of course, you just try the first day in the input with the months {28, 30, 31} and simulate the cycle till the second day in the input matches or else output NO!

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

That solution for C was so easy! I tried to elaborate a mathematical solution but things got too complicated. BTW, is it possible to get time for each point in O(1)? It's pretty easy to convert time into coordinates, so there basically must be a way to do the opposite i.e. convert coordinates into time.

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

Не понимаю, как прийти к решению задачи A.

Если не сложно, могли бы описать подробно?

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

Поясните, пожалуйста, что подразумевается под фразой "_Поэтому можно перебрать пару столбцов, которые мы будем обменивать (или не будем обменивать их вовсе)_" в разборе задачи B

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

    Насколько я понял, всё, оказывается, достаточно просто. Решение задачи — грубый перебор. На это должно было намекнуть условие с ограничениями на n и m (n, m <  = 20). Поэтому, чтобы не пытаться решить задачу эффективно за O(n) с множественными проверками и дополнительными условиями (усложняющий код, понимание и отладку), нужно было решать простым неэффективным методом (грубым перебором), но без лишний запутанности кода: переставить очередные столбцы и проверить, можно ли из этого получить отсортированный строку за 1 изменение. Если все работает успешно, то написать YES и выйти.

    Что ж. Мотаю на ус. :)

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

      Получается, переставляем каждый столбец с каждым и на каждой итерации цикла проверяем возможность сортировки каждой строки за 1 перестановку?

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

        Да, именно так. Только что реализовал, и действительно все ок. Если посмотреть исходный код гроссмейстеров, то все как один решили именно так.

»
14 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

there are on subtrees of size k at all

Maybe there's a typo, it should be

there are no subtrees of size k at all

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

    I just can't understand why I get downvote. Or that we shouldn't point out typos?

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

Can problem D be done using this approach: starting from index 1, for each window of length 'm', we find the smallest character and add it to the answer. For checking the smallest character, set can be used with the element stored being (character,index). As we move the window, we remove the first element of the previous window and insert the new element of current window, then check if the new smallest character is the same as previous. If it is not, we can add it to our answer. Let the answer be 'ANS'.

At the end, we can iterate through the string and for each character that is not added in the answer, check whether it is less than the largest character that exists in 'ANS'. If yes, we can add it to answer and continue.

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

The Tutorial of problem F use status O(n*n*d).But many people solve F with status O(n*d).Can anyone tell me how to solve it with status O(n*d)?

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

If i-th bit is equal to one for at least one vector of the basis, then this bit will be equal to one in the 2^r - 1 triples.

Can you explain why?

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

    Fix vector u in the basis which has i-th bit. Not depending on vector v from first 2^{r-1} vector, one of v and v xor u will have 1 and other one will not

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

      in know it's been long .. but can u explain the basis related part of G in simpler terms

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

Can anyone explain D?

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

    it is important to observe that if a letter L is needed then all the occurrences of the letter from 1..L-1 will be included in the lexicographically smallest string. Now the main problem is to find the least number of occurrence of the letter L.

    The initial problem is to find the max smallest letter L within which we will be able to visit all the intervals. To do this, we will iterate through all the intervals for each of the letters. In each iteration we will check whether the current letter indexes can fill any intervals and mark them. While doing this we will have to make sure that we always take the right most position and if we can use that position in other interval then we have to use it as it will solve our main goal of taking the least number of occurrence of the current letter. See the below test cases for clarification.

    test case: 3 aaaaaaaaa ans : aaa

    3 ababab ans : aa

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

Anyone solved 'D' with segment tree?

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

    I did. It became extremely complicated though.

    21310505

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

    I did too. But it was only used for looking up "rightmost minimum character in an interval". I wish to note than it can also be done with RMQ: O(n log n) preprocessing and O(1) queries, but I find segment trees less error-prone and easier to code, so that's what I used.

    Code: http://codeforces.com/contest/724/submission/21289565

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

      I was doing exact same as you linkret but forget that maximum of all minimum char over segment must be greatest in result char array and all less left char must be included in result char array.

      Thanks:)

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

Can anyone explain, why cycles with "zero" XOR sum makes sense for answer? I have submission 21335792, where I ignore all "zero" cycles, it gets WA24. But here 21335866 I use all cycles, even "zero", and get AC.

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

    The mistake you made wasn't ignoring the "zero" cycles but "int mr = min(sz, 60)"

    notice that mr may be larger than sz

    what if cyc = {1, 4} ?

    You will get mr = 2, base = 1, r = 1 but it should be that mr > 2, base = 5, r = 2.

    So just change it to "int mr = 60;" and everything will be right.

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

"cut(i, j) = min(cut(i - 1, j - 1) + si, cut(i - 1, j) + pi + j * m)."

In problem E, what do you mean by m? I can solve the problem in O(n^3) but don't understand this relation.

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

    They meant c, maximum amount of goods for a single transportation. So they cut all edges to j cities, which are currently in set A.

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

    You consider two cases. If you assign the ith vertex to set A, the capacity increases by si. Instead, if you assign ith vertex to set B, capacity of cut increases by pi+j*m. The j*m value comes from the j vertices in set A such that there is edge from those to ith vertex.

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

The 724E - Транспортировка товаров can be also solved using greedy (didn't get this right during the contest). It's a little tricky, but basically you first do all the trading that doesn't require sending things, so that each city either just produces or just consumes, and then go through the cities from left to right. You can maintain a list of already seen and active "producers", along with an information on how much can each of them send if a "consumer" comes (either directly, or via other already seen cities that don't produce, but can be used to transfer goods through them). When you get a "consumer", greedily use producers, starting from the rightmost one.

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

    "via other already seen cities that don't produce, but can be used to transfer goods through them"

    Can you please explain this a bit more?

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

To problem E: why isn't it cut(i,  j)  =  min(cut(i  -  1,  j  -  1)  +  si,  cut(i  -  1,  j)  +  pi  +  min(j  *  m, si)) ? it also seems OK..

For the case that I cut both si and pi

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

editorial for problem F The number of trees that have exactly one centroid is equal to

when n is even, it should be tree(n, d, n/2 — 1) to avoid counting 2-centroid cases.

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

I've found O(n*log(n)) solution for problem E and it ran in almost no time 21622504.

I felt that the constraints should have been higher but they were not...

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

    Eh, could you please explain your solution ?

    I am only able to solve the problem with the complex O(n2)

    Thx.

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

      Instead of the approach given in the editorial we can do the following: Let the partition of vertices for the minimum cut be (S, V-S). Then |S| can take values from 1 to n+1. By doing some work it is easy to find out the capacity of the minimum cut which has |S| = i for i=1 to n+1. Our answer is evidently minimum of all these capacities.

      Have a look at my code after you brainstorm on my point given above...

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

Is there any any mathematical generalisation for problem c. P.S. I'm a newbie,all I could see was some pattern and then it showed time limit exceeded my solution is http://codeforces.com/contest/724/submission/21307944 .can someone help me out ?

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

In problem E, why the formula to calculate the minimum cut is  ?

(Sorry if this is something trivial, I'm completely newbie in minimum cut problem)