Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Автор Lewin, 7 лет назад, перевод, По-русски

Привет!

Раунд 2 VK Cup 2017 состоится 16 апреля в 18:35 по московсвому времени (время в вашем часовом поясе по ссылке), параллельно пройдет стандартный Codeforces Round #409 для первого и второго дивизиона. Соревнование "VK Cup 2017 — Раунд 2" предназначено для команд, квалифицировавшихся из Раунда 1 или Уайлд-кард раунда 1. Лучшие 100 команд пройдут в Раунд 3, а у остальных будет еще один шанс в Уайлд-кард раунде 2. Те, кто не участвуют в чемпионате VK Cup, могут индивидуально принять участие в Codeforces Round #409. Все три раунда будут длиться два часа, все будут рейтинговыми.

Раунд не состоялся бы без следующих людей (в случайном порядке): KAN, Errichto, winger, AlexFetisov, LiChenKoh, xiaowuc1, MikeMirzayanov. Кроме того, спасибо компании ВКонтакте за проведение чемпионата.

Как всегда, стоимости задач будут объявлены позже.

UPD 1: Стоимости задач:

div2: 500 — 1000 — 1500 — 2000 — 2750

div1 и официальный раунд: 500 — 1000 — 175022502250

UPD 2: Разбор по ссылке (на английском языке): http://codeforces.com/blog/entry/51598

Поздравления победителям!

Официальный раунд:

  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
  • Проголосовать: нравится
  • +217
  • Проголосовать: не нравится

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

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.

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

    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.

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

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

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

TFW необходимо участвовать в раунде 2, чтобы пройти в раунд 2: Лучшие 100 команд пройдут в Раунд 2

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

Если будет участвовать один человек из команды и он пройдет в след. раунд, то пройдет вся команда? И рейтинг будет меняться только у этого человека?

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

Good luck to all participants!!!

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

T-shirts?

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

Unfortunately Clashes with Manchester United Vs Chelsea!

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

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

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

Rating prediction: div1, div2, VK-round2

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

Extensions:

Have fun & high rating:)

couple of pleasant thing that happened this week
»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

lueluelue

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

Will the contest be rated?

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

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

how can I enroll this :( ?

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

Hack me if you Can!

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

王大拿

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

YQY! ;(

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

Long queue for submission :(

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

long queue for submission in problem C:(

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

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

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

King Of Unsuccessful hack

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

Problem difficulty is like AACCE lol

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

problem title: "E. Verifying Kingdom"

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

same thing with some other problems :D

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

didn't enjoy the contest :p

quite a boring one

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

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

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

Problems statements are Short and Clear.

Nice Problem Set.

Thank You.

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

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?

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

Logic for Div2 C please?

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

    Binary Search

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

      More details please.

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

        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.

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

        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

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

        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 .

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

          How did you choose the upper limit as 1e18.

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

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

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

            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.

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

    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.

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

How to solve Div2 D?

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

    Point-line distance

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

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

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

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

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

          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.

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

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

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

      Can you elaborate it with some details.

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

      Point-line distance

      From what point? To which line?

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

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

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

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

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

            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.

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

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

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

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

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

How to solve Div 2C?

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

    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.

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

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

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

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.

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

    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

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

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?

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

    True

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

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

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

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

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

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

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

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

    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.

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

    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.

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

    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?

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

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

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

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

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

    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)

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

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

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

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

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

How to solve Div. 1 C ?

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

      How does it help us?

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

        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.

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

    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

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

    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

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

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

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

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

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

    same

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

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

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

Сначала прочитал название задачи C как "Возмутительный Контест". Видимо, не зря

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

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

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

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

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

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

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

      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

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

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

        What is this? 1 -> 2 -> 10

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

          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.

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

            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?
            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          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)

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

Div.1 D makes me hate mathematics.

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

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

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

    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 ?

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

      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

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

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

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

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

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

    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

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

      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 .

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

    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.

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

what are hack case for div2 A ?

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

Any tip for Div1 D?

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

    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.

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

      Fast Subset Convolution?

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

        Fast Subset Convolution.

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

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

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

undoubtedly today's best performer

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

Бан?

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

http://codeforces.com/contest/772/submission/26422584 Объясните, кто-нибудь пожалуйста, как тут затлиться могло? Все другие тесты такого размера проходятся за копейки времени.

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

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

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

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

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

Fatalities everywhere in Div2 C and D 0_0

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

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

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

what happened on div2.D?

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

Ребята после сис. тестов написано, что фулл, а в таблице не засчитывает и пишет -1, исправьте

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

Что случилось с тестером по задаче Div2 D? У меня вердикт — полное решение и при этом -1 в общей таблице.

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

Why this submission stuck in pretest 9? :D

UPD: FIXED

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

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

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

I want to cut my veins...

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

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

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

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

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

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

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

          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.

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

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

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

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

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

У меня, в посылке 26427063 засчитано решение D на полных тестах (409 Div 2), тем не менее в результатах оно значится -1, при этом, при клике на этот -1, я вижу единственную строку с полным решением. Это нормально?

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

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

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

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

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

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

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

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

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

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

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

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

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

    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)
    
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

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

        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.

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

          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 ?

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

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

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

      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.

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

        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.

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

        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.

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

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

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

        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.

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

          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.

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

            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.

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

        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!

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

    Got AC with Java 8 & binary search: 26437377.

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

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?

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

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

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

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

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

what's wrong !!?

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

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

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

how much time will it take to update ratings?

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

    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.

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

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

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

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

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

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

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

      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?

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

        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)
        
»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

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

    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.

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

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.

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

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?

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

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.com/contest/801/submission/26438478

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

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

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

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

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

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

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

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

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

    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.

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

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?

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

    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.

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

    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.

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

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

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

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.com/contest/800/submission/26441326

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

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

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

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

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

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

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

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

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

    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.

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

hello world! :)

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

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.

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

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)

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

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