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

Автор Tigutor, история, 8 лет назад, По-русски

Всем привет!

Через два дня, в 19:35 состоится Codeforces Round #339 (Div. 1 & Div. 2) Этот раунд необычен тем, что мы, его составители — обычные школьники, объединенные тем, что вместе занимаемся на кружке в 179 школе. Для нас этот раунд — первый опыт и мы постарались сделать его максимально интересным и безошибочным. Я приглашаю вас всех писать этот раунд, потому что задачи будут решаемы, но при этом даже tourist-у придётся подумать над некоторыми :)

Под началом и полным контролем Михаила Тихомирова(Endagorion) задачи для вас готовили: Егор Чунаев(ch_egor), Василий Алферов(platypus179), Дмитрий Саютин(cdkrot), Тимофей Гутор(Tigutor), Мария Федоркина (crossopt). Кроме того, задачи придумывали: Михаил Сорокин(themikemikovi4), Сергей Алейкин(Derrior). Отдельное спасибо Глебу Евстропову(GlebsHP) за помощь в подготовке контеста, Маше Беловой(Delinur) за перевод условий на английский язык, AlexFetisov и winger за тестирование, и, конечно, (MikeMirzayanov) за уникальные системы CodeForces и Polygon.

Раунд будет проведен по стандартным правилам Codeforces, сначала — претесты, потом финальное тестирование, внимательно продумывайте все случаи в своём решении.

Удачи всем на контесте!

UPD Разбалловка: Div 2. 500-1000-1750-2250-2250, Div 1. 750-1250-1250-2000-2500

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

Div1:

  1. TankEngineer

  2. KAN

  3. Petr

  4. Um_nik

  5. snuke

  6. matthew99

  7. jcvb

  8. superpear

  9. pashka

  10. fsouza

Div2:

  1. mingaleg

  2. Ronnoc

  3. BoQiR

  4. maks1906

  5. zloyplace35

  6. huansuz1

  7. 2016

  8. Danlark

  9. MrPapaya

  10. bohuss

UPD Разбор

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

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

Poor english, let's hope the english statements will be better..

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

    Yes, i dont speak english very vell, but lately we'll correct this post. English statements will be created by Delinur, and she know English very well.

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

    Statements were pretty clear, thanks for that!

    problems were also nice and interesting, I really liked C div1 and D div1 :)

    my only complaint is A div1. there was no idea behind it, just a stupid geometry formula.

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

i has very very good expect contest, so many prepared people and i like endagorion contest because they very very good.
best hope much good statements

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

Yeee, another codeforces round rated. Wishing ratings high to all, hope math problems to see.

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

Google Translate would have done better. :D

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

      "we, its drafters — ordinary students, united by the fact that together are engaged in the circle in 179 schools"

      Somebody help, my sides are leaving the orbit

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

      Is this the original post? Hillarious!!!

      because the problem will be solved, but even the tourist-y have to think about some

      I bet touristy will scratch his head for the entire duration of contest, as to why the drafters have given solved problems in a contest :D

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

The statement of problem B in the last round was horrible, i was not able to understand it till the contest ends.

and from the English used in this blog, I think this one will be worse :(

please make sure the problem statement be clear and concise to be fair enough for all contestants.

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

GL & HF

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

I want to say the Tigutor-у that his knowledge of english is very good.

I'm not only fan of Ilya_MSU but fan of Tigutor too. What tasks have you created except Div1E?

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

How do you know tourist will have to think it over..?

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

Вчера — школьник в ЛКШ, сегодня — автор раунда на CF (c)

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

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

It's really inspiring to me that someone with less rating than me could hold an CF contest. Thanks!

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

I enjoy contests by lower rating writers. They usually contain interesting problems that involves creative thinking.

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

I think there are at least 3 problem eassy in CF round 339.

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

    No buddy. All problems are solvable by you if you are coder like Tourist :)

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

      why you must compare with tourist... you must do better and you must solve problems even tourist cant... you must make it solvable.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -52 Проголосовать: не нравится
Your code here...
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

A contest prepared by so many people is my worst nightmare. Hope for the best though.

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

