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

Автор SYury, история, 6 лет назад, перевод, По-русски

Всем привет!

Завтра (5 октября, 17:35 (UTC+3)) состоится Codeforces Round #514 (Div. 2). Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Участники из первого дивизиона могут написать контест вне конкурса.

Выражаю благодарность KAN за его помощь с задачами и координацию раунда, Aleks5d и Um_nik за тестирование раунда и, конечно, MikeMirzayanov за замечательные платформы Codeforces и Polygon.

Вам будет предложено 5 задач и 2 часа на их решение.

UPD: разбалловка 500-1000-1500-2000-2500

UPD2: Поздравляем победителей!
Div. 2:
1. qingczha
2. PaidySung
3. Hyperbolic
4. memopaper
5. reku

Оба дивизиона:
1. Radewoosh
2. qingczha
3. natsugiri
4. nuip
5. PaidySung

UPD3: разбор

Удачи!

  • Проголосовать: нравится
  • +293
  • Проголосовать: не нравится

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

gl hf

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

Wow, that's by far the shortest announcement in a while.

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

    Plus, It thanked MikeMirzayanov for his awesome Codeforces and Polygon platforms. :)

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

Back to back contest...

ohhh Yessss...

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

Finally, a regular Codeforces round is here after a week of waiting. I love Codeforces.

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

удачи всем

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

That will be first time ever in my life, I will face 2 consecutive contests in almost 6 hours.

ACM ICPC Dhaka Regional Site Online Preliminary contest — (BD time) — 03.00 PM to 8.00 PM.

Codeforces Round #514 (Div. 2) — (BD time) — 08.35 PM to 10.35 PM.

Thanks :) SYury

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

Shortest announcement... Not good.

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

Hope the problem statements will be as short as the announcement :) .

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

So concise description.

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

It is an unforgetable experience to start a contest at midnight.I love Codeforces.

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

A red problem setter and just div2, it's gonna be hard contest.

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

I wish everyone gets positive rating changes.

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

I hope that lack of div.3 contests means that the next gonna be amazing

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Score distribution !!??
»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

there're only 5 problems prepared by a red problem setter? gonna be a hard contest

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

B must candidate to the "worst problem on the year" !

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

What is test 4 of D problem?

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

    I have the same problem.

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

    2 -10000000 1 10000000 1

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

      The lack of setprecision makes WA then? :)

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

        Actually the most common problem was too low binary search upper bound.

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

        Yeah and also the radius is huge so you can't just start your binary search at 1e7

        I found a solution that didn't take care of precision and searched from [0.2..1e15] and lucked out of that pretest (for now... pending system tests) but anyone who went from [0..1e15] with the same precision problem will fail it.

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

      Thx, max-radiuos ~ 10^14 !!!!

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

      It will be nice, if D statement was added hint about this restriction, or limitation of x,y coordinates. This is div2 problemset -).

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

        h = abs(y - r); sqrt( r * r - h * h ) ---> WA4

        sqrt( 2*r*y - y*y) - AC ! ``

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

By any chance is D first ternary searching for x coordinate of center and then binary searching for the y coordinate of the center? If not can someone give any hint on how to approach.

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

    This solution does not fit the time limit restriction.

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

    I solved it by binary search on radius R: then for a fixed R for each point you can calculate the interval of the x coordinate of the center of the circle (by pen, paper, math). Then you need to check whether all n these intervals have an intersection.

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

      We only obtain two possible points for the center of circle(since it has to lie on the line y=R) while checking it for each given point,right? Why do we get intervals instead of two points?

      Got it.I thought that all the points needed to be on the circle boundary.

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

Building a neat binary search solution for D, with all those precision handling and everything, and still got a WA at pretest 4.

