VK Cup Round 2 + Codeforces Round 409 Announcement
By Lewin, 8 years ago, In English

Hello!

The round 2 of VK Cup 2017 will take place on April 16 at 18:35 MSK (check your timezone here), along with separate div1 and div2 Codeforces Round #409. The contest "VK Cup 2017 — Round 2" is for teams qualified from round 1. The top 100 teams will advance to the Round 3, while other ones will have one more chance in the Wild Card Round 2 later this month. Those who don't participate in the VK Cup can take part in the Codeforces Round #409 individually (problems will be available in English too). All three rounds last 2 hours, and all are rated.

The round would not be possible without the following people (in no particular order): KAN, Errichto, winger, AlexFetisov, LiChenKoh, xiaowuc1, MikeMirzayanov. Additionally, I thank VK company for sponsoring this contest.

As usual, the scoring distribution will be announced later.

UPD 1: The scoring distribution is as follows:

div2: 500 — 1000 — 1500 — 2000 — 2750

div1 and official round: 500 — 1000 — 1750 — 2250 — 2250

UPD 2: The tutorial is available here: http://codeforces.me/blog/entry/51598

Congratulations for the winners

Official round:

  1. LHiC, V--o_o--V
  2. I_love_Tanya_Romanova, enot110
  3. netman, andrew.volchek
  4. aid, ershov.stanislav
  5. MrDindows, Rubanenko

div 1:

  1. SirShokoladina
  2. jqdai0815
  3. jcvb
  4. Syloviaely
  5. Um_nik

div 2:

  1. ngkan
  2. justarandomstring
  3. fgvfgfg1
  4. DryukAlex
  5. DorMOUSENone
Announcement of VK Cup 2017 - Round 2
  • Vote: I like it
  • +217
  • Vote: I do not like it

Comments Comments (270)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

As I my teammate for VK wouldn't​ be able to participate can I participate in Round 409 instead? Because last time all teams qualified for Round 1 needed to participate in the Round 1.

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

    Actually, there should be no difference for you: in which round to participate. Except the fact, that if you'll write official one, you'll have chances to pass to the next round.

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

      But so if I fail my teammate's rating will be ruined too :D

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

    Bro! it's round 409 actually. :D All the Best

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

Good luck to all participants!!!

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

T-shirts?

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

Unfortunately Clashes with Manchester United Vs Chelsea!

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

    And the F1 Grand Prix!

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

    You can win wildcard round, similar to winning Europa League for League Champions ticket :)

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

    I'm glad that man utd won otherwise i would have regret missing the contest. GGMU

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

Something is wrong with my teacher. I write in C++. He gave me A+

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

Rating prediction: div1, div2, VK-round2

Для официального раунда (VK Cup 2017 — Round 2) на странице результатов предсказание будут отображаться только для команд с английским названием. Предсказания будут доступны в английской версии и таблице

Extensions:

Have fun & high rating:)

couple of pleasant thing that happened this week
→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

lueluelue

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

Will the contest be rated?

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

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