I'm new here, could you tell me if there's a difference between Div. 1 and Div. 2? Thanks

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

    Hello, Div 1 is more difficult and is generally for contestants with a rating >=1900. On the other hand, Div 2 is easier and for less experienced competitors.

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

    When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros). The contestants who don't take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you're part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.

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

    What is your div1 account?

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

    Difference between Div. 1 and Div. 2

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

To be honest I don't think the English is poor...quite clear for me...

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

    they edited it, the last version was a bit funny but if you tried your best you could understand what it meant

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

BTW,you're good-looking:D[user:Tigutor]

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

哇塞高中生出题好厉害也!

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

I hope tourist takes part in this round and talk about the difficulty

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

Does the scoring mean that the difficulty of div2 D & div2 E is the same?!

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

    It's difficult to say. For decent div1 coders it may be same. For good div2 coders it may not.

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

задачи будут решаемы

какое растяжимое понятие :)

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

The comment is hidden because of too negative feedback, click here to view it

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

Can someone plz explain the second testcase in DIV-2 1000 points....

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

If i get WA in pretest then also 50 points will be deducted?

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

    yes, but if you don't AC that problem , there will be no decrease on your total score.

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

      this is what Codeforces says : "there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "

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

I'm becoming newbie today n:). So happy to achieve this feat. Feeling gratefull. after being hacked 3 times. :)

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

Well. That could've gone better.

But dat number of pretests... I really hope not to fail systests now :D

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

Let the hate begin!

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

Will the tests which lead to successful hacks be used for system testing?

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

Do we need convex hull in div2C or we can find the smallest radius without it?

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

    Min from distances to all edges.

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

    No, because points are given clockwise or anticlockwise direction.

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

    Look at the second test

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

    You just need to find the point on the polygon closest to P and the one farthest away, the one closest to it is going to be on one of the edges ( so check each edge), the one farthest away is going to be one of the vertices ( so check each vertex )

    Let MAX be the largest distance to P and MIN be the shortest distance to p. Then the aswer is (MAX*MAX-MIN*MIN)*PI.

    No convex hull required.

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

      the one closest to it is going to be on one of the edges

      wrong.

      Consider the segment with end points -1,2 and 1,2. The minimumis at point 0,1.

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

      I tried something similar , but I was checking for min distance on vertex too. Can you clarify a bit more why the one closest is going to be on one of the edges?

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

        It could be that the point which is closest to p is an endpoint of some line segment. In general, for a given line segment if the projection of p lies on that line segment then that's the closest point to p on that segment. If not, then the point which is closest to p is going to end up being one of the endpoints of that segment.

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

    I think we just need to find the point of intersection of each side with normal from origin to that side. If it lies within that segment, then that point is to be used to find minimum radius, otherwise, the smaller distance to origin from the 2 end points of the segment are to be taken as candidates for minimum.

    Waiting for editorial.

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

    we can do it without convex hull also. to find shortest distance of each line segment from center first find distance of both points from center and then check if the line having slope equal to the perpendicular of this lines egment and passing through center intersects the line segment or not. if yes, calculate intersection point as well as its distance from centre. take minimum of all calculated distances.this is the smallest radius.

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

I don't think Div1 B and C worth the same score. T^T

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

What's the idea behind Div2 Problem C pretest 3?

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

Div2 B time limit was a bit too strict I thought

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

    Dont use python or biginteger.

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

    No! You must check if the given number is beautiful (reading it as a string). If it isn't beautiful, save it for the final step. For each beautiful number, you have (lenght-1) zeros. So, if the number is only composed by one "1", and this one must be at the first position (because the restrictions), you don't need to do estrictly a "product", because most of them are one "1" and a bunch of "0". You need to save the sum of total zeros of beautiful numbers called "zSum". So, if the non-beautiful number is zero, the answer is zero. Else, the answer is a string composed by the non-beautiful number (remember to read it as a string, because the lenght can be 100000 as maximum) and then "zSum" zeros. I took me a few submissions before figure it out.

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

      Yes, my java submission counts number of zeros and appends a 1 or the non-beautiful number at the front. In java, it TL-ed on test 8, but in c++ it did not. Minor optimizations could drastically change the verdict for this problem. That is why I think this TL was too strict(I wonder how hard it was to pass for python users...)

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