This is just plain sadistic... :<

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

    what was ur greedy after the binsrch on answer?!

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

      I didn't do greedy.

      My logic: for each radius r being checked (obviously the y-coordinate of the circle's center will be r), traverse through every points and find the leftmost and rightmost x-coordinates that the circle's center's will be not-further-than-r distant to that point with its x-coordinates lying between the leftmost and rightmost.

      If all intervals intersects somewhere, then r is one answer (might not be the optimal one, that will be solved with further binary searching).

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

        what is your output if the points are (-1e7,1) (+1e7,1) ?

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

          Got my issues now. The upper bound of my binary search was too low (heck, it's insanely high to be honest).

          Thanks! :D

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

            I dont know how to handle this extreme high cases either. the radius of curvature is too high. and squaring it will exceed variable limits. Hence i cant take distances between two points. This is why i couldn't do it either incontest.

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

              I just figured out a way btw :D bet it'd pass all tests in practice :D

              I'll binary search everything in long double, and to counter precision issues (to break the binsearch loop properly), I'll calculate the absolute/relative error of the lower bound and the upper bound and see if it is low enough.

              (The function is given in the statements itself, and it's easy enough to implement :D )

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

              The following formula helps to keep calculations <= 1e18.

              sqrt(A * A - B * B) = sqrt((A - B) * (A + B)).

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

    I also got WA on pretest 4. But I overcame it after increasing the number of iterations of the binary search (unfortunately I got TLE on later tests and didn't have time to optimize the algorithm :( )

    edit: nvm, my algorithm was not the same as yours

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

      What was ur algorithm btw?

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

        Binary searching for the point of tangency. Given a point of tangency, you can compute in O(n) minimum radius and you have that the optimal tangency point can not be farther away from the point that is on the boundary of the minimum circle on the current tangency point.

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

howto solve C ?

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

    HINT: Remove numbers at an odd position's, until there more than 3 elements.

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

What is the pretest-6 of C?

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

    As I guess: 6

    Answer would be:

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

      How do we compare it with 1 1 1 1 3 6?

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

        Your answer is lexicographically smaller (the 4th element is 1, while the optimal one's is 2).

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

          But according to the given statement, j=2(0-based indexing) then a[i]>b[i] is not satisfied for i>j.

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

            You got it wrong. The criteria is like, the lexicographical order is determinded by the leftmost element that differs between two answers.

            So, we'll determine j = 3 (0-based) only.

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

      The last one is special.

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

Previous contest haven't got any Editorial even till now. I hope this contest gets an Editorial soon enough.

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

I hated this crap.

A was stupid subtraction with confusing intervals, B was ad-hoc (and a terrible one at that), C was math, D was geometry and I didn't even read E after so much frustration with the other 4 garbages.

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

    Problem D was one of the best problem I have ever tried but missed to submit, i just needed 10 seconds, found a little bug in last moment (-_-).I tried only problem D in 2 hours.

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

How to solve C? I was thinking of finding the number of coprimes for each number in range 1 to n and then greedily removing the number having largest number of coprimes. But couldnt implement. Is this right? Please share your approaches.

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

    my pretest passed solution:

    initially current_gcd = 1, then remove every even index (1-indexing) if n is even, or remove every odd index if n is odd from the original sequence so we can get larger gcd faster, except when n = 3 we just remove index 1 and 2 because its better.

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

    The idea was the following: Initially the gcd is 1 and this needs to be increased to some g>1. Consider the smallest prime factor of g (say p). To increase the gcd from 1 to g we need to remove at least all the numbers which are not divisible by p. We need to minimize the number of numbers not divisible by p, which is same as maximizing the number of numbers divisible by p.

    It can be observed that except for n=3 in all other cases, p=2 (We can hard code the solution for n<3). After removal of "bad" numbers, all the remaining numbers will be the first floor(n/2) multiples of 2. Now it is possible to recursively build the solution, by solving for n=floor(n/2) and multiplying the resulting sequence by 2 elementwise.

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

I'm gonna be green like a String in the wind

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

It'd be nice to see a Segment Tree problem once in a while, a DSU, or even a DP. It seems all we see now is math, math and more math. Go to IMO if you want math.

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

    Problem C was not Math, just IQ test. Don't be tricked by GCD !

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

      I was wondering how to do that...

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

      Ahhhhhhh, I didn't know this was an IQ test, dude. I thought we were in a programming competition!

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

        Most competitve programming problems are not only about "Please implement this algorithm/that data structure", but also at requiring you to make certain observations. And that is the part when your IQ is needed.

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

          Yeah, I accept that part of also requiring you to make certain observations.

          I just utterly detest it when the whole problem is about making observations and/or math calculations, with little to no programming technique or data structure.

          But why bother discussing? Everyone will see I'm cyan and you're red, so they're gonna downvote me and upvote you. Whatever.

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

    You got E for dp today.

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

      DP?

      I did a solution for E using binary jumps, but for some bogus reason I got TLE on Test 24, when all the previous test cases had at most 150 ms. I don't care anyway, the contest's over.

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

        I remembered the minimum number of paths for the subtree and the possible paths ending in the root (in that minimal splitting). These paths had a structure that the sum of values was increasing, but the length of the path was decreasing (otherwise it is not profitable to store other paths).

        I do not know how to prove that the number of such paths will be reasonable (maybe it won't and my solution should tle) but it passed. While merging these paths, merge smaller set to larger.

        Then try to extend every path with the value of the new root. If you can't, start a new path in the root.

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

          That sounds way too complicated and too much thought involved for a problem that doesn't require any thinking, just implementation of a technique.

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

    I solved E in 200 lines using 3 segment trees and dp.

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

      Really?!

      It's a simple binary jumps + binary search with much less than 100 lines and only two data structures (one for ancestors and one for sum of weights).

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

        If you want dp you think dp

        Also, you just need to maintain the stack of vertices in a dfs and do bsearch over it, no need for LCA stuff.

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

how to solve B and E?

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

    B find every cell which is surrounded by ‘#’, when found one,copy these '#'s to another graph(initialized by ‘.’). compare two graphes,judge whether they match.

    I don't know how to solve C,(((QAQ ORZ

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

      C can be solved recursively. The base cases are (1, 2, and 3) for which the answers are given in the sample itself. For all other cases remove the odd ones first and then divide the array by 2 and it again becomes the same problm. The only thing you should take care of is that we are dividing it 2 but it is not actually the case so, at the time of printing we have to print the actual values itself. Hope it helps!

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

    I didn't even read E during the contest because all the other bullshit took away my time, but after reading it now, I think it can be solved with prefix jumps over ancestors and binary search, but I still have to test my solution.

    I'll see if I'm right once the turtle finishes system testing all solutions for this sorry excuse for a contest.

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

I'm don't know if I'm too easy-going, but 80% of time when I think the problemset is good, I read the comment section and seeing everyone else bashing it...

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

    You thought THIS was good?

    Well, yeah bro..... you're either too easy-going or you're a math freak. Choose whichever you like.

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

      I registered for the contest late and ended up did not even touched ABC (since I can't submit them in the first 10 minutes even if I implemented them fast enough), only focused on D and E, and both of them seems OK so far.

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

        D was not that bad, considering it's geometry, and all geometry is boring and confusing. Except for the part that my idea is correct and I get WA on Test 4. Let's see what happened after System Test.

        E was nice I think, but all the other bullshit took away my time during the contest, so I didn't even read it.

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

          all geometry is boring and confusing

          What lol?

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

            What you just read pal. Geometry is simply not of my liking.

            I solved D in the end (after the contest...), but that doesn't mean I enjoyed doing it. Thinking a solution for a geometry problem is not fun, and coding it is a pain the ass.

            Formulas like asin/acos/atan and all that stuff that I never remember which one is what without Google, cross product, neverending variables for something as simple as a line intersection... and all that without even mentioning precision errors. A correct solution can get WA for something as insignificant as replacing "double" with "long double".

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

        can you please share the idea for E?

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

    I actually really liked the problems, especially B and C, and I think I have an idea for E...

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

    Problems are more enjoyable to one when one has managed to solve them.

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

Is E something like finding the topmost vertex you can reach from each vertex, and then starting from the leaves?

Forgive if grossly incorrect.

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

How 1e9 computations are possible in 2s on CodeForces (as http://mirror.codeforces.com/contest/1059/submission/43853124)?

Shouldn't it timeout.

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

    1e9 pure computations only take about 0.2-0.4s for C/C++ solutions. Other languages (Java, Python, etc.) will surely get TLE for that.

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

It's a little weird of today's problems :)

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

How do you solve D?

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

How fast system testing is done today. WoW.

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

Координаторы посмотрите сюда плз 1)http://mirror.codeforces.com/contest/1059/submission/43859812

2)http://mirror.codeforces.com/contest/1059/submission/43864411

3)http://mirror.codeforces.com/contest/1059/submission/43864455 Первый код зашел на контесте но упал во время проверки Второй код отослал после проверки и зашло Третий код отослал после того как зашло и получил ТЛ Код во всех один и тот же

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

Problem E was BY FAR easier than B, C and D. After reading it, I instantly thought "Binary jumps + binary search", and that was it. Coded it in over 10 minutes and got Accepted after fixing a stupid bug of not stopping iterations of marked vertices at root of tree.

Come on, let the downvotes rain!

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

Anyone have any idea what was systems test 18 on B (It's m = 900 and n = 999 or something so I can't copy see the whole of the test case)? 43842790

Bye bye expert :'(

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

share approach for problem B plz ? thanks in advance ..

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

    My approach = Question says center of square 3*3 will not be painted rest all elements of 3*3 grid will be painted,so center of matrix can be (2,2) to (n-1,m-1). So for every possible center check for all 8 side boxes and if none of the neighboring cell contains '.' then assign a certain fixed value to all neighboring cells. Repeat this process for whole matrix and at last check this matrix with actual matrix ( i.e if matrix[i][j]=='#' && value not assigned). If both are same then "Yes" else "No".

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

Some submissions work with greedy passed problem E may get wrong with this data:

4 4 6

1 2 4 3

1 2 2

the answer is 2 but some submissions output 3

This kind of submissions start from leaves and go up as far as possible greedily, and continue with a process like topological sort

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

    I think it will be more fair to rejudge E with stronger data.

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

    The idea of starting from leaves and going as far as possible each time is correct. It could time out with strong tests if done naively (i.e. simple dfs), but the answer should be correct.

    The key is to try to go up as far as possible for all leaves, even if there's a middle vertex that's already included in another path from another leaf. For the sample test you provided, a correct greedy solution would do the following...

    • Process node 3 and make path (3,2) with total weight 6.
    • Process node 4 and make path (4,2,1) with total weight 6.
    • Skip node 2 because it's already included in a path.
    • Skip node 1 because it's already included in a path.
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The key is to try to go up as far as possible for all leaves, even if there's a middle vertex that's already included in another path from another leaf.

      why?

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

        Because there can be a case where you try to go up from one leaf and go to a certain vertex v because including the next one would surpass the limit, but the next leaf to the right has a lower value, so you might go up some more ancestors from this one.

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

          but then you have to disinclude the earlier path, right?

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

            Yes, if the problem asked you for the actual paths, you'd need to check what leaf each node corresponds to, but it only asks you the total number of paths.

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

It is a nice problem set. D is really nice. But i implemented it in a binary search fashion along with the computation of distance square from the given point to the center of circle using euclidian distance. I just used long double and i din check for any precision error. Although I think the error may come in line number 25 and line 38 and 39 in my implementation. I believe there could be more precision checking test cases. Here is my submission https://ide.geeksforgeeks.org/5vmRXdAzE0. Anyhow sincere thanks for the great problem set.

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

Когда дадите рейтинг?

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

Can anybody help me with D? I know the solution is using ternary search but I can't figure out why my own solution is incorrect or why it is having precision issues.

43867521

I have done bs over radius and in my check function I have tried to find whether there exists a value of x for this radius.

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

Oh my god question D was very very unlucky for me. Take a look at these 2 submissions:

AC: https://mirror.codeforces.com/contest/1059/submission/43867295

WA: https://mirror.codeforces.com/contest/1059/submission/43848961

The only difference is what you choose to start your binary search from. The AC one has high=1e16, the WA one has high=1e15. The algorithm and formulas are otherwise entirely the same. However #43848961 is JUST outside the precision bounds.

I spent the whole contest debugging my code and finally changed my formula to be more numerically stable, but just changing the bound a bit would have AC'd.

Plenty of people got AC first try but I see plenty who got WA with the EXACT same formula and just chose an unlucky bound, so it didn't pass pretest 4 (and only pretest 4) due to precision.

TLDR; I think the precision for problem D is too tight and a bit unfair.

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

    Well... if you look at the correct answer and compare it to the your program's answer, you'll actually find that it's pretty far off. Quite a bad approximation (even the accepted version barely passes the limit). 1e-6 is a standard precision requirement.

    I'd say the implementation could use some work. Most people who got accepted had way better (tighter) approximations. I'd say it's LUCKY that your second submission passed (and not unlucky that the first one didn't).

    Also... it doesn't really have anything to do with luck. This particular test is easy to think about, it's obvious that it has the highest probability of introducing precision errors and is also very easily to compute by hand (with pen and paper). Therefore, it should be one of the first cases you'd want to check your program on. Not stress-testing your code is your fault, not anybody else's.

    TL;DR: try to analyze your mistakes, improve yourself and work to get better instead of blaming the system :)

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

      I got a bit triggered so I'm going to reply:

      Here's a bunch of AC's on just one page (most recent at time of writing) which would fail if 0...1e15 was chosen as the binary search bound. Note that this is just a CURSORY glance looking for exactly what I was talking about:

      Original (AC): https://mirror.codeforces.com/contest/1059/submission/43912614 Change bounds: (WA): https://mirror.codeforces.com/contest/1059/submission/43920041

      Original (AC): https://mirror.codeforces.com/contest/1059/submission/43913915 Changed bounds: (WA): https://mirror.codeforces.com/contest/1059/submission/43920093

      Original (AC): https://mirror.codeforces.com/contest/1059/submission/43916864 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/43920289

      Original (AC): https://mirror.codeforces.com/contest/1059/submission/43917464 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/43920315

      Original (AC): https://mirror.codeforces.com/contest/1059/submission/43918142 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/4392036

      Even Radewoosh's solution (AC): https://mirror.codeforces.com/contest/1059/submission/43841799 Fails from precision just by changing the bounds: https://mirror.codeforces.com/contest/1059/submission/43920454

      The exact same solution is everywhere on the leaderboard.

      If that many solutions with the same incorrect formula pass simply because the author chose a luckier starting bound for their binary search then that means one of 2 things:

      1. The solution should be OK and the precision should be set more lenient
      2. The tests should be thorough (which they are not) and try to punish poor precision instead of leaving it to random chance

      We have 1/2 people AC and 1/2 people stuck the entire contest fixing precision, but all of them have the same solution... is that fair? My point isn't complaining and blaming for not doing well, my complaint is that the tests aren't thorough enough to warrant that precision requirement.

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

        You need to understand that.. for test #4, the problem has exactly one mathematical answer: 50000000000000.5

        The fact that these solutions that you linked get AC with answers such as 50000044046781.77815247 is ALREADY pretty generous, I would say. You can see that the answer is pretty far off. Other implementations out there yield results like 50000000000000.4949989318847656, which is miles better. The precision margin is there to allow results like these, which are very close to the actual mathematical results (since computers cannot do real number arithmetic perfectly). Making the margin even more generous would be unfair to these "better" solutions. And again, 1e-6 is the standard error. It's pretty much always this in every contest (even tighter on some problems). What would you have it changed to?

        Ok, changing the parameters (like the binary bounds) on a "bad" implementation might make it get accepted, but that's simply by luck. What you SHOULD be aiming for is one of those "better" implementations, not changing parameters on "bad" ones in hope that it gets better.

        Also, my point about test #4 being the first test you should stress-test your code on still stands.

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

        Something else I'd like to point out: in all of these solutions that you linked, there's a common pattern. The number you take the sqrt out of is computed like this r * r - (y - r) * (y - r), but going an extra step, this can be rewritten as y * (2 * r - y), which is relevant because now you are doing operations on numbers of lower magnitude, therefore reducing the chance for precision errors (which a good programmer will know; as someone else said, this is a programming contest, not a maths contest).

        As proof, this simple modification on your WA code turns it into AC, with an answer of 49999999999272.4042434692 on test 4, which is orders of magnitude closer to the actual answer than the 50000049523832.28391265869140625000 of your AC solution.

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

          I know! I know! None of what you said is wrong, it's just not the point.

          I'm saying that there should at least be more tests, OR the precision bound should be higher. I'm not saying that all of these WA's should pass, I'm saying that they should either all pass (which you clearly don't like, that's fine) or all fail.

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

            I also notice this when today I am solving the same problem. I just wonder how to implement this in a better way. Would you like to tell me?

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

              The problem happens because larger doubles have worse precision. When sqrt(r*r-(r-y)*(r-y)) is calculated, r*r and (r-y)*(r-y) is often is quite large (1e18*1e18) but with a small y value they are too large for the small result to be precise enough.

              So rearranging the equation to avoid needing r*r is possible:

              r*r - (r-y)*(r-y) = (r + (r-y)) * (r - (r-y))
              

              If y is in the circle, then it must be true that 2r-y >= 0 and so:

              sqrt((r + (r-y)) * (r - (r-y))) 
              = sqrt(r+(r-y)) * sqrt(r - (r-y)) 
              = sqrt(2*r-y) * sqrt(y)
              

              This way the largest intermediate value used is 2r-y which is no larger than like ~2e18, much better than 1e36 and will have enough precision.

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

    I think task D was a valid problem, since dealing with real numbers' precision is key in competitive programming. However, I think this is a valid suggestion as well. If the problemsetter's intention was for contestants to figure out a thoroughly precise solution, Why does a weak program pass by fixing small details? As far as I am aware of, a good problem should be able to break any solution that is not the intended one, and this one didn't. Not to mention that this is a two-hour contest, where penalty for wrong submissions and delay is significant. Therefore I do believe it is a bit unfair to leave ambiguous constraints, since people will waste too many points on a solution that isn't even supposed to pass.

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

Good Contest, Quick testing ,Fast editorial. Day made. Thanks codeforces!

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

Лол, меня дисквалифицировали. Какие-то чуваки скоммуниздили мой код по С, так как я юзал ideone с паблик кодом(не обращал внимание раньше на эти настройки и не думал, что код могут видеть другие) Забавно, что некоторые даже отправили мой код до меня)) Я случайно, не баньте плиз, больше так не буду

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

Weak tests in E.

I hacked this solution from Giver with the following test (works locally ~50s):

I wonder whether other solutions fail this test as well.

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

    System test for E is so weak. Many O(n2)(worst cases) approaches pass the test, which is unfair for those who employ a correct algorithm of O(n log n).