how can I enroll this :( ?

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

    Click the third "Before contest"'s "Register now »" to join it. Have fun!

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

Hack me if you Can!

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

王大拿

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

YQY! ;(

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

Long queue for submission :(

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

long queue for submission in problem C:(

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

Midway through the exam I realized I forgot to register. I guess I'm now officially too old for this shit.

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

King Of Unsuccessful hack

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

    I was trying to find the bug of someone's code but I couldn't find it :(

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

      No coach , you wanna reach the white rate :"D

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

      whaa,u're trying to make a big leap in rating changes

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

      I was trying to find the bug of someone's code but I couldn't find it :(

      Hah! Did you find anything wrong with my Div2.A solution? =)

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

        Hey man , he qualified for ICPC , but i think he has a problem with Mike Mirzayanov

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

      too late :) worse

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

      Mhammad1 Well, we didn't get the visa for ICPC this year, but at least now you are famous :D

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

      Stress testing isn't a good strategy for hacking.

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

Problem difficulty is like AACCE lol

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

    How to solve D?

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

      For each adjacent vertexes A, B and C: find the distance between point B and line AC, divide the distance by 2. Choose the minimum.

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

problem title: "E. Verifying Kingdom"

problem statement: described formally — no story about a kingdom or something :D

same thing with some other problems :D

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

    I think the writer's goal is to increase letters V and K as he can :D

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

didn't enjoy the contest :p

quite a boring one

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

Please look into the user sp_502, and submissions of user newworldorder, it seems first user is just hacking second user in every 3-4 minutes to top the leaderboard. :P

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

Problems statements are Short and Clear.

Nice Problem Set.

Thank You.

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

I solved div.2 D quite fast, but it didn't pass presets. After thinking about possible bugs about 50 mins and stress-testing the solution I decided to change the language implementation from MS C++ to GNU C++ and it passed presets. So the question: is it honest to set such a high precision requirements that submission verdict heavily depends on C++ compiler choice?

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

Logic for Div2 C please?

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

    Binary Search

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

      More details please.

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

        Binary search for absolute charging time (l): One device needs (l*a[i]-b[i])/P time to charge in that period(l). Take the sum of these positive values ant compare it to l.

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

        Binary search the answer. for the device i: if b[i] — a[i] * time < 0 , you will need -(b[i] — a[i] * time) units of power. and check whether p * time >= AllThePowerYouNeed

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

        Take lower limit of ans as 0 and upper limit as 1e18 . Now since you know the time for which each device work thus you know the total power needed (req (power)=a[i]*mid) . If the power already present >= req (power) then continue to another device else the required power will be supplied from the plug and time required ( plugging time for this device ) for that = (req-b[i])/p ; this way sum up the time required on plug for each device (= totaltime). If totaltime>mid then r=mid else l=mid because if total time is more than the mid then answer should be less than mid otherwise answer can be greater than or equal to the mid . To check if we can use the devices indefinitely : check if mid>=1e17 after the binary search loop , if this fails then ans is mid .

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

          How did you choose the upper limit as 1e18.

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

            Randomly. I did the same thing and payed for it :)

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

              I chose 1e18 and it passed systests.

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

                mine for 1e15 is TLE, but 1e10 accepted with 93ms

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

            I think the upper limit is 1e10 because the worst case that I can think of is you have n = 1e5 devices, The charger is as fast as possible but doesn't make the devices work for infinity p = 99999, each device uses minimum amount of power a[i] = 1 and has max starting power b[i] = 1e5. Now the time needed will be 1e10 because you originally have 1e10 power in total (summation of b[i]) and each second you lose one power in total (lose 1e5, one for each device.. and regain 99999 from the charger) so it will take you 1e10 seconds to run out of power.

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

    Imagine that there is no charger. Then your answer would be the min(b[i] / a[i]). (The one that finishes faster).

    But the charger makes you able to add this b[i]. So Binary Search the answer.

    When you are checking if they can last x seconds or not, you will need to sum needed = sum(max(0, x — (b[i] / a[i])) * a[i]), which is the energy needed by everyone to last x seconds. and if needed <= stay * p then you can charge them and make them last <= x seconds.

    BTW max(0, x — (b[i] / a[i])) is the how much time we need to add to the ith device to complete at least x seconds.

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

How to solve Div2 D?

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

    Point-line distance

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

      I know that it is minimum altitude of a triangle, but checking all N^3 triangles TLEd.

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

        For line (i, j), just check point i + 1 and j - 1

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

          I tried doing that (well, even more, since I also checked i — 1, and j + 1) but got WA on pretest 4, but I calculated the area of a triangle, so maybe it was just double precision.

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

            Did you find ur mistake? I have wr on test 4 too.

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

              Yeah, it was precision error, changing double to long double gave me AC.

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

          I got AC checking only adjacent triples i,i+1,i+2

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

      Can you elaborate it with some details.

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

      Point-line distance

      From what point? To which line?

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

        From one point to line between two near points(You should calculate the distance through perpendicular)

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

          From one point to line between two near points(You should calculate the distance through perpendicular)

          Is that the required distance D?
          Can you give a prove for that (its not obvious for me)?

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

            If D > (distance from one point and line between two its neighbouring points) / 2 then we can place points in such a way that we will have not convex polygon.

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

              Could D be less than (distance from one point and line between two its neighbouring points) / 2?

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

                Sure, we should take minimum of such values for all triples of consecutive points. Besides, we should also satisfy the condition that the answer is less or equal than half of any edge of the polygon(not to have intersections).

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

How to solve Div 2C?

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

    Binary search on the time. Calculate how much under 0 each device will go if it runs without charger for t seconds.

    If the sum of these values that go under is less than or equal to the capacity of the charger * t then that time is valid and you should try a higher one. Otherwise go lower. At least I think that'll work.

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

Similar problem to Div.2 E: http://codeforces.me/problemset/problem/487/C

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

    How did you find it?

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

      Just googled "prefix product sequence".

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

      I found it also, when I searched for prefix product. I didn't know what does it mean, so I just googled it.

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

        Well, it looks like googling that problem didn't help anyone. That's a relief for me :)

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

          487C was at least as difficult as this one, and I don't think the idea of that solution could be easily rewritten for this one.

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

          But I remember the problem and its solution without googling :)

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

    Imho, that problem differs from today's very much

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

I think user sp_502 has cheated because he hacked a same user for 10 times

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

I tried to hack a solution when the contest was only ten minutes or something. But Judge kept me in waiting queue during the whole contest and after 50 minutes someone hacked the solution and got the points and i'm still in waiting queue. Why this was happen? Also I didn't get negative point :(

I was pretty sure about my hack case.

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

    this happened because someone hacked it before u and was waiting in the queue for a longer time than u were. u didnt get negative because the problem was already hacked by someone else before so ur hack was not taken into consideration

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

My idea for div2B was: for every 3 adjecent points calculate the distance between the middle one and the segment, formed by other 2, then halve the result, and take minimum of all these values, but it didn't even pass the 3rd pretest(

Could anyone point out where I've gone wrong?

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

    True

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

    I did nearly the same and passed pretests. Did you consider n,1,2 and n-1,n,1?

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

    Maybe you have forgotten about first and last points, because my solution is same.

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

    You also need to to halve the distance between two consecutive points.

    Edit: That distance is actually never optimal. Explanation Here.

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

    If it's point i, then you have to check it's distance from the line (i-2, i-1) and (i+1,i+2) line also. I did it, maybe it's still not sufficient, or my implementation was bad, but I failed on pretest 4.

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

    You also have to take the minimum of half of each polygon side lengths. Because if somehow the radius is bigger than half of a side, you can move two ends of that segment making the polygon intersect itself.

    Edit: forget it.

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

      Height / 2 will always be smaller as the side of polygon is hypotenuse of the right triangle formed by the height, the side and the base(split at the point of intersection).

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

      I didn't consider this... And passed pretest???

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

    I binary searched the answer, checking if its possible the same way as you described. At least it passed pretests)

    P.S. Maybe you forgot about p[0], p[n — 1], p[n — 2] or smtj like that?

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

    I did the same thing and it passed. Maybe you initialized the answer wrong. The maximum possible distance was 10^9*sqrt(2)/2.

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

    Probably precision issues. I did the same, for some reason it was accepted after I output the answer with "cout << setprecision(10) << ans << endl;".

    By default, cout outputs 6 digits after the decimal point, which I thought would be just enough, so I'm not sure why this changed the verdict though...

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

    thanks for replies, guys :)

    I was considering i, (i + 1) % n, (i + 2) % n, so indexes are not the case. Well, now I am confused, might be precision issues, but at least I know the approach wa correct)

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

      I think you just have to print answer with greater precision.

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

    Mine failed pretests with double, but passed with long double in C++11.

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