В задаче С Div.2 у меня недостаточная точность на тесте вроде: 3 0 0 0 1 1 0 1000000 1000000 Думаю, не проходит третий претест именно из-за этого. Как избавиться? Неужели длинное умножение?

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

    Нецелочисленная арифметика там возникает только при выводе ответа, так как вместо расстрояний в этой задаче нам интересны их квадраты.

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

    Нет, третий тест на логику программы. Посмотри на картинку с комментария выше. Скорее всего, ты не обрабатываешь этот случай.

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

      Да, да, уже понял. Только хотел написать, что бы не обращали внимания на мой коммент. Но, к слову, то, что я написал выше, для моего решения также является проблемой.

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

    Третий претест — это когда ближайшая точка лежит на одном из отрезков (а не является одним из его концов).

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

      Даже неловко, что попался на то же, что и тысяча других людей)

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

        Да я и сам попался, сразу заподозрил что решение неверное (уж слишком легко), завалился на третьем претесте, еще немного подумал, 15 минут гуглил как найти расстояние от точки до отрезка, и наконец сделал :) AC после системного.

        UPD: Интересно, почему столько минусов у комментария? Вроде и чуши полной не написал, да и не обидел никого. Отпишите в ЛС пожалуйста в чем дело :)

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

          Я тоже часто не понимаю. Бывало наоборот — писал какую-то фигню и получал за неё больше десятка плюсов. Но все равно минусуют намного чаще и без видимого повода.

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

    Отличный контест, огромное спасибо. Задача А очень поучительная, никогда не получал такого интересного эффекта во время переполнения. Были мысли написать что-то, что не позволило бы произойти такому, но отвергнул эти идеи как ненужные, что является очень грубой ошибкой и хорошим уроком на будущее. От этой задачи по-настоящему получил массу удовольствия, несмотря на то, что провалился на ней

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

      Ну не могу сказать, что получил массу удовольствия от полученного взлома через 1.5 часа после начала, но это было несомненно поучительно :)

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

The test case 1 900000000000000000 12345678, helped me earn 1800 points in the contest by hacking the first problem of almost every user in my room. My best ranking ever, thanks to hacks.

Actually python rocks for this question.

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

Div2B pretest 9? how?

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

    This one checked if your program could answer correctly the case where all numbers were beautiful

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

      What?? There's always 1 non beautiful number..

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

        at least n - 1 beautiful numbers

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

        some number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.

        may may may may

        it just guarantees for atleast n-1 beautiful numbers. never for atleast 1 non beautiful no

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

        There is always one number subtracted from, but it might remain a beautiful number. Confusing, I know :P

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

      And here i was thinking i can hack some submissions because of this. -_-

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

There could be a lot of hacks on problem A if not third pretest(

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

    There could be a lot of hacks on every problem if not these good pretests :)

    I think it was a bit cruel — to give samples which can be solved with "point-point" distance, without "point-segment". And at the same time there was no crazy hack fun...

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

      I figured out the point-segment thing with concave polygons after failing the 3rd pretest, but didn't have time to code it all...

      Effing geometry.

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

I remember some people were joking about the difficulty of the problems before the contest... Anything to say? :P

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

Can anyone explain Div 2 C? My idea was to find the minimum distance from P to the polygon and the maximum distance and then pi*(max*max-min*min)

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

    I don't know correct solution, but yours fails at this test:

    4 0 0
    -1 -1
    0 2
    1 -1
    0 1

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

      My idea was exactly similar to this comment Now I'm confused

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

      You're wrong. The minimum distance doesn't have to be the distance from P to one of the point in the polygon.For example, for the test: 3 0 0 0 2 -1 1 1 1 The minimum distance is 1 while not sqrt(2).

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

    Minimum distance doesn't always lie on vertices.

    eg 3 2 -1

    1 0

    2 1

    3 0

    ans = pi*(4-1) = 3*pi.

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

      I handled that issue

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

        Then maybe you didn't handle the finite line issue.

        The min point must lie on the finite line segment.

        If you just considered perpendicular distance from point p to line then you might fail some cases.

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

        I also handled the issue and failed test 3 : maybe you forgot the edge between the first and last vertex.

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

          Maybe your solution to find the minimum distance from a point to a segment has some bugs.

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

            No I just added the last edge and it passed all tests :)

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

I think this round is too difficult ....

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

