MikeMirzayanov's blog

ACM-ICPC World Finals 2017
By MikeMirzayanov, 8 years ago, translation, In English

ACM-ICPC World Finals 2017 will begin on May 24, 2017 at 15:00 (UTC). This event is the main event of the year in the world of sports programming!

This year ICPC Regional participation included 46,381 of the finest students and faculty in computing disciplines from 2,948 universities in 103 countries on six continents. A record 50,145 students and 5,073 coaches competed in ICPC and ICPC-assisted competitions this year, setting new records in participation.

Codeforces wishes the teams to show a vivid and interesting contest contest. We wish to find beautiful solutions, write without bugs and enjoy many accepted problems!

Links:

ACM ICPC World Finals 2017 English Broadcast:
ACM ICPC World Finals 2017 Indian Broadcast:
ACM ICPC World Finals 2017 Chinese Broadcast:
ACM ICPC World Finals 2017 Arabic Broadcast:
Broadcast from legends: Petr, tourist, Endagorion:
  • Vote: I like it
  • +292
  • Vote: I do not like it

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

Is it rated?

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

Is there a live contest?

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

    No, this is a repeat. Tsinghua University win with 11 solved problems.

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

Does anyone know a link to current results?

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

Is there any mirror where we can solve? Or atleast view the problems?

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

    here it says they will add problems after contest starts, maybe 30 mins after the start?

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

Are there problem statements available?

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

rng_58 and other Atcoder officer's broadcast: link

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

What is the public contest link where the legends are submitting their solutions?

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

    Well watching the stream right now they are not submitting their solutions because they can't, I think they are waiting for this link to become valid just like everybody else.

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

Problems are available here: https://icpc.kattis.com/problems

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

when will the final results be out?

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

How to solve Problem F, is it a dp problem?

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

How to solve C?

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

    bipartite matching

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

      How is it a bipartite matching problem? Can you please elaborate a little more :D

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

        First of all, you need to see that a value > 1 should be present in the final grid if and only if it is the max in a row / column else you can replace it with 1 and it will be still be a valid solution.

        So, for each value which is max in some row/column you get a subset of rows(nr) and columns(nc) in which it is maximum. Now you can have atmost nr + nc numver of those values to get a valid answer but if we can put a value at some of their intersection such that 1 value satisfies 2 maximum condition, we can get less number of positions with that value. That is where maximum matching comes into picture. Lets say r1, r2,... r_nr and c1,c2,c_nc are the rows and columns such that their maximum is same. So we take all nr * nc intersections that is A(r1,c1) , .... A(r_nr,c_nc) and whenever A(i,j) > 0 we make an edge b/w i and j. Now this is because we cannot convert a zero value to a non zero value. If we find the maximum matching in this graph, some rows and columns are matched. So if we put the current macimum at their intersection, then we can refuce the number of maximum by macimum matching value. So, we need nr+nc-max_matching number of positions with current value.

        Also, we need to keep in mind that, there may be some non-zero values unaccounted for in the values, we need to make those values = 1.

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

          Thanks I got it AC :D

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

ITMO wins!

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

Can someone explain to me the what was going on with the ASCII art bird with Russian text that was spammed in the Twitch chat (especially near the ending of the ceremony)? Foreign memes are always interesting to learn about :D

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

    It's just spam hype copy-paste meme. Russian version of Le Toucan has arrived

    goose spam mem
    goose-hydra spam mem
    → Reply
»
8 years ago, # |
  Vote: I like it +283 Vote: I do not like it

I find it weird that announcing National Taiwan University as the first to solve J (submitted at 296) already implicitly revealed that Warsaw University failed to solve J (submitted at 294).

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

What's the trick in J?