How to solve Div. 1 C ?

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

    https://math.stackexchange.com/questions/2149600/prove-ax-equiv-b-mod-m-iff-b-equiv-0-mod-gcdm-a/2149624

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

      How does it help us?

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

        After this , you need a sequence of numbers a1, a2, a3, ..., ak such that gcd(ai, mod) divides gcd(ai + 1, mod) 1 ≤ i < k , so sort all the allowed numbers according to their gcd with mod and do dp.

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

    You can go from a prefix product x to some other prefix product y if and only if gcd (x, M) | gcd (y, M). (that is, there exists a number z so that x * z % M = y if this condition holds). Now, for each value d | M, you can keep cnt[d] the number of numbers q that have gcd (q, M) = d and do not appear in the given list and some dynamic programming. If we write down the numbers gcd (prefix_product[i], M), we'll get some clusters (contiguous groups with the same value). You can keep dp[d] the maximum length of an array whose last element q has gcd (q, M) = d. There are few divisors for M<=200.000 (160 in worst case), so we can compute the dp in complexity O(number_of_divisors^2). In order to get some z for given x and y so that (x * z) % M = y, you should use modular inverse. To better understand it, look at the numbers' decomposition. Take care at the fact that the modular inverse of a number t is defined if and only gcd (t, M) = 1

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

      What does the symbol | mean?

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

        a | b means that b is divisible by a. Sorry, in my country it is a recognized notation

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

    First try to find max prefix modulo sequence. Prefix modulo should hold condition that gcd(pre[i],m) is divisible by gcd(pre[i-1],m)

    Using that condition,by dp we can find prefix modulos and then some inverse modulo operations on it gives the sequence

    Here is my submission

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