Do this sample

2

10 10

for Div2 B

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

Div2:C could also be named as "Peter and Ygrrite".

PS: Game of thrones fans will know:P

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

What is the intended approach for div 1 D?

The same question for a single query can be solved using dp on trees in linear time which led to me to come up with an approach which involved using HLD to compute dp at the bare minimum required nodes (klogk for each query I think) but the implementation was turning out to be too long so I went off to sleep instead.

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

    You can first build the auxillary tree, which is a compressed tree of the marked nodes in O(klogN) time consisting of O(k) nodes and then apply the same dp on this tree in O(k). For implementation details on how to build the auxillary tree, refer my soln here

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

Div2 A should've been named Hack those overflows.

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

My WA solution for div2 C was to compute minimum and maximum radius, find difference between circles and output. I specially handled the case in which all radii were the same(answer =0)

I claim that any radius between [minradius,maxradius] can be attained by some point in the polygon. Is this false?

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

Thanks for great div2A! 22 successful hacks are non penis canina. My hacks:

1 1000000000000000000 1000000000
1 1000000000000000000 536870912
1 1000000000000000000 536870913

536870912 = 2 ^ 29

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

Thank you for strong pretest for B!

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

I hate Div. 1 A. No interesting idea, just applying mathematical formulas and crying when wrong answer on pretest #3 shows up and then finding a typo in one of these formulas :'(

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

    I agree div1A doesn't find its place in any contest it's a stupid problem.

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

    By mathematical formulas you mean distance between points and distance between point and line? They are well known and quite easy. Actually, geometry problems are quite rare on codeforces, so it's good to have them sometimes.

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

      'Well known' — yes. Quite easy? Well... (between points ok, that's easy, but I didn't remember the formula for the distance between a point and a line and I had to deduce it by myself)

      Also there surely are many much better geometry problems than that.

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

        We have this formula on the lesson in 8 form: abs(a*x0+b*y0+c)/sqrt(a^2+b^2) x0, y0 — point's coordinates

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

    There is an interesting, simple idea. However, there's also annoying geometry. If P was inside the polygon, though, it could've made an easy div1A without the annoying stuff.

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

Any One Please tell me that is What is "Hacked".

After my submission I received a message that solution is hacked...

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

    This means another contestant has found a case when your program produce wrong output. In short, your solution is wrong.

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

    It means someone found bug in your solution and found test in which your code fails. So, your solution incorrect and you should find bug and resend solution.

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

Thank you for preparing such a contest like this!Although I don't pass Div.2 C,this contest is well! Thanks everyone!

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

At this time tourist

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

What is test case 9 in div2B?

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

спасибо за интересный раунд! очень понравилась задача div2 C. К Сожалению, когда понял свою ошибку, не успел отправить правильное решение)

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

The only problem I liked from this set was Div1 D :(

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

    Seriously? My code started working after the contest (on pretests) and it's 300 lines. I don't like it. Idea is simple: there is a stupid algorithm with time O(n+k). How to fit the queries? Just compress the graph to make it O(k) vertices. Or do you have another solution?

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

      I liked the problem D too.

      My solution is slightly above 100 lines; the idea is to compute the answer in offline and to use maps with small-to-big optimization.

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

        And I just processed 64 queries at once using bitmasks :)

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

      My solution is heavily based on LCA. We sort vertices from the query in the Euler order (it's computed in one of LCA implementations anyway). Then it's optimal to take consecutive vertices whose LCA has the largest depth and disconnect them by deleting their LCA. If LCA is also a selected vertex, we need to delete some of its children, also -1 case is handled here. The only difficulty is how to implement this idea in the best way, but anyhow it should be O((N + K)logN).

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

    What about div. 1 C? I know you enjoy palindromes :)

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

Any idea in DIV2E/DIV1C?
There are no DP, right? Just only some tricky but easy-to-implement construction? :)

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

    If we have two letters with odd ai then the answer is 0. Otherwise the answer is g = gcd(ai).

    Let's build such string:

    1) If all ai is even then we can build a block of length with occurrences of the i-th letter (in any order). And then copy that block g - 1 times, each time reversing it. Easy to see that we will have exactly g palindromes (because g is even).

    2) If we have some odd ai then g is odd. So for each even ai the value is also even. So we can build g identical palindrome blocks of the length , where the letter with odd ai will be in the middle and all the letters will occur times.

    It's not hard to prove that the answer can't be greater than g.

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