We get the upper bound of F, the upper bound of W, and the upper bound of vF + W (by running normal flow three times). I think I proved that these are also sufficient conditions (by maxflow = mincut), then it's easy to compute the maximum of Fa * W(1 - a). To construct the solution we need to run another flow once more. Do I miss something?

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

    Exactly like that. No trick :)

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

    I think these were few reasons of only 1 ACd solution:
    1) scary objective function, might create an impression of requiring hard math
    2) actual solving of problem <=> realizing what is a set of reachable flows (F, W) (rectangle with cut corner). If you start solving this problem it is not obvious that this works this way, but as soon as you realize this it really is easier than it seemed to be 3) medium problems were harder than usual (at least in my opinion), they took more time to solve them, so not much time was left for harder ones (or at least, harder looking ones :p)

    We got the right idea, but sadly apparently made some implementation bug along the way, got no time to debug

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

      Yup, rng's solution was pretty much the intended one, and it's relatively straightforward (as flow problems go). I was personally rather surprised how few teams attempted J. To your reasons I would add 4) the usual contest groupthink: nobody solved it early, so everyone assumed it was hard. :)

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

    Yes, but how exactly do I reconstruct the flubber and water flow?

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

      Once you know how much flubber and water you need to send, you set the capacities from the super source to the flubber source and water source accordingly and construct a flow. Then you reduce the capacities of the edges to the value of this flow, and run flow once more, this time reducing the capacity of the edge (super-source, flubber source) to 0. This yields the water flow. Flubber can be found by substracting those two.

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

        yeah, but how to know the direction of flubber for those edges with no water flowing at all?

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

          From the first flow. It tells you how much stuff (water+flubber) goes in which direction. In particular, on every directed edge it holds

          fflubber(e) + fwater(e) = fwater + flubber(e)

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

            ACC, thanks!!

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

        ACC, Thanks!!

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

I think this was a very good chance to stop Russian domination on ICPC with Warsaw and seoul at their peak :D . Seems they will continue their domination for a little upcoming years before current chinese 17 years old lengendary grandmasters focus on ->