Did you noticed that names of problems starts with "V" and "K" letters?

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

That feeling when you finally fix the bug and your solution runs ... one minute after contest ends ...

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

    same

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

    In Div1 D, I finished coding but the first example didn't work. After contest I found that I calculated G(0) + G(1) + ... + G(999999) instead of G(0) ^ G(1) ^ ... ^ G(999999)..........

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

the same code for div 1 B got WA 4 by using C++ 14 and passed pretest by C++ 11.

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

Is div2E/div1C just brute forcing on factoring of m then using dp to find the chain of factors the give the largest answer?

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

    It doesn't look so. What will be the chain of factors for this input:
    3 10
    2 9 1

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

      1 -> 2 -> 10 for 1 we get 3, 7 for 2 we get 4, 6, 8 for 10 we get 0 so the answer is 6

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

        I am sorry, but I don't understand what you have written.

        What is this? 1 -> 2 -> 10

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

          That's a chain going through the divisors of 10. His approach is correct. Edit: just a quick explanation: if you are on the divisor d, you can get to any number x such that gcd(x, m) = d and to the divisor T such that T % d == 0.

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

            That's a chain going through the divisors of 10. His approach is correct.

            Probably, I didn't understand the approach in the first place. Let me clarify a few moments.

            The divisors of 10 are: 1, 2, 5, 10.

            1. How do we go from this sequence of divisors (1, 2, 5, 10) to the chain 1 -> 2 -> 10?
            2. How does this chain 1 -> 2 -> 10 help us find the final sequence of length 6?
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              You have: (btw the divisors are 1, 2, 5, 10)

              0, 3, 4, 5, 6, 7, 8

              divide those numbers by their gcd with m

              • 1: 3, 7
              • 2: 4, 6, 8
              • 5: 5
              • 10: 0

              order the divisors increasingly and d[i] = i'th divisor of m.

              dp[i] = max(dp[j] from j > i and d[j] % d[i] == 0) + number of numbers with gcd(x, m) == d[i]

              The answer will be on dp[0] (it will be 6) and the path of the answer will tell you which numbers to pick (the path is the chain).

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

          Notice 1 divides 2, 2 divides 10. I first picked all the numbers that have gcd(X,10)=1, which are not banned from input. Then, I went to numbers that have gcd(X,10)=2, which are not banned from input. Finally, since 0 is not banned, I put 0 at the end of sequence. Because you can only reach number B from A if gcd(10,A) divides gcd(10,B)

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

Div.1 D makes me hate mathematics.

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

Seems like he used the technique described by the bots in previous round :3

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

    It's interesting that how he can be in same room with his fake account, is it just coincidence or there is a trick :D ?

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

      In div1 if you have ~20 accounts then there is high probability that 2 ids will be in same room :P in div2 it works sometimes too :P

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

again, div2C/div1A, like some problems in previous contest, is containing 100 kilometers long input file

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

Did someone come up with an upper bound for the answer in Div2 C ?

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

    I think it should be around max(n)*max(initial_power). I dont have a proof but I generated some test cases and they gave me this idea

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

      Your idea is correct because generate power must be lesser than sum of usage if the answer different than -1. Then it is obvious that the loss of bi is at least 1 per sec and so upper bound is sum of bi .

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

    I used 10^20, it was enough. I think the bound is somewhere like 10^10, if you consider that all n (10^5) devices lose 1 power per time unit, (goes out after 10^5) then it's 10^5*10^5=10^10.

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

what are hack case for div2 A ?

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

Any tip for Div1 D?

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

    Instead of f(S)=x consider f(S) ># x where a ># b off a's i-th digit is larger or equal to B's i-th digit for every i. To compute it and to get actual result from this auxiliary results do something similar to Fast Subset Convolution.

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

      Fast Subset Convolution?

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

        Fast Subset Convolution.

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

        Fast Subset Convolution is a technique to solve a following problem. We are given set U and a function (P denotes power set). We need to compute function g so that . Bruteforce way is O(3n), using FSC we get O(2n·n).

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

undoubtedly today's best performer

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

    Zoomed screen 300%, still can't see picture :D

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

      He got -72 hacks, and -2192 point overall, with 3 solved problems.

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