I don't like Div2B statement — take too much time to figure out that numbers could be very long etc etc. One of these tasks where statement reading takes the same (or more) time as solution finding and coding.

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

Authors at this moment...
system testing

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

    We're sorry, because The Great Admin now in taxi and hurry to start system testing)

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

When I read the problem statement of Div2.B at first, I could not understand.
By repeating to read the statement many times, I noticed that "find the product" stands for calculating , and then I could solve immediately.
By and large, the accounts for sample case are too short for me.

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

Div1A is really great for Educational Round. Authors would do better by PM'ing Edvard with this task. I know that it's wrong, but I was badly confused about this right from the start of the contest.

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

    Did you participate in Education Rounds with geometry problems? In the first one, half of solutions were hacked due to precision problems. In the second one, even the author solution had precision problems and they had to increase the error tolerance 1000 times. I think it is not a coincidence that there are no geometry problems in the last 3 Education Rounds. Too much work to get them right when your adversaries have 24 hours to find challenging cases. Unless you want to restrict coordinates to be less than 100 and set required precision to 1e-2.

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

Its very funny that participants who have 26 successful hacks on A failed A on system testing :)

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

    Anyway, they earned a lot of hacking score (besides they didn't solve the A)

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

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

Super Contest, I got a lot of fun!!!!!!

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

Что особого в тесте 26 к div. 1 B?

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

    Если кому интересен ответ:

    В моём решении перебиралось число чуваков, которых поднимем до A, а также "вторым указателем" поддерживался чувак, по которому выровняется минимум. В 26 тесте они "наползают" друг на друга.

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

      Странно. У меня из-за этого был WA6.

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

        Если интересно, вот строка генерации:

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

          Иначе говоря, n = 2054, A = 6746, cf = 807, cm = 237, M = 6525798, seed = 561626.

          Рандомный тест.

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

      Вы абсолютно правы, этот тест именно против этого, а строка генерации действительно немного страшная, потому что этот тест нашло стресс-тестирование.

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

      А если минимум — это не число из массива?

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

        Ну я немного упрощённо описал решение. На самом деле я храню индекс в отсортированном массиве элемента a[i] такого, что минимум находится между a[i-1] и a[i].

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

"Респект" тому кто составлял легенду к div1A. Просто самая лучшая..

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

Look there, running code: here

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

Why system testing stuck at 100% ?

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

Thanks to authors! : )

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

Хороший раунд, требует не просто знания алгоритмов, но и знания языка

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

Endagorion tomorrow published editorial, please wait...

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

div2 D. Skills what's the answer of 3 5 1 0 4 0 4 1

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

Another test case for Div. 2 A:

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

My code working fine on my machine but failed system test for the same code. Working fine on custom invocation also.

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

    I'm sorry to say there's no way that code's "working fine". You're getting an overflow error, checking that it doesn't become smaller isn't enough, as it can overflow into a bigger number.

    For instance, consider numbers modulo 40, k = 4. The powers are 4, 16, 24. 24 is clearly wrong, but it's still higher than 16. Your code won't detect this kind of error.

    What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right.

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

Отличный контест! Большее спасибо и успехов авторам, не забывайте сменку :З

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

Don't know why it failed system test ? code

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

Ratings Updated!

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

the worst contest I see in codeforces problem B was unclear

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

    Can't agree with "worst", was quite well overall.

    But Div2B is bad, I agree with that. Statement is over-complicated a lot.

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

      As for me it was one of the best problems during last several rounds because it is the one i have just solved and only thanks to it i have become a "specialist") And it is the one you haven't solved (from what you have tried to solve), i know(

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

        Congrats :)

        Yea I've failed on that one — algo was correct, but I didn't checked all branches correctness. My failing case was where non-beautiful number comes before 0 in sequence, so I printed "nonbeautifulnumber0" instead of "0". After self-analysis I blame my bad emotions about problem statement — because of them I wasn't very concentrated when checking.

        Besides that, its very easy problem. ProblemStatementComplexity > ProblemComplexity. I really hate these ones (and my hate is what caused these bad emotions) :)

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

