SYury's blog

Codeforces Round #514 (Div. 2)
By SYury, history, 6 years ago, In English

Hello!

Codeforces Round #514 (Div. 2) will start tomorrow, October 05, 17:35 (UTC+3). This round will be rated for the second division (with rating lower than 2100).

Many thanks to KAN for his help with the problems and round coordination, Aleks5d and Um_nik for testing this round, and MikeMirzayanov for his awesome Codeforces and Polygon platforms.

There will be 5 problems for 2 hours. The scoring distribution will be announced later.

UPD: the scoring distribution will be 500-1000-1500-2000-2500

UPD2: Congratulations to the winners!
Div. 2:
1. qingczha
2. PaidySung
3. Hyperbolic
4. memopaper
5. reku

Both divisions:
1. Radewoosh
2. qingczha
3. natsugiri
4. nuip
5. PaidySung

UPD3: editorial

Good luck!

  • Vote: I like it
  • +293
  • Vote: I do not like it

Comments Comments (134)
| Write comment?
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

gl hf

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

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

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

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

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

Back to back contest...

ohhh Yessss...

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

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

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

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

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

    How many did youb solve in the icpc preli?

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

      We did bad in ICPC Preli. Unfortunately we solved only 2 problems. In Problem C and D, we got TLE. WA in Problem J.

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

        It's okay. We didn't do much better either. Solved 3, got AC in J. Which year are you in?

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

Shortest announcement... Not good.

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

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

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

So concise description.

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

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

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

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

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

    It has just 5 problems, so yeah, it's gonna be hard.

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

I wish everyone gets positive rating changes.

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

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

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it 
Score distribution !!??
→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

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

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

    Yes, I can not understand the statement of problem B. Kind of shit!

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

      the problem for me was that he didn't say that we shouldn't include empty cells in the sides of chosen rectangles .

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

What is test 4 of D problem?

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

    I have the same problem.

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

    2 -10000000 1 10000000 1

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

      The lack of setprecision makes WA then? :)

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

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

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

          Ye ye already got it thats the second,bigger issue.

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

        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.

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

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

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

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

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

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

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

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

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.

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

    This solution does not fit the time limit restriction.

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

    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.

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

      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.

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

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

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

    what was ur greedy after the binsrch on answer?!

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

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

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

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

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

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

          Thanks! :D

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

            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.

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

              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 )

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

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

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

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

    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

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

      What was ur algorithm btw?

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

        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.

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

howto solve C ?

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

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

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

What is the pretest-6 of C?

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

    As I guess: 6

    Answer would be:

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

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

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

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

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

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

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

            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.

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

      The last one is special.

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

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

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

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.

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

    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.

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

      Probably would have got WA on Test 4, so why bother?

      Geometry can never be fun. End of story.

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

      Want fun? Solve some string matching problem, a range query problem, or a nice DP one. Let geometry for math geeks and masochists.

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

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.

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

    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.

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

    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.

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

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

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

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.

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

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

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

      I was wondering how to do that...

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

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

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

        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.

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

          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.

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

    You got E for dp today.

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

      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.

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

        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.

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

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

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

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

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

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

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

        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.

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

          Would the above ideas pass this test?

          Edit. Yes, they should.

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

            Yes, my code got 2 as answer.

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

how to solve B and E?

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

    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

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

      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!

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

    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.

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

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...

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

    You thought THIS was good?

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

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

      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.

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

        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.

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

          all geometry is boring and confusing

          What lol?

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

            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".

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

        can you please share the idea for E?

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

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

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

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

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

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

Forgive if grossly incorrect.

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

    Well I got AC with that idea (at least on pretests).

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

      can you please explain the idea a little bit more?

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

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

Shouldn't it timeout.

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

    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.

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

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

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

http://codeforces.me/contest/1059/submission/43847734 Whats wrong with my submission for C?

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

How do you solve D?

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

How fast system testing is done today. WoW.

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

Hint for problem D https://www.geogebra.org/graphing/gqhms2jk

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

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!

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

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 :'(

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

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

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

    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".

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

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

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

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

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

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

      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?

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

        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.

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

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

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

            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.

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

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.

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

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.

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

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

AC: https://codeforces.me/contest/1059/submission/43867295

WA: https://codeforces.me/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.

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

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

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

      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://codeforces.me/contest/1059/submission/43912614 Change bounds: (WA): https://codeforces.me/contest/1059/submission/43920041

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

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

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

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

      Even Radewoosh's solution (AC): https://codeforces.me/contest/1059/submission/43841799 Fails from precision just by changing the bounds: https://codeforces.me/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.

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

        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.

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

        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.

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

          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.

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

            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?

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

              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.

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

                Oh, get it. Thank you very much!

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

    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.

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

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

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

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.

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

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

    → Reply