OMG, so many WA's for problem Div.2 C

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

Its showing failed system case for div2 D for all users, but displays accepted when clicked on it.

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

Fatalities everywhere in Div2 C and D 0_0

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

Why does the system say my problem d failed system test, but when i click inside it said i got accept?

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

what happened on div2.D?

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

    Bug on standings page.

    EDIT: Fixed now.
    EDIT: Unfixed :P
    EDIT: I think it's fixed for good now.

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

    I think if we take triplets , We should have considered 1 as well in triplets ...I did not consider point 1 in triplet :/ I do not know anything

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

    At a moment the bug is fixed.

    But now it is buggy again...

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

    hope to be fixed as fast as it can...

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

Why this submission stuck in pretest 9? :D

UPD: FIXED

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

10^8 floating operations, 2s. Not sufficient. TLE on testcase 42 :/

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

I want to cut my veins...

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

    Please don't! It is our own bad experience that is a lesson to us not to repeat our mistakes.

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

      It was just an expression for being mad. Anyways, I don't even know what was my mistake. 26422821

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

        You stop when to and from are relatively close to each other, but it doesn't guarantee you that the number in between is close to answer.

        You can simply run some number of iterations (smth like 500) and then print the result. It's counted as good practice here. :)

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

          But the correct answer will be between from and to always, won't it? I thought about the iteration number also, but I found it better to go for relative error, as the judge checks.

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

In Voltage Keepsake problem judge is rounding up, and i am outputing more precise and getting wrong answer for that :)))

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

How come got accepted problem D and it's counted as a "Failed System Test" in the final standing.

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

