Endagorion's blog

Technocup 2017 Finals and Codeforces Round #403 Editorial
By Endagorion, history, 8 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +56
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Why it shows Tutorial is not available ?

UPD: It's available now :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +20 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 :)

        → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know but the somebody's code doesn't seems like that.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    we need to find the minimum time so that all participants can be in one place. that place need not be an integer, so it could be an integer but it doesn't have to be. so our time would be a long double variable.

    lets assume that the time we picked is very large. the larger the time the better the odds of us find a point where every person can meet. why? because each person can then travel farther distances (north or south) which means the odds of persons crossing each other's paths is higher. if lets say there are only 2 people and the distance between them is large, as we give them more and more time to travel they will get closer and closer to each other and at some time t, they will cross each other. the same argument can be extended to more than 2 people...

    so if we picked some time t1 and we somehow were able to figure out that everyone CAN meet at some point x within that time, what does that mean for all times t GREATER than this t1? it means that for any time greater than t1 all the people CAN meet at that point x. why? because the only thing that we do by increasing the time is that we give everyone a chance to travel even further north or south. so this point x is obviously within everyone's reach, even if we give everyone extra time. so basically there is no point of checking for times greater than t1, if at t1 everyone can meet at point x.

    now, if we picked some time t1 and we somehow were able to figure that everyone CANNOT meet at some point x within that time, what does that mean for all times t LESS than this t1? it means that for any time less than t1 all people CANNOT meet at any point x. why? because reducing time to travel means everyone travels every a shorter distance than before, which means the odds of everyone meeting reduces further. so basicaly there is no point of checking for times less than t1, if everyone cannot meet at point x.

    ^ the above approach is binary search. so we pick a time t1, see if its possible for everyone to meet at some point x. if it is possible then we check for a time less than this t1, as t1 is already the best answer we have. if it is not possible then we check for a time greater than this t1...

    now given a time t1 how do we figure out if it is possible for all people to meet at some point x? given a time t1, person P can travel anywhere between (positionP — speedP * t1) and (positionP + speedP * t1). speedP is a limiting value. the question says person P can travel at speeds no greater than speedP. so we have a range [x,y] where we know the person can travel to. we need to find [x,y] for every person and see if all these ranges have an intersection range. if it there is no such range that is common to all [x,y] then for this particular time t1, all people cannot meet at some point x. if there is a range that is common to all [x,y] then it means all people can meet at any point within this common range.

    **here we will be doing binary search on long double variables, which is not as straight forward as it is with integers. we usually stop binarySearch(i,j) when i == j, but how can u say i == j when i and j are double values? i might be equal to j for a few decimal places but not necessarily for all. how do we tackle this?

    as the question states the error should be within 10^-6 doing binary search at least 80 times would mean we have correctly covered 6 decimal places. if the error rate was maybe 10^-10 we would need to increase the number of times we do binary search maybe to 110 times... u can create a dummy binarySeachForDouble(x.0, y.0, steps) and keep doing binarySearchForDouble(x.0, (x.0 + y.0)/2, steps — 1) to see that x and y keep getting closer and closer....

    refer to https://codeforces.me/contest/780/submission/46841304 for better understanding

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I was wondering about the same thing. Both solutions 25258392 of V--o_o--V and 25257297 of jqdai0815 make use of maximum matching too.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Most of the solutions used greedy approach which is definitely not accurate that it fails on the mentioned case and similar cases.

      That would match the fact that N <= 1000, otherwise if greedy was enough N could have been <= 100000

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Answer is YES?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C can solve using BFS without knowing about degree plus 1. Check my submission.

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be helpful if anytone can tell how to apply BFS in Div2 D.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B has the similar idea of segment intersection as in this contest's B https://codeforces.me/problemset/problem/1730/B

→ Reply