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

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

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

Auto comment: topic has been translated by Endagorion (original revision, translated revision, compare)

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

Why it shows Tutorial is not available ?

UPD: It's available now :)

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

В задаче E в первом решении вместо сета можно использовать стек, тогда второй логарифм пропадает.

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

    Не могли бы вы объяснить каким же образом можно использовать стек?!

    Заранее большое спасибо :)

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

Can anyone explain how Div2 B can be solved using Ternary Search

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

    I have done this.

    We analyze total time in relation to position, I will call it p selected. Time of each point x with speed v is abs(x - p) / v. If we make p vary, as v and x are fixed we'll see an abs function

    Which is the total time? The worst of all those times. formally max(v1, v2, ..vn). If we make drawings we can see that if we plot the total time in function to the position selected, that graphic has no local maximum, and the left and right sides tend to positive infinite. So we observe that as the function is continuous we need to have a unique local minimum somewhere in the center of the graphic (otherwise the sides can't tend both to infinity). There can't be more than one minimum, because otherwise we would need a maximum to exist and we accepted it didn't exist. The left side of the minimum must be strictly decreasing (as it comes from positive infinity), and the right side strictly increasing (as it goes to positive infinitive), and so, the graphic is something like this

     Note that the left derivative is negative and the right one is positive. Which means we can make a ternary search on the point when it changes, from negative, to positive, that will be a local minimum, as the only one, the global one, hence the solution of the problem.

    Evaluating the function will be O(n), so total complexity the product of O(n) and your number of ternary search iterations (of logarithmic behavior)

    25253744

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

      Great explanation, I have seen this problem on virtual contest and tried to solve with similar approach. Intuitively I felt that there should be only one point where the required time is minimum. But couldn't solve during the contest, after reading this comment everything clicked and got AC.

      By the way, I have checked your solution and why use mabs? cpp has its own fabs which does exactly same

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

        By ignorance :) Sometimes, during a contest it is faster to write these simple functions rather than open google haha. Also sometimes I decide to avoid to use some c++ functions to reduce the risk of generate unexpected algorithm complexity, however this is not the case :)

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

for Div.2 D (Div.1 B)
somebody says try all ai, if there is the conflict then try all bi. if these two cases both have conflict then the answer is NO.
like submission 25322923 and try the input:

  4 
ABC DDD
ABC EEE
QWE FFF
QWR FFF
get the output: NO but isn't
 ABD, ABE, QWE, QWR 
a solution?
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here we don't try all b_i when there is some conflicts for a_i. But only those b_i whose corresponding a_i conflict with each other.

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

Can someone please help me understand the editorial of problem 782B — The Meeting Place Cannot Be Changed. how to iterate for all t's and how to apply binary search.

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

В задаче 782B — "Место встречи изменить нельзя" используя простую эвристику можно построить две последовательности отсортированные по начальной координате. Одна с возрастающей начальной координатой и убывающей скоростью, вторая с убывающей начальной координатой и убывающей скоростью.

Для возрастающей последовательности, легко заметить что друг имеющий большую начальную координату и большую скорость явно придет к месту встречи раньше. (аналогично для убывающей) Все остальные друзья не влияют на место и время встречи. Максимальное время встречи пар состоящих по одному человеку из возрастающей и убывающей последовательности и есть искомое время.

Используя эту несложную эвристику я получил на питоне время выполнения на порядок лучше чем метод половинного деления. Python реализация эвристика с перебором

В данном случае тест кейсы являются хорошими для полного перебора, в случае "неудачных" данных, можно получить точное решение за время O(n*log(n) для сортировки остальные значения можно собрать в один проход O(n).

Для этого рассматривать нужно пересечение возрастающей и убывающей последовательности с учетом времени. Python реализация без перебора

P.S. Мы строим два графика min(max_xi(t)) и max(min_xi(t)), пересечение и есть искомая точка встречи.

max_xi(t) максимальная координата x i-го друга в момент времени t (он идет на север с максимальной скоростью) min_xi(t) минимальная координата x i-го друга в момент времени t (он идет на юг с максимальной скоростью)

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

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

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

782B can be solved without binary search. Working time is much better comparing to binary search solutions. heuristic with enumeration all pairs & O(n*log(n)) sorting + O(n) scan

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

in div2 E, why is it guaranteed that the tour exists? and even if it doesn't which, why is writing the nodes in that way is guaranteed to generate the answer?

edit: i understood the solution, but why is it called euler tour?

and is it me, or mentioning that traversing an edge twice is fine had to be mentioned in the statement?

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

    would someone tell me if we can visit the same edge twice? and if so, why is it called "euler tour" in the editorial?

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

      Yeah, we can visit the same edge twice. Suppose in the dfs ordering of nodes, we backtrack all edges (in the dfs tree) once.

      -> Total edges traversed = 2*(n-1) -> If we divide into k parts, we get [2*(n-1)/k] <= [2n/k] -> We can always assign dfs (preorder) accordingly.

      I have no idea why it's called Euler tour, since that means we should be visiting each edge once, and end up on the beginning node.

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

        You should code simple recursive algorithm for Euler tour. But write vertice twice first time on visiting and another time after recursive return (on each return to the vertice). This will produce required sequence.

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

In div1D, what is meant by "optimizing boolean multiplication with bitsets" and how do we achieve this optimization?

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

Can you figure out what is wrong with my code in problem 781B (wrong in test 16)? 25333425

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

what meaning "The route is a closed polygon line in the place, with all segments parallel to one of the axes" in Intranet of Buses? help on Intranet of Buses!

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

I'm getting 'Tutorial is not available'.

And tutorials for some other rounds are also not available currently see this

KAN MikeMirzayanov please fix this.

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

А где разбор?

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

In Div1 B (football league problem) what is the mistake in my algorithm? I really don't see the bug. http://codeforces.com/contest/780/submission/25485848

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

can someone please find why am I getting runtime error in python2.7 in problem C div 2?

Here is my code, a big thanks in advance

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

in task d(div 2) test 5 aaa b aaa c aaq z aab z aab o craches lots of solutions. The result is probably YES aab,aac,aaq,aaz,aao but it isn't)

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

What's the idea behind giving 5 seconds for div 2 B if the intended solution is 46 ms 26456429 . Is it to allow for N^2 solution or to trick people into attempting N^2 solution?

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

    I believe it was done to allow solutions using slower programming languages.

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

      interesting. There is programming language 100x slower than c++? If so, what language is that?

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

        I'll give you a hint: the name of this language starts with letter p.

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

Can anyone please explain me why the complexity in DIV 2 B is O(n * log (eta inverse) ) and not O(n * log ( max (eta inverse,(h-l) ) ), here h=upper bound and l = lower bound of the binary search respectively. Thank you in Advance :)

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

Endagorion That may seem too old, but for problem B div1 for the second part after having only distinct Ai, isn't maximum matching needed?

A case like this causes a lot of accepted solutions to fail:

4

ABC D

ABC E

ABF X

ABX E

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

Can someone explain why my algorithm used in Div2 B The Meeting Place Cannot Be Changed is wrong. I assigned each friend the velocity plus the velocity of last friend(using the concept of relative velocity, last friend which is on the northest side has been given zero velocity while another friend will move towards him with a greater velocity) So minimum time I am getting is less than jury's answer. Here is the link to submission