training on problemsets that consist in half of only ugly geometric problems and the rest somehow distributed between problems like "translate directly very chaotic statement into C++", some problems requiring backtracks filled with weird heuristics, some obvious problems requiring heavy library algorithms and one or at most two problems requiring some thinking Credits : Swistakk

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

    Heh, I actually really liked this problemset, a lot of problems required really nice ideas, no library problems, just one geo problem that was on the easy side (however I personally would prefer more ;p). B falls into both reading complicated statement and backtracks with heuristics, but I heard it was not that painful (didn't read lol).

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

      This problemset contained some nice problems.(Of course I didn't solve all of these nice:v). I mean by nice something not belonging to the category above and you may see in an IOI or CF contest.

      At the same time, some of them were unfair I think and gave advantage to some teams. I believe problem A was discussed\encountered by a lot of experienced contestants as I saw some variations of it before (even I am not a geometry fan but I saw). Problem D I believe is pasting from library.

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

        Yeah, A was kinda a fail, I solved exactly the same problem 1-2 months ago from old Petrozavodsk camp. That helped me getting first solve on this one xD.

        I don't know why are you stating that D was pasting from library. It looked like it can be well known, but nobody from our team knew this. If you meant that main difficulty of D was writing D&C trick then I will definitely disagree (meaning that coming up with it was much harder). Inb4, if you ask then we don't have convex hull of hyperbolas in out library xD.

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

          Regarding problem D, does this one look familiar?

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

            Yes, it does :). Funnily enough, mnbvnar gave me this problem few months ago and I couldn't solve it (he solved it, but I didn't learn solution), but today he hadn't got an idea and I came up with same weird trick with hyperbolas :pp. When I explained my solution to him he immediately recalled that problem and said it is basically same solution :p.

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

              http://mirror.codeforces.com/gym/100886/problem/I

              A problem mentioned in a blog is not that big deal. I mean every problem has a probability to be found on the internet in some chinese papers.

              But I have seen the problem of pairs (a , b) and queries (x , y) and asking for max ax + by like three times. One of them is in this petrozavodsk camp [problem:http://mirror.codeforces.com/gym/100886/problem/I]

              and another variation in our region and another one in a chinese regional (I don't remember unfortunately). It's really unfair to pick problems just found that easy way. Even petrozavodsk version is slightly different, But I don't think it will make that big difference. (anyway my friend solved this back in the virtual and I am just too lazy to think of these stuff) :D

              Another thing that I came across

              http://mirror.codeforces.com/gym/101047/problem/F

              This is from a 2015 regional and exactly the same problem (even harder) as ICPC 2016 problem L (If not mistaken , it was easy anyway but still). It's from a regional qualifying to 2016 and surprise , same problem.

              Like I have seen a lot of problems in ICPC that just requires a straight forward approach of something. Not a variation , the really straight one.2015 , 2016 was no difference.There are some things that I don't understand, Why problems in ICPC are different than stuff we see in IOI/POI/CF. I bet like most of teams in the contest spent their time sweating and debugging and arguing with each other. and nobody felt like he had fun solving the problems. Like POI problems for example or even CERC even are much more fun than ICPC problems and hard the same. Even though , you need simple stuff to solve the problem and so much creativity. It's just more fun than solving linear programming and a geometry problem that any code with less than 69 if statements is wa and still missing tests.

              I haven't solved a really hard problem of past ICPCs but most of (easy->medium) problems are just like this.

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

                Having creative challenges is nice, but the point of those Easy->Medium problems might be different. It's a problem solving contest after all, not a "hey I'm smarter!!" contest.

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

            Also, given the speed of some Japanese teams solving G, it was probably similar to some local contest.

            My utmost concern as a judge in an ACM regional was 'what if one of our problems exists elsewhere?'. I don't believe the judges knew about those problems, it's impossible to be sure that a problem never existed elsewhere.

            I think this keeps coming up every year. This is basically unavoidable given the thousands of existing contest problems.

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

              It's not about existence of a problem. 2 problems were "traditional" problems. I don't know if there was more. Same thing every year.

              The same situation of giving a maximum bipartite matching problem in a beginners qualifying contest in your university.

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

              I'm Japanese but I've never seen similar problem to G. The only cause that Keio University took FA of G is this team contained me:D

              The problem G seemed interesting and actually it was very interesting. I like others in this problem set too (except A). Thank you very much for problem setters! Also, thank you very much for all who supported this wonderful contest!

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

                Heh, it was kinda suspicious to see that first accepted solution to G came from a team whose first accepted submission was on that very problem (before E and I) and which places around ~120th spot :P. Such situations usually mean that they managed to get away with some naive heuristics and maybe our team was first one to "really solve" this problem, but on the other hand this problem didn't look like one that could be solved using approaches that are not fully correct, so I was a bit confused. When after contest I noted that Keio team has snuke everything became clear :).

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

                  Sorry to confuse you & congratulations for gold medal!

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

                  Haha, no need to be sorry :D. Thanks to you we started thinking about that problem pretty quickly instead of being stuck on D which turned out to be a good decision ;).

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

                  snuke, what strategy did you use during WF? I am confused...

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

                  I guess he used strategy "Screw overall result, let's have some fun solving nice problems and maybe getting some cash for First To Solve's" ;p

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

                  Yes. We ignored time penalty and aimed to FA in problems of my favorite genre (graph theory or some kind of puzzles).

                  The problems in the World Finals need much more thinking than Asia Regionals. The computer becomes vacant while I'm thinking because our team contains only one active competitive programmer. peryaudo was a blue coder but not so active now. So we are no match for the other teams at World Finals (especially in time penalty). This is the reason of my strategy.

                  In the contest, I read J and G at first. I misread J and it seemed impossible one. (I thought v is given for each edge. Without misreading, I would try to solve J instead of B.) I read G next and thought of solution for some minutes and got FA. I tried to solve B next. The written rule seemed almost same as a board game "Cluedo" but solution was not so obvious. (the intended solution seems using pruning in brute force... all writers must read this blog. I'll post about my solution.) I thought of solution for few minutes and implemented/debugged for long time. However I could not get FA. Finally we switched to solve easier problems but I was too tired to solve more problems. In parallel, my teammate solved E,I by himself and F with my hint.

                  As a result, we solved 4 problems and got WA/RE on B and C. To be honest, I think this result is lower than I expected. But I'm satisfied that we could complete our first goal "get FA" because I know it's difficult to perform perfectly in the crucial contest. Anyway the World Finals was very exciting. I wanna go next year too but I'm already not a student now(;_;) See you again at some contests!

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

How to solve G?

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

    This came partially from my own attempt at the problem and partially from listening to the solution on the livestream, so it might be corrupted, but I hope it's close enough and easy to follow.

    Firstly, a little mathy rant: we can treat the state of the 300*300 squares as a column matrix C of size 1*(300^2). Then the reproduction without errors is simply multiplying by some (mostly 0) matrix M over Z_2 (just take mod 2 after multiplication). Hence, we have some sort of homomorphism: if f() brings us to the next state, then we have f(a+b) = f(a) + f(b), where a and b are states.

    So now we can think of errors as toggling the state of 1 square, and hence 1 generation later, this will toggle the state of exactly 9 squares. This gives rise to a crucial observation that gives a trivial polynomial time solution: if a configuration has a possible previous state, then that state is unique.

    Justification: Let E() denote possibly a mutation of 1 square. Suppose on contrary that E(f(a))= E(f(b)). Then E(E(f(a) — f(b))) = E(E(f(a-b))) = 0 (possibly), but (proof omitted, but loosely speaking I think considering 'corners' can prove this) there is no nonempty state s such that f(s) has less than or equal to 2 cells.

    Furthermore, the bounding box of a figure increases by 2 in each dimension each iteration, so the question is just to find f^-1 of a state repeatedly, if it exists. Also, we need to do this at most 150 times, so this admits a trivial polynomial solution contingent on how fast we can find f^-1 of a state.

    Let A be the current state we are given. We want to find (if exists) B=f^-1(E(A)).

    It turns out we can easily check whether the top row of A contains a mutation: if there is no mutation, then we can recover the row from the top left corner onwards. Then, there is an error iff the top right hand corner has an invalid parity checker. Through a similar process, we may check the second row next and so on. Repeating for columns, we can find the row and column of the mutation, and once we know the location of the mutation, finding f^-1 is easy. (I'm rushing for time, maybe someone else can furnish a more coherent explanation for this part later?)

    Since this process takes O(N^2), we have overall algorithm time O(N^3) and we are done.

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

      I think you meant "Then, there is an error iff the top right hand corner has a invalid parity checker", or did I miss something?

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

Final ranklist ?? https://icpc.baylor.edu/scoreboard/ is frozem

EDIT : GOT IT !! https://icpc.baylor.edu/worldfinals/results

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

Could anyone tell me the solution to Problem E?Thanks! UPD：I was confused by the data range n<=1000 and now I got it.Please ignore.

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

    Can you share your idea?

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

      Just do binary search on the answer,and you can pass in O(nlogn) time.

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

        Actually I did it.But it got tle on some cases. code

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

          In binary search on doubles, limit the number of steps to say 100, cause there will be precision issues comparing doubles.

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

How to solve H?

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

How to solve C?

I tried moving the max in a row/column to cover a row and a column (simultaneously) if possible, but I get WA test 7.

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

    The only constraints are:

    • Every 0 must stay a 0
    • Every nonzero must stay nonzero
    • Every row must have its maximum somewhere
    • Every column must have its maximum somewhere

    The first two are easy to satisfy by placing 0s and 1s. For 3 and 4, you want to satisfy both with the minimum amount of "placements" of values. You can save a value if you use it for both a row and a column. So try matching as many as you can!

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

http://www.csc.kth.se/~austrin/icpc/finals2017solutions.pdf

All solutions

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

Why sharif fut didn't participate?

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

    I guess visa issues.

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

      So why Tehran University participated?

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

        I have no idea, probably because they got visas :P. For every number in set {0, 1, 2, 3} there was at least one team that had that many participants because of visa issues. Sad, but true.

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

          There were teams with 3 members because of visa issues? :P

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

Give me some of your's ACM world finals t-shirts

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

    How much can you afford to pay for it?

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

My solution for B (without pruning and its time complexity can be estimate easily):

Brute force search for "which cards are removed" and "for each people/weapon card who has it". There are at most (6^2 * 9) * ((3^5)^2) ≒ 20,000,000 cases.

Before fix the distribution of people/weapon, the clue '*' is ambiguous. After fix, the clue '*' can be regarded as "if the player has suggested people/weapon card, this clue is no more information, otherwise the player has suggested room card".

Then for each pair of (player,card) can have one of three state "player has card", "player doesn't have card" or "player can have card". The distribution is possible if there exists an assignment for "can" state (to "has" or "doesn't"). The existence of assignment can be calculated by simple maxflow.

TL was tight so it was needed to implement carefully. source code (3.37s on Kattis)

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

I'm wondering how teams solved problem A. The computations regarding whether lines cross the polygon boundaries need to be done exactly, which — I believe — requires the use of exact arithmetic. The input coordinates are given with 21 bits. I think that means that you can, for instance, compute intersection points (42 bits), but not for instance midpoints between intersection points (84 bits).

What is the general technique for implementing these calculations exactly using only 64 bit integers?

(PS: I have a "naive" AC solution that uses C++'s "__int128" type and computes midpoints — but I'm certain it's not necessary).

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

    I don't know why are you so afraid of (long) doubles here, they work well. General setting when doubles can be bad is when perturbing slightly can change answer a lot in a not continuous way (here for example "does this point lie on this line?"), but here all points involved in such questions have integer coordinates, so it is very unlikely doubles will give significant errors.

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

      Can you explain this a little more?

      Are you saying that using long doubles (with a 64-bit mantissa) would allow you to compute the line between any two vertices exactly (using 42bits), and it would also allow you to determine exactly whether another polygon vertex lies on that line (using 42+21 = 63 bits?)? But that if the other polygon vertex does not lie on the line then you'll conclude it's either not touching or crossing a polygon boundary anyway? And if crosses, it'll only influence the distance you report as answer, so rounding error does not matter? You determine whether it crosses using the sign of the result of the incidence test?

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

        Are you familiar with concept of using epsilons in geometry tasks? Since non-integer computations show up all the time in geometry we need to operate on real numbers and we can't expect doubles to satisfy conditions like a==b even if they are really the same number. If you want to check that A, B, C lie on same line you can check whether CrossProd(A, B, C) =  = 0 if you have everything implemented on integers, but you can't do it like that if they have real coordinates and in such case we check whether abs(CrossProd(A, B, C)) < ε, where epsilon is chosen wisely, for example ε = 10 - 9.

        Here is my code for reference that gets accepted on Kattis: http://ideone.com/08pisZ

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

          wisely

          LOL

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

          Thank you. I'll take a deeper look at your code.

          I note that the only place where you require the epsilon check in this problem is your ptOnSegment (due to the use of the sqrt() function.) If you remove the epsilon check from the other tests, your program will still pass. That said, this version of ptOnSegment was new to me, thank you.

          For fun, I tried my solution (which avoids division and sqrt) with double and long double, and __int128 — it passes with all three choices: http://ideone.com/zy3uG9 (and no epsilon).

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

      IMO, it's reasonable to be scared of using doubles on a question like this, despite the integral coordinates. You identified the main issue: that a candidate line could just barely work or not work depending on how close a polygon vertex gets to it. The problem is inherently unstable (that is, there are valid input cases for which permuting the vertices by a small epsilon leads to a large delta in the answer). Thus care is warranted.

      Unfortunately, it's not trivial to see what the worst-case epsilon is. With coordinates bounded by 10^6, how close can a lattice point get to a lattice line without lying on it? If I remember correctly, the actual answer is 7*10^-7, for the simple case of (1,1) and (0,0)-(10^6,10^6-1). But it's not obvious (to me, anyway) why another less-simple example couldn't come closer. EDIT: I guess Pick's Theorem is the way to prove it. :)

      So for this problem you need an epsilon on the order of 10^-7, for coordinates ranging up to 10^6. 13 decimal digits of precision are required, and doubles have 15, so they're good enough. But it's close. In a contest I'd still try to use integer arithmetic (well, doubles guaranteed to be integral) whenever possible.

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

        Actually it's quite easy to estimate how close can point be to a line. Let point A be really close to line BC. (B-A)x(C-A) is integer, so its abs is >=1. However |BC| is not larger than 3e6 and crossprod is base times height, so height is at least 3e-7.

        However that's rather irrelevant to why my code works. I do not test whether point lies on line by checking if it close to that line, I test it by checking if crossprod is 0, so for that part even epsilon=0.5 would work :). What requires doubles computations in my code is computing intersections of an arbitrary line (determined by two vertices of polygon) with sides and then checking whether that point lies on that segment. That can also be estimated properly, but epsilon 1e-9 sounds sufficiently fair enough for me here ;p.

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

          I was answering your comment "I don't know why are you so afraid of (long) doubles here". I explained why someone could (and should) be afraid. :) Good for you; using integers for the intersection test is the best way to avoid any such issues.

          Ok, I was being dumb using Pick's Theorem. Your cross-product explanation is much simpler!

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

            My solution is based on integers, i only use double for comparing angles and storing intersection points.

            Solution
            → Reply