How come same solution fails in Java: 26436284 but passes in C++: 26436022, can somebody explain this? Both solutions are exact same and both use double, it is not as if we use long doubles in C++ or anything. Super confused right now :(

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

    I had the same problem with Java — rewrote it in python3 after an hour and it passed.. Too bad I get a really bad time :(

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

I found, only 1 person got accepted by Java in Div1A. Most contestants got failed at test 71. Is this case valid?

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

    Yes I agree and somehow it passes with EXACT same solution in C++, see my above comment for the codes. Bad time to use Java :(

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

Problem A, Java 8: I don't see a single Accepted solution with binary search... (there are a few with sorting + explicit computation though).

All of them failed on test 71, with "9995877311.0944" vs "10000000000.002304". Unfortunately, I don't see a way to download the test (as it is too long and gets truncated). Is it possible to share it somehow? I'm really interested in what's going on there. (I can try to get it part by part with debug submits, but I guess sharing is easier)

FWIW, the troubles are clearly with precision, but I don't get why they appear only in Java (I see C++ binary search solutions accepted), and so consistently. I tried known precision-related tricks (like sorting doubles before adding them together), but they don't seem to help here...

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

    There seem to be some really weird stuff going on today, I solved A with sorting + traversal in java. However I solved B with the standard approach of calculating all heights of every 3tuple in java, but got WA, then I just ported my solution to python and got accepted. Is the servers JVM broken? :^)

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

    This is a bit unexpected for me too, and we'll look into it.

    Test 71 is generated by the following code:

    n = 100000
print(n, 10 ** 9)

for i in range(99999):
    print(10000, 100000)

print(10001, 100000)
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just out of curiosity, given that you use Java yourself, is the reason you didn't see this issue when writing problems because your reference solutions did not use binary search? Or is test 71 a hack case and thus was not seen before?

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

        Test 71 was a hack. Actually it caused unexpected verdict in our java solution, but since all other c++ solutions agreed (in particular, the one that used long doubles also), we decided to mark the java solution as incorrect.

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

          Had u been a contestant trying to solve this problem in Java, and not the setter today, you would have failed to solve this problem right ?

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

            I understand the frustration, and I have experienced this multiple times first hand where the problem is just not solvable in Java because of the problem setter's mistakes. As a contestant, I definitely would have been upset by this as well.

            On the other hand, I think it's a dangerous precedent to set to remove hacks that are difficult for a particular language to handle. I think the ideal solution is that problem setters should learn from this and set lower bounds or make sure precision is not as big of an issue (for example, there is no need for me to set a_i,b_i <= 10^5, and I could have set a_i,b_i <= 100).

            Anyways, I think the most similar situation is in round 284 where denormal numbers caused some submissions to TLE: http://codeforces.me/blog/entry/15356. In that case, the decision was to keep the contest rated. I feel that that situation is closest to this situation, so that's why I think the results should still stand.

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

      We managed to find a java solution that works. We believe the problem is that the comparison A <= B when A,B are very large may not be precise. We're not sure why it only shows up in java.

      More specifically, the inequality we want to check is sum(a) * t — sum(b) — p * t <= 0, for devices that need to be charged. This may be imprecise, so we can compute it as sum(a * t — b — p * t / n) <= 0 instead. This seems to agree with all of our other solutions right right now.

      Unfortunately, I don't think we will change results, but I think next time I'll lower the bounds of such a problem more so precision issues like this are less likely to come up.

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

        It makes sense that summing many doubles is less precise than multiplying long by double. Why does it only matter in java is less clear to me.

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

        Interesting. I didn't by any means imply that results should be changed in any way — jury answer is clearly the right one.

        I tried to debug what's going on, but I still don't understand what happens there :( Apparently function f(t) = sum(a * t — b) / t — p is very non-monotonic around t = 1010, and jumps around 0 like crazy even with small changes of t. I'm not sure why the same doesn't happen in C++ — maybe it gets magically optimized to use higher-precision arithmetic.

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

          I checked some solutions from the top of the leaderboard, and they fail if compiled with -ffloat-store flag. Nothing new, though.

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

        I don't find it pretty fair to leave the results as they are.

        The fact that the same algorithm can pass in C++ and not in Java, is pretty unfair. It should be samely easy to get AC in every languages. Even the sentence We managed to find a java solution that works tells, that this was pretty hard for Java programmers. We couldn't have known, that Java double is buggy at big values, so this test is pretty cruel.

        Personally, I have lost 71 rating instead of winning something like 30, because of this test case. I'd be happy if this test case could be ignored for Java users, as a lots of people got WA on this test while using the right approach.

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

          In a problem with bigintegers, will you want all big tests to be removed for C++ submissions?

          You choose a language yourself and it's up to you to know its weaknesses. A solution is good if and only if it passes all created tests — not if it passes all tests except for those hard for this language.

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

            I think it's something else with C++ big integers. If you need big integers, then the whole problem is about big integers, and handling hundreds or thousands of digits. You can know, that you can't use C++ there. But here, the problem wasn't about the double's precision at 10^10. Even Lewin said, that this result was unexpected, so they didn't make this to have problem with double's precision.

            In C++ everyone knows that it can't handle big integers, because there is simply no datatype for that. But in Java, as you can see from the comments, and submissions, most of the people didn't know, that the precision of double is not enough.

            On the other hand I get your PoV, and you are mostly right, but I still think, that this problem was unfair for java users as a div2 C.

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

        Finally, I achieved to solve this problem (26441610) in C# by summing up like segment tree. Now, I'm really interested in whether we could hack this or not and how we should manage real number!

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

    Got AC with Java 8 & binary search: 26437377.

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

Hi, can anyone explain me this?

CLICK

Why the green guy, who got 1232 points doing A and B got +203 points when me and other green people with 1230 points A and B done got only 30-50?

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

    I believe that 'that green guy' got his solution on problem D accepted.

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

What is wrong with this solution http://codeforces.me/contest/801/submission/26427548 for Div2C / Div1A

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

    you have to output -1 if it is possible to keep all devices on indefinitely, you didn't do that.

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

      I did, check line 53. If it is possible even at max_limit, I output -1

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

cout gave me wrong answer on test case 3 26434138 later after the contest just printed output using printf with 8 decimal places and got AC 26435680 :/

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

what's wrong !!?

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

Two problems double WA , long double after contest AC , i hope that's not intended.

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

how much time will it take to update ratings?

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

    Probably something is wrong with the checker, lots of people got WA on div2 C with java, so they'll check it. It may take some time.

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

In div2 C , what happens wrong when we compare the answer to the upper bound in binary search for the infinity case? 26437983

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

Can someone explain to me why my solution for Div.2 C fails with binsearch upperbound 1e11 or 1e9 but gets AC with 1e10 ?

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

    It fails with 1e9 because it is too small and fails with 1e11 because you use the == operator. Never use that thing with doubles.

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

      Thank you so much! Using relative error it turns out that I can use upper bound up to 1e16. The only not clear thing here is why 1e9 is too little. I mean how to find upper bound for the answer in this problem?

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

        For the following test it is clear that each second our total sum of b[i] decreases by 1 every second (as p — sum(a) == -1). Our total initial sum of b[i] is 10^10, thus we can see that the answer will be 10^10 and that this is the worst case. 

        n = 100 * 1000;
p = 100 * 1000 - 1;
print(n, p)
for i in range(n):
	print(1, 100 * 1000)
        → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I am really not able to understand why i am getting TLE on test 74. Please help me!!! Code: 26437499 UPD: It got accepted when upper bound = 1e10 but fails when upper bound = 1e12 or 1e18 , i don't know why?

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

    Probably because you lose precision and can't get a difference of 1e-5 when the numbers go too big so it creates an infinite loop.

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

      How do we resolve this issue?

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

        Iterate a fixed number of times (like 100-200) or use relative error

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

          Can you please point out what edit i need to make in my solution.

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

            http://codeforces.me/contest/801/submission/26439427

            1. look at the binary search look (it's now a for, not a while)

            2. look at the infinite condition (it's using now relative error instead of absolute error, the same could be done for the first loop)

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

              Thanks for the explanation :) , my solution was also getting stuck in Infinite loop whenever the ans was calculated correctly, so I used clock to break the loop. Anyways it failed sys test due to 1e9 Solution

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

I cannot believe I passed Div2 C systest. I have no idea how precision works here. I just keep adjusting parameters until I passed pretest.

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

26431601 has WA 28.
I have a variable ans, the initial value of which does not matter.
After some attempts:
1. ans is not defined -- WA 28.
2. ans = INF, INF = 1e9 + 7 -- WA 28.
3. ans = 1e9 -- WA 33.
4. ans = 2e9 -- AC.
5. ans = 0 -- AC.
Can someone explain me WHY?

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

Huge minus to author's karma for Div 2C/Div 1A problem. They decided to not accept Java's double precision and didn't give enough time for BigDecimal solution. So if you use c++ and long double you are fine if java — please fail on test 71. BTW: solution with hardcoded value for such "tests" receives "Accepted": http://codeforces.me/contest/801/submission/26438478

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

    You're fine only with GNU c++. With MS c++ I also had precision problems using the same code.

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

Can Someone explain why are solutions for Div2/C got TLE when submitted in Ms C++ 2010 and got Accepted when submitted in Gnu++14? here's my code in Ms got TLE at test 66 26436248 and Accepted with exactly the same code on Gnu++14 with time 78!! 26436769

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

Lol, such a simple solution for div2C, and I spent a hour for solving it in much more complex way

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

I'm the one to blame for the same number of points for two last problems. I solved the last problem quickly but struggled with the other one a bit. I even proposed to swap those two problems... (fortunately, it didn't happen).

And btw. I'm surprised by precision issues in Java. Is there any fix for that? Maybe we can simulate float values with bigintegers in Java (if it's necessary)?

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

    I tried to use BigDecimal, but it is too slow and TLEs. Maybe there is some way to be very careful with the precision of the BigDecimals and make it work, but have not seen any solution like that so far. meijun has this submission though, 26437993, that uses streams somehow and passes in Java, but I don't really see how to intuitively know that this should work.

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

Is it normal to have a submission failing the second pretest (which was part of the sample in div1D) counted as wrong submission? It was just now when I saw that I have -50 on that problem because it failed second sample (of course I could have made sure it works, but I sent it just about 2 minutes before the ending and, as I was running out of time, I didn't check all samples).

Also, in the first problem, I used custom invocation to test my first attempt for div1A on a test with N = 100.000 and I saw it was running in 2200 ms, so I decided to resubmit it with smaller precision (170 iterations of the binary search instead of 200). The new source worked in custom invocation in 1930 ms, but on the final tests it worked in just 300 ms, which makes me wonder: is custom invocation running the code with the same speed as it does whilst system testing?

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

    A participant might send a wrong code, print some debug info, or their solution can be wrong in CF system (e.g. small MAX_RAND). These mistakes aren't usually penalized thanks to friendly checking of the first test. Doing the same for other samples would help mostly if a participant is lazy or doesn't have time to run his solution on those tests — these arguments aren't that strong. I think the current system is ok.

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

    To your first question yes it is normal, only incorrect submissions to the first sample / pretest are not counted. I don't claim to judge if this is fair or not, however there are cases where it is not trivial to know if a solution passes the samples, say in constructive problems with many possible solutions, and thus making all submissions that fail on samples not count would be a big departure from current policy.

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

    Thanks for the information. I just wanted to know if this is supposed to happen. I thought that CF ignores all solutions that fail samples, not necessary the first test. Soo, the answer for the first question was clarified. Can anyone answer the second?:)

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

Can someone look at my solution for Div1 B? I'm trying to use Binary search and moving the points closer to each other (perpendicular) and then computing the cross product to see if it's convex or not.

Please help: http://codeforces.me/contest/800/submission/26441326

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

For Div2-C / Div1-A
This is AC code and this is the WA code.
Only difference is, for -1 case, in AC code I have : 

if(check(1e14))

and in WA code I have: 

if(ans >= (1e14))

Can someone please point out what is my mistake here. Is there some kind of overflow which breaks my binary search to converge on a solution.
The WA solution gives answer 99999997522874.859000000 on test-74, that is, it converges on a solution.
Thanks

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

    I had to face the similar problem.

    WA

    AC

    Can't understand which statement caused the overflow, if any.

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

    Strange behavior with my submission:

    Submited under MS C++ during the round and got WA71: http://codeforces.me/contest/772/submission/26418943

    The same code (only casting to double in printf) submited under GNU G++ 14 get AC: http://codeforces.me/contest/772/submission/26460846

    How is it possible?!

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

    This is accuracy error with doubles, it's not good to compare >= when using doubles. Try to change (ans >= (1e14)) to (ans > (1e14)-EPS), EPS is a low number, like 1e-5. In this case 99999997522874.859000000 is very close to (1e14), but not equal, then it's good use EPS when comparing doubles.

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

      I actually think the difference between 1e14 and 99999997522874.859000000 is not very small, particularly not as small as something like 1e-5, (2477125.14063 to be exact).
      Even then, here is the same verdict after the suggested modification WA

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

        Try to submit in g++14, double is more precise. I guess the solution lost precise in (thisAns * v[i].first).

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

Hello... Why I don't rated in this contest I solved a question A

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

My team submited this code under MS C++ for problem B in 22 min of the Round 2: http://codeforces.me/contest/772/submission/26422281 — got WA 4.

The same code submited under GNU G++ 14 get AC: http://codeforces.me/contest/772/submission/26461048

IDK what's wrong with MS C++ in codeforces, but with problem A http://codeforces.me/blog/entry/51577?#comment-355114 — my team lost 1390 points and, ironicaly, 100 place. :P

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

    Different compilers generate different machine code, i.e. different set of assembler commands. And differently process floating point numbers. Try this code under MS C++ and GNU G++ 14 (you can use Run option):

    #include <iostream>
int main(){
  std::cout << sizeof(long double)  << std::endl;
  return 0;
}

    It turns out that MS C++ prints 8 (bytes), while GNU 14 prints 12 (bytes). It means that under MS C++ long double is less precise than under GNU C++ 14. Moreover you could think about computing triangle area with more precision in problem B. In this case double would be enough.

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

      Thx, correct explanation — extinguish burning )

      But anyway there are submissions which using double (not long double) with 8bite size and the get AC. Example: http://codeforces.me/contest/772/submission/26419872

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

        http://codeforces.me/contest/772/submission/26419872

        You are right. It almost same as your solution. And again, this AC double solution was sent to GNU G++. In fact, it produced a better assembler code for implementing function f(...). The same code sent to MS C++ generates WA 71: http://codeforces.me/contest/800/submission/26463062

        But if we rework a bit f(...) function with Kahan summation approach — we get AC, even on MS C++. See this attempt: http://codeforces.me/contest/800/submission/26463142

        The main problem is in this line:

        double add = T * a[i] - b[i];

        UPD. In test 71, T*a[i]-b[i] ~ 10^14. Then we get the sum of 100000 such numbers, which is about 10^19 and does not fit into double precision. Lower bits of final value are just truncated and this leads your binary search to a smaller value, than test requires. So no magic here, just a bit of luck for GNU users :) I suppose GNU organizes all intermediate computations within floating-point registers (which are 10 bytes and more) with no writes to RAM.

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

hello world! :)

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

Very quietly I take my leave

As quietly as I came here;

Quietly I wave good-bye

To the rosy clouds in the western sky.

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

Why I can register for Vk Cup Wild Cart round 2 only as individual participant? There is not option for registering as a team(I took part in both Vk cup rounds as a member of a team)

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

The unpaired "(" in D makes me feel puzzled and make mistakes in the first code

→ Reply