That moment when you realize you failed test 3 on Div2 C because you forgot the edge between the first vertex and the last one...

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

Well done KPACUBO, good job!

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

Div. 2 D is interesting except for asking the final value of the numbers, that adds nothing but boring and time consuming implementation.

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

    I was thinking about and decided that it doesn't add a lot of code, and has some advantages.

    Firstly, you can check participant's answer more precisely.

    Secondly, you could detect [potential] situation when participant's solution is better than jury's one and report.

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

      It's true a lot of lines of code aren't added but the logic behind them takes a lot of time to think and debug properly. It costed me 15 minutes to code it on top of the 30 minutes used to find the best value.

      Indeed, but I still think the problem is already good without them, maybe just asking the minimun value and the number of maximum values used is enough.

      That's not a job for contestants.

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

        2) Yes, but first reason still applies =)

        What about your idea to output a number of full skills and the minimum level I think it is too spoilerish, because allows to guess that the maximums can be taken greedily.

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

Can anybody please help me where my div2 A problem is getting wrong. ?

Code link — http://ideone.com/EzXlNf

Input case : 1 999999999999999999 1000000000

My output : 1 1000000000 1000000000000000000

Correct output : 1 1000000000

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

    You are using doubles for l and r, doubles have precision problems. It's probably representing 1000000000000000000 and 999999999999999999 as the same number.

    You should store l and r in long long and use doubles to check possible overflow.

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

Was long intended to fail the tests (Test 24) in Div 2 A in JAVA ? I changed my code to BigInteger and it passed.

I'm sure a lot of people used the method I did. All I did was preprocess the powers, store them in a TreeSet and print subSet(l, r+1) (which is an inbuilt method in JAVA TreeSet (similar to C++ std::set)) which prints all the elements in the range [l,r]. You can do this by adding it to a vector, then sorting etc, same thing.

I don't think these solutions should have failed. This is just my opinion. Here is the WA code and AC code.
Only changed Long to BigInteger, nothing else

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

    You need to be clever if you use 64 bit ints (java long) in order to avoid overflow errors. Echoing a similar answer I already gave:

    Checking that the numbers are in the correct range isn't enough, as they can overflow and land in the range again. For instance, consider numbers modulo 40, k = 4, and [l,r] = [3,25]. The powers are 4, 16, 24, etc. Since the third number should be 64, 24 is clearly wrong, but it's still in the [l,r] range so your program will print it out.

    What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right and you don't have overflow errors.

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

    This problem basically asks you to properly handle the overflow. If there exists an input which make your code fail, then your code should fail (no excuse).

    You can deal with overflow problem without having to rely on BigInteger.

    From your code, you only need to add one line before start *= k;

    if ( start * k > LIMIT ) break;  // check overflow (LIMIT can be 10^18, or you can use 'r')
    start *= k;
    

    But wait, start * k can be overflow, can't it? Yes, so change it to this:

    if ( start  > LIMIT / k ) break;
    start *= k;
    

    You don't need BigInteger at all.

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

(http://imgur.com/JckabmD) Why is my output wrong?

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

Got WA in problem a, initially I was using long double, and I lost a lot of time because apparently codeforces wont work correctly with %Lf. So I switched to double, then I got WA because I needed long double precision. What was the point of div2 a? To get me not to use c++?

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

Почему после cf round 340 идет сразу 342, где 341 ?

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

Oh, I didn't know that Decimal in Python is so slow. TL56 on Div2 C :( And the same solution with the usual Float is correct.

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

    Its not "decimal in python", its "python" itself who is slow :)

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

      It is ok for the problems like Div2 A-C. I just mustn't be too greedy for precision in 2C=1A.

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

        Well yea, I was using it before. But then I've failed to implement some solutions because it was 40 times slower than C#. So I've decided to switch.

        And I believe two active languages is a bad idea for competitive — it is better to master one (there is a lot of cases to study, like overflows, reading 1e9 test inputs, etc etc).

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

    On the bright side you got to hack my botched handling of vertical lines.

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

Div2 problem A, good example how useful Biginteger can be.

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

    BigInteger Will get TL, Muhaha.

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

    Not sure about C++, but in C# we have "decimal" type which can store up to 28-29 digits (basically it is int128 with "floating point position").

    I also have another somewhere interesting solution for C#:

    Do all the math on regular long type (int64) inside the "checked { }" block which force compiler to check all math operations for overflow. If got an exception -> break cycle.

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

      Cool solution!

      Also, there's BigInteger in C# (in System.Numerics), which is also fast (in such small case).

      To Java Users : ...... and easier to write. 15385528

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

      I think It's fair to say that decimal can be used more like int97 or unsigned int96 rather than int128. Because mantissa is only 96 bits plus 1 sign bit.

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

Typical GNU C++:

pair<int, int> s = pair<long double, long double> (13.3, 14.4);
cerr << s.first << ' ' << s.second << endl;

No warnings.

if (rand() % 10 < a.size()) puts("0");

naive.cpp: In function ‘int main()’: naive.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (rand() % 10 < a.size()) puts("0");

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

    Sad but logical.

    With floating point types being silently and implicitly converted to integers all the way in the history of C/C++, it is only logical to extend this property to simple aggregate types as well. So, no warning, as in int x = 4.59;.

    Regarding rand() % 10, there is no way to tell that the result of int rand() is actually non-negative, except if we go and analyze the source of function rand(). In the general case, it would be impossible for a compiler to do (with halting problem as a subproblem). Why rand() returns int and not unsigned is however a good question — why, indeed?

    And the problem the compiler warns about gets quite real with if (rand() % 10 - 10 < a.size()) when the part rand() % 10 - 10 is converted to unsigned (~4 billion) before comparison takes place.

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

      I don't understand why this get warning:

      int ans2 = (long double) (10 + rand());
      cerr << ans << endl;
      

      naive.cpp: In function ‘int main()’: naive.cpp:85:38: warning: conversion to ‘int’ from ‘long double’ may alter its value [-Wconversion] int ans = (long double) (10 + rand());

      but conversion for pair<long double, long double> don't. My solution for A fails today because of that.

      And about comparing of signed and unsigned values. Why it can't compare them in the following way: if signed value is negative then we know answer, otherwise compare them in unsigned type?

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

        Oh, there's -Wconversion which is not covered by -Wall or -Wextra. Didn't remember that, sorry!

        Now that's actually strange. In my hand-rolled implementation of pair <T1, T2> (version 1, version 2), such usage does trigger a warning with -Wconversion right where it should. Perhaps the library authors do something more clever, or, theoretically, not detecting the warning in the library code might be a compiler bug.

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

        Regarding comparison of signed to unsigned, that would be a really clever move if there was a processor instruction to do exactly that. Looks like that's not the case, and the alternative is to issue a branch instruction, which may be an expensive operation on a modern PC. And C/C++ compilers usually produce efficient (while not necessarily intended) code by default.

        Also, legacy software may depend on the current documented behavior.

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

Not knowing how to know when overflow will occur in power costed me getting to expert. Oh well, atleast I learnt something today. :)

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

Can someone tell me which edge case did I miss for DIV2B ? http://codeforces.com/contest/614/submission/15367847

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

    It seems your code fails for such a non-beautiful number:

    100005

    Its start from '1' AND have zeroes. So you count these zeroes towards the final answer, but also printing the number as it is. So 4 more zeroes than necessary.

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

Picture removed.

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

    Please don't take it personally but honestly speaking I don't like this picture. A national flag is the symbol of independence and sovereignty of a country. Inappropriate uses of a national flag is not appreciable. May be you didn't do it purposely. But you should know that we can't disrespect our country by using our national flag inappropriately. As a Bangladeshi, my request is please remove this picture. It hurts my feelings. I don't want to see a big hole and some stripes on our flag.

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

    I'm not sure with the question, but I guess, the answer is yes.

    I also fell for the notorious test case #3. My solution was: find the furthest and closest point among the N given points to P. Apparently the "among the N given points" part is wrong. The closest point is not necessarily one of the N points.

    consider this case: 3 0 0 -1 1 1 1 0 2

    The closest point is (0, 1) which is not among the 3 points in input.

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

So where is the tutorial ?

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

can anyone tell me what is the logic behind div2 B ?

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

    The beautiful number are in the form of 1, 10, 100, 1000, 10000, ..., and there is at most one non beautiful number. So you only need to print the non-beautiful number, followed by as many zeroes as there can be. However, you should be careful with the case where there is zero or no non-beautiful number.

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

WOW!!! We have 9 Legendary grandmaster now!!! :D

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

    There were only 5 after the rating changes if I remember correctly. I wonder what happened, wasn't the new system supposed to counter rank inflation?

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

I passed the pretest of problem D with a little issue, and I skipped my old solution and lost 145 points when I found the issue. But when I submitted my old solution today I just surprisingly found it pass the system test.

Your text to link here...

This is the correct one. Just press "compare" to view the old code and the obvious issue.

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

It seems that the contest will be with no Editorial :(

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

Отличный контест! Интересно вышло, что по кол-ву взломов самой сложной задачей оказалась DIV2 A! :)

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

NICE

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

В списке посылок DIV1 в начале раунда видно огромное количество решений DIV1A "по вершинам" и фейлов на претесте 3. Причем цвета участников самые разные, даже красные есть с таким ляпом.
По-моему, стоимость задачи 750 и простота пришедшего в голову решения должны насторожить. :)
В DIV2 к концу первого часа было примерно 40 участников с пройденными претестами против 600 попытавшихся, но это не так удивительно, как попытка отослать решение по вершинам из DIV1.

Авторам спасибо за достойные задачи, требующие продумать все случаи в своём решении!
Подсказка, предполагаю, была не просто так написана :)

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

That moment when you realise that E is solvable faster than all other problems (except A). :(

Just because there's no different cases and the most complex operation is modular plus.

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

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

hello, have a question: is double on the system a single-precision float? because i believe my solution of the problem C of DIV-2 was correct and on my computer i had correct outputs and apparently on the system it has output different answers.

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

I think problem A is one of the most Hacked problems on Codeforces.

I hacked 11 and an other 15 solutions failed system test .

every one will know how to handle overflow after this contest :D .

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

just another way to describe div-2 A

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

I am getting wrong answer on Case 56 for Div2 C . i used ternary search.. Can someone please help ???

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

There wont be any editorial for this round?!

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

How to solve problem C from Div.2? I assumed that it is necessary to subtract the area of the minimum of the maximum circumference. But it is not so. Thanks

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

    Yes we need to find the area between the farthest point as radius and the nearest point as radius. farthest point is just the vertex at maximum distance from P , but the nearest point can be a vertex or an edge . So just find the distance between each edge and P and take minimum.

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

      But it wont work for the second sample test case. In that case you can see there is a traigular segment with its base towards the pivot. The distance between the line and the pivot is 1. If I use the above approach the answer would be 9*PI — 1*PI but the answer is clearly 9*PI — 2*PI.

      I am still unable to get the approach for this problem and waiting for the editorials eagerly.

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

        It works all right ! :D .

        In the second sample case farthest point is clearly (1,2) and when you compare distances between every edge and P , You will get the minimum distance with either point (0,0) or (2,0) . I'm not sure what's confusing you !

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

          but when you consider the edge joining (0,0) and (2,0) the distance between that edge and the pivot is 1 which is smaller than sqrt(2) which is the distance with point(0,0) or (2,0).

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

            There is no edge between (0,0) and (2,0). edges are given in clockwise or anticlockwise direction. You are mis-understanding the question. Read it again carefully.

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

How to solve Div2 D ?

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

Будет ли разбор?

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

How to hack a c++ solution that use the defined pow() function ?

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

И когда будет разбор?)

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

Waiting for editorial~~~

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

Still no editorial?

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

Many people don`t know English very well. And I also. But we are gathered here to develop our skills in programming!

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

Ребят, как Div2D решить? Никаких мыслей... И когда будет разбор?

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

    Отсортируем навыки по возрастанию, назовем этот массив v, будем хранить два указателя L и R. Все навыки больше R будут раскачены до максимального значения, все навыки меньше L будут раскачены до какого-то значения val, где v[l] <= val < v[l+1]. Изначально R = n-1, а L — максимально возможным. Дальше идем от R = n-1 до R = 0, двигая указатель L влево, пока нам не хватит денег для прокачки всех навыков до L до какого одного значения значения, для каждого R храня ответ.

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

Auto comment: topic has been updated by Tigutor (previous revision, new revision, compare).