Автор lewin, 23 месяца назад, перевод, По-русски,

Привет, Codeforces!

Приглашаю вас принять участие в особом раунде Codeforces, который начнется 29-го января в 20:05 (московское время). Спасибо, Wunder Fund — лучшие участники получат призы и сувениры! Вот несколько слов непосредственно от компании Wunder Fund:

Мы работаем в центре Москвы и занимаемся высокочастотным трейдингом — разрабатываем высокопроизводительные системы и алгоритмы автоматизированной торговли на финансовых рынках.

Именно здесь оказываются важны алгоритмы, которые вы так любите придумывать и реализовывать — нужно быть быстрее других, сделки совершаются за доли секунд! На Codeforces разделяют нашу любовь к высокой производительности, поэтому мы и решили провести раунд. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

Мы предлагаем интересные и сложные задачи по low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь. У нас небольшая команда, поэтому вы сразу станете ее значительной частью. Разбираться в экономике и финансах не требуется, а вот алгоритмы и структуры данных это то, что нам нужно.

Заинтересовались? Присоединяйтесь к нам! Про вакансии можно почитать на нашем cайте.

Мы будем рады подарить участникам призы и подарки:

  • 1 место — PlayStation 4
  • 2 место — Xbox One
  • 3-5 места — Sega MegaDrive 16bit c играми
  • 1-50 места — сувенирные футболки Wunder Fund
  • 51-500 места — 50 футболок будут распределены случайным образом!


Заинтересовались работой в Wunder Fund?

А я хочу поблагодарить всех тех, кто помогал с подготовкой раунда:

  • GlebsHP за ревью и помощь в подготовку задач,
  • LiChenKoh и ??? за тестирование задач,
  • Delinur за переводы,
  • MikeMirzayanov за существование систем Codeforces и Polygon,
  • и, конечно, Wunder Fund за инициативу выступить спонсором раунда!

Надеюсь всех вас увидеть на раунде. Желаю удачи и удовольствия от раунда! Если вы хотите чуток потренироваться перед раундом, вы можете взглянуть на задачи моих предыдущих раундов (по ссылкам: A, B, C). Очень постараюсь порадовать вас интересными задачами.

UPD: Опубликован разбор задач.

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

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

Will it be rated round?

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

    Yes, it will be a rated round.

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

      Is it gonna be 5 problems in 2 hours?

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

        This has not been finalized yet. I can say that it will be between 5-7 problems in 2-2.5 hours (and maybe combined div1+div2). However, we have not yet decided, but I will update the post when I find out.

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

          This is neither here nor there, but do you work for / are affiliated with this Wunder Fund, or did you simply write problems for a round sponsored by them?

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

            I am not affiliated with Wunder Fund. Basically, I wrote some problems for a regular Codeforces round, but then Wunder Fund offered to sponsor a round at around the same time. I felt very lucky to have a opportunity to write for a company sponsored round, as there will be prizes and more participants.

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

    I cant understand the downvotes, i had a query and i asked it.

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

Приятная маленькая страница. Понимаю, что Вам не нужна страница для привлечения клиентов, а только для поиска талантливых работников. Но можно где-нибудь дописать что-нибудь про город, где Вы находитесь? Конечно, по фразе "Просторный офис в 5 минутах от м. Белорусская" можно догадаться, что речь идёт о Москве, но... может просто дописать одно слово в фразу "Приятный офис в центре Москвы"?

А то именно так и образуется стереотип о "москвичах, которые думают, что за МКАДом жизни нет", фразочки про default-city и прочее :)

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

    Захожу я такой на страницу с вакансией C++-разработчика. Думаю — о как забавно подошли ребята к организации приёма на работу, предлагают решить задачку. Решил попробовать себя и написать к ней решение, написал, посчитал ответ, пытаюсь отсабмитить ответ в поле "Максимальный результат", нажимаю на кнопку "Проверить ответ"... И получаю сообщение "Please include an '@' in the email address". Хм, интересно, вроде хотят получить ответ, а просят какой-то e-mail. Дай-ка я туда вобью временный e-mail на временном десятиминутном почтовом ящике. Однако же, туда тоже ничего не пришло.

    Вам точно не нужен сначала веб-разработчик?

    UPD: Впрочем, путём лёгкого изменения в исходниках, я добился того, что мой ответ был принят и сочтён правильным, и в принципе, такой скилл можно считать в рамках дефолтного багажа знаний IT-шника. Я не проспойлерил только что часть решения? :)

    UPD2: Пообщались в переписке, проблема была исправлена.

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

      Спасибо за тестирование! Не получается воспроизвести баг, написал в личку.

      Наверное, удалось вызвать "Ура!"-модальное окно?

      Если ответ сочтен правильным, решившему показывается секретный код и наш тайный почтовый ящик)

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

        Крутая почта :) "Russian HFT mafia in London celebrating X-ma"

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

Hope to have Some Short & Easy to Understandable Problem Statement in this Contest . Good Luck to All & Me.

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

Let it be combined DIV 1 and DIV 2. It will be more interesting and challenging for the DIV 2 coders as well.

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

My first reaction was, lewin is the setter, the problems will be awesome :D

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

And there will be a lot div 1 contestant participating in div 2 to get prizes :'(

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

tourist gonna play everyday PS4 :)

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

Prizes and gifts only for Div1?

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

    We are planning to merge divisions, it will be common problemset with 7 problem. Everybody can win prizes!

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

      the contests page say duration is 2 hours, but usually combined rounds are extended by half an hour, so will you keep the duration 2 hours?

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

    Nope. See 51-500 get shirts on random basis. So, try your best, you can be lucky.

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

3-5 places = the best prize

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

I can not wait my school holiday which starts with big CF round, continue with World CodeSprint, Serbian Qualifications Round, Codechef Lunchtime, Codeforces div 2 round and finishing with HourRank. This will be an awesome weekend and my parents will kill me because I am using computer so much :D

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

    Win Playstation 4 so you can use your computer less and make your parents happy :)

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

      It is bigger probability to go to some shop and steal PS4 than win some prize on the official contest :P

      Even I haven't got t-shirts which I won before 8 months :)

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

      Prizes and gifts only for Div1?

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

Хорошие призы! Шанс что-то выиграть есть действительно у многих.

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

I hope it's a combined round even though I always fail big time in these for some reason. Let's see how it goes this time :D Hopefully it can be better, especially that Lewin is setting this round. I liked your problems in Round 309.

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

PS4 for the first place, Xbone for the second place. You also think the PS4 is better?
*grabs popcorn waiting for xbox and ps4 fanboys to start console war*

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

I loved your last round specially that problem about combinatorics !!

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

What if tourist preferred Xbox than PS4?

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

memes)

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

can i join if my age is less than 18 (i am in school not university) ?

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

    They will never choose you even if you were 18++.

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

    Why on earth wouldn't you be able to join?

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

      "Note, Wunder Fund is a Russian-speaking company" -- did you noticed that?

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

        Well, technically being an adult and speaking Russian are kind of unrelated skills.

        Also, I took 'join' in his comment to mean the joining the round, not the company.

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

          well, if you didn't mean the company, then you were ambiguously so funny.

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

        Russian can be learned — maybe not in big favour today, but there were times when physists, chessmasters (etc) learned Russian just to be able to read Russian books, so why not? If you set such goal and put yourself in correct environment you can get speaking simple Russian within few months. I bet guys in WunderFund would be enthusiastic to help. But first thing to do is probably to reverse the graph. Mirroring across vertical axis would look much better.

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

    Reason is there ,and here

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

    sure!

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

As div.1 and div.2 combined, I think the contest duration should be increased at least 30 mins to have more time to challenge and solve problems

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

Легкий рейтинг++ для Div. 2)

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

Большое Спасибо компании WunderFund! Надеюсь все пройдет удачно! Удачи всем!

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

Why not Nintendo!? Though I think it's impossible for me to get one:)

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

В описание приза есть опечатка, там написано "сувениврные футболки Wunder Fund".

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

so there's a high probability that dude at rank #51 won't get a t-shirt....

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

    Higher than for rank #600 so I guess it's still optimal to fight for a good place.

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

What about rooms? Will they also be combined? Please say no!

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

Стоимость призов за 1 и 2 место примерно одинаковая... Плойка вновь нокаутирует бедную коробку...

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

I really hope that Pretests would be strong enough, because it sucks when someone spends half the time working on a hard problem and gets the same position of someone who spent all the time refreshing the room page for new people to hack.

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

    IMO, being able to hack a lot of people has his own merits. Debugging is pretty important in software development, especially video games (look: literally any Ubisoft PC Game).

    Hence, I believe that the pretests shouldn't be EXTREMELY weak. Just somewhere between "hacked by a little toddler" and "pretests = systests". Just so that people that are ACTUALLY pretty good at debugging are able to shine, while the regular coders aren't shut down either.

    With the exception of hash coders. I hate you guys with passion, you wonderful, gambling luckers!

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

      My comment is based on my experience from the last round. After I solved three tasks, I found hacks, went to my room and started hacking. There were too many people to hack that I didn't even have time to read the fourth and fifth problems properly, although they weren't hard, but I don't regret it because thanks to hacks in the Standings I was among participants who solved 4 problems. I'm just thinking that it would have been much more fun if I spent time solving the rest of the problems rather than refreshing the room.

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится -31 Проголосовать: не нравится

it will be a rated contest

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

rated contest

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

The contest is prepared by lewin ==> the contest is greatfull :D

Good luck!

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

I believe you guys forgot to send an email announcement.

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

it is midnight again where i am when the contest is supposed to hold which means that i may miss again. i wish everyone who will be in the race could get good marks.*^_^*

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

oh lots of contests these days !!

ENJOY !

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

Will the problems be sorted according to difficulty?

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

    It depends on score distribution which will be announced just before contest

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

why is it so late? I thought it is always at 2pm(GMT)

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

so combined round and only 2 hours. pretty interesting.

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

What way you will use to choose random prizes? For example in one of past cf rounds python code posted on the blog and rand seed was id of last submit in contest.

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

Is the number of problems and duration of the contest finalized?

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

When you're trying to win all prizes

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

Why so much hate for trunghai95? Whatever he comments gets down voted so brutally :p Or, am I gonna get it now? :/

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

will the rating system be changed (because it's div 1+ div2) or will it stay the same???

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

6699 registered! Interesting number (=

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

7 rpoblems and only 2 hours.

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

CF running slow for me. Not a good sign.

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

ох кажется ляжет кф скоро(

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

почему у tourist Последнее посещение: 22 часа назад

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

Why has registration been closed? Please open registration — the competition hasn't even started yet.

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

Its saying i am not allowed to view the contest.

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

Random T-Shirt Winners will be determined using the following code (with the help of testlib). We will run the code with the only command line parameter — the points of participant on the place 500 (or total points in case of tie).

====

Случайные обладатели 50 сувенирных футболок будут определены с помощью следующего кода (использует testlib). Код будет запущен с единственным параметром командной строки — количеством баллов у участника на 500-м месте (или суммой по всем таким участникам, если несколько займут 500-е место).

====

#include "testlib.h"
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    
    vector<int> places;
    for (int i = 51; i <= 500; i++)
        places.push_back(i);
    shuffle(places.begin(), places.end());

    cout << "T-Shirt Random Winners:";
    for (int i = 0; i < 50; i++)
        cout << " " << places[i];
    cout << endl;
}
»
22 месяца назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Today: funny CF handles!

[user:http://codeforces.com/profile/CantGetAnyACWhyAmISoWeak]

Doesn't seem to be true, considering he's somewhere above 60th place now.

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

short and nice questions...enjoyed solving :D

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

At problem D, when X was equal to Y, I printed N * X instead of (N-1) * X. I locked the problem, then I got hacked. Everything else was correct.

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

    if X < Y then answer is X * (vertices in longest path) + Y * (remaining vertices).
    Else answer = Y * (vertices — 1)
    Is this correct ?

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

      Incorrect.
      3 2 1
      1 2
      1 3

      Write answer — 3 (1->2->3)

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

      No, if x < y you can use multiple paths in the tree. Let m be the largest number such that there is a set of m edges which forms a collection of vertex disjoint paths (i.e. no three edges share the same vertex) then the answer is m * x + (n - m - 1) * y.

      Conversely, if y < x then the graph could be a star, in which case you'd have to use an edge with weight x.

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

      It depends what you mean by "vertices in longest path". I'd rather said "max total length of set of paths", because it could consists not connected sub-paths.

      And it surely wrong for X > Y case. It could be "x + y * (n — 2)".

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

      For X<Y, it fails if you have this:

      6 1 2
      1 2
      2 3
      3 5
      4 5
      5 6
      

      You can go 1->2->3, then jump to 4 (by a non-tree edge), then 4->5->6.

      For X > Y, it fails if you have:

      3 2 1
      1 2
      2 3
      

      Here it's impossible not to use an edge from the tree.

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

    I could not pass the 3rd pretest until the last 3 minutes, and realized that I checked long long everywhere except printf("%d"). Could be a crazy fail too :D

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

    well next time don't add unneeded ifs:)
    I bet both solution for y > x and y < x would give right answer for x = y automatically

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

Imho, 2 hours is not enough for 7 tasks. Besides that, nice tasks :)

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

    You have passed pretests in only three problems) And no one have solved G. But tasks were beautiful, I agree with you

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

What is the hacking testcase of Problem C ?

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

    For my solution it was: 4 0 0 2 0 1 0 1 2

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

    As I guess, something like this: 4 1 1 2 1 3 1 5 5 But I don't know exactly and I Haven't enough time to hack anyone with this test

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

Great to see eatmore performing again.

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

I want to ask for a bit of feedback on my code.

I coded E, a "standard" segtree (rotation angle + translation vector), except it is TLE-ing pretty badly. Could someone try to figure out why, by reading my code? It should be fairly understandable.

http://codeforces.com/contest/618/submission/15662186

Thanks in advance.

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

    Well I know from practice that sin and cos are waaay too slow. Maybe you should have saved them in arrays sin[360], cos[360]? Try it.

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

      I believe this still gets TLE.

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

        Try getting rid of cout. I do see sync_with_stdio(0), but on my system changing cout with printf optimizes 2s out of 7s (after cosines are already precalculated), even if I move << fixed << setprecision out of the loop.

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

          This is really weird. In custom test, I designed some test cases for n = m = 3e5, and they got TLE. But now it is working pretty fast when I actually submit. This is confusing to me.

          Thanks anyways.

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

            I think it's something about CF running several solutions on the same machine (but different cores). Try asking MikeMirzayanov to investigate if you're absolutely sure that it's CF-related problem.

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

Okay please tell me how to solve D. I understand that if x<y we need to find the diameter of the tree and the answer will be diameter*x+(n-1-diameter)*y. And if x>=y answer will be (n-1)*y or ((n-2)*y+x). Whats wrong in this?

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

    It's not diameter. Here's a tree.

    1 2

    1 3

    1 4

    4 5

    4 6

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

    Not a diameter, you need to split the tree into lines such that the sum of lengthes is maximal.

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

    First of all, watch out for x > y and n = 1 read the problem statement.

    And if x ≤ y, we want to split the tree into as few paths as possible. Tree DP.

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

      n cannot be 1. (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 109)

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

      n is at least 2; read problem statement more carefully.

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

      n is >= 2 from problem statement.

      I noticed that in case where x > y one should watch for single vertex with degree n-1, as it forces you to use cost x at least once. Maybe I am wrong.

      On Tree DP — sorry for silly question — is it possible to split tree in less then (number of leaves — 1) paths? Can you give an example or somewhere to look for it.

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

        It depends what do you mean that path is. For example

        6 1 2

        1 2

        2 3

        4 5

        5 6

        2 5

        has 4 leaves, but you can use 4 of its 5 paths (all except 2 5).

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

      Got my mistake.

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

    you could add to path not only diameter. Also you could add some more edges from tree.

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

I'm good at geometry:( I think Problem C can be solved by PolarAngleSort,but I failed on test4.

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

    In problem C, I find first three points that made a triangle. Then I iterate over all other point, if a point is inside the current triangle, replace any vertex of the triangle with that point; if a point is on an edge of the current triangle, replace any node of that segment with that point.

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

    No need to do polar angle sort, just sort by X (or Y). First two points will be in the answer. Last point will be the first point not on the same line as first two points.

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

my submission before 5 seconds did not go into submission queue.. T.T

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

    I pressed submit 50 seconds before the end and still failed to submit — looks like it wasn't a good idea. Anyway I don't think my submission was good, so I actually saved 50 points :)

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

      As I understand, you won't be punished for 50 points if it won't pass pretests, only if got AC. Not sure about system testing.

      Anyway, it is a usual thing — last 5 minutes of every contest is very dangerous time to submit anything :)

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

        If you are correct, then this is second place where Codeforces is factually incorrect — admins, please fix it!

        First place is Help tab in top menu — if you press it and scan through the rules you will see that Div.1 still starts from 1,700+. In both Russian and English version. I reported to Mike, but he was probably too busy.

        For submissions penalty — during the contests, this is what text on the right tab says — "you get 50 points penalty for each unsuccessful submission except if it fails on first pretest, etc." — at least in Russian version.

        Admins, please fix!!

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

          I'm not sure how it supposed to be, but just checked some older contests and in fact:

          1) No penalty for wrong submissions if you haven't got AC for this task

          2) No penalty for AC submissions that failed system testing

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

          If it's the penalty of problem AC score and not of total score, it's correct.

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

    I submitted before 10 sec the problem C

    It went in the queue but how frustrated I was when i realized I did not erase a misplaced "return 0 ;" that I used when debugging :(

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

      About same case for my Problem D where I forgot to comment out freopen -_-

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

How to find minimum area triangle in O^2?

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

I know I will sound stupid, but I couldn't solve Problem A... (I didn't even try the other problems) My final submission was: http://codeforces.com/contest/618/submission/15665677 which seems to do something different than what problem A requests. Why??? What did I get wrong?

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

    You could have just simulated the process in O(N) . (Look Here)[http://codeforces.com/contest/618/submission/15651613]

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

one silly mistake and rank moved back a 1000 places >_< .

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

Please don't do this. Either submit a bad solution early, or don't submit a solution at all. That makes us, hack hunters really thirsty...

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

Open questions:

1) is N!=NP ?

2) What is the fastest algorithm for multiplication of two n-digit numbers?

3) Can the rotation distance between two binary trees be computed in polynomial time?

4) Will a day come in future that Codeforces server problems be permanently solved?

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

Problem C — Time limit exceeded on test 84... :(

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

I got runtime error in case 87 on problem C, I have absolutely no idea how that could have happened. Here is my submission: 15659929

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

    Seems to me like you sent wrong link.

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

      Oh yeah, my bad. Thanks, I fixed it.

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

        To your quection: in first cycle mejor can be exactly 4 * 10^18. So in this case you will get uninitialized s, and I don't know maximum possible major in second cycle (maybe >= 4 * 10^8 ant in this case you will get unitialized t)

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

    No "return 0;" in main.

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

      Yeah, that is why he he/she passed previous 84 tests:D

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

      It's allowed in C/C++, compiler will treat that as return 0;. But that's behavior specific for the main function only.

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

    It's because of mejor=4e18. 4·1018 is too small "infinity" when looking for the farthest point when are up to 109 by absolute value. So, the s variables is not set after the first loop and behavior afterwards is undefined.

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

A solution to the hard case of D can be found here:

http://www.austms.org.au/Publ/Jamsb/V44P2/pdf/1761.pdf

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

Why didn't you include at least test with n = 2 and x > y in pretests for D? There are still other corner cases for hacking.

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

    I didn't include any cases where the tree is a star and x > y. For n<=3, the only possible tree is a star.

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

All problems are very excellent. Thanks to Wunder Fund Company.:)

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

chill bro, it's A and it's not easy to hack this guy. Why would someone try so hard on A?

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

Wow, so many fails on problem C.

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

RomaWhite, maybe, is the unluckiest human in the whole world now... 1 point form XBox One :(

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

    Testing is not finished yet, so he could finish on worse place.

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

      When It was 97 percent of testing I thought that nothing can be changed at the top of the table. That was my stupidity. Egor have sent solution when it was 1 hour and 59 minutes. Congratulations to him!

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

    on the other hand, Wunder Fund are lucky because that point avoided the headache to them deciding who will win the Xbox

    UPD: now both dropped one place to 3rd and 4th so no one is lucky and no one is unlucky

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

    And now he won't...(rank 4)

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

Interesting that this solution that doesn't map the indices passes the tests: http://codeforces.com/contest/618/submission/15664708.

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

    I think you're wrong. Solution requires two arrays of points — input array and sorted array. Answer building by sorted array. And indexes of input array are printed.

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

connor: blue, extremely high. His previous results aren't that great. Seems suspicious.

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

Can I see my ranking considering only div. 2 participants?

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

Hello guys,can someone please give me any hint on how could i solve problem B? Cheers

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

I didn't participate but I had this probably bad idea for C : take any point, then take its closest neighboor, and finally take the closest point that is not in line with those two points. So far I didn't see where it fails, can anyone show me where it fails? edit : it works

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

    This is correct, since this third point will be on the line that is parallel to the line that connects the first and the second point and is the closest to this line.

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

      Thanks ! It seemed too simple with all those hacks and red coders weren't so fast for such a simple algorithm. Maybe I would have failed anyways because of int overflow in vectorial product (had this idea late).

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

    As solution it seems correct. But it depends how you implement it — bruteforcing will be O(N^2) and it is TLE.

    I solved it a bit differently in O(N):

    1. Find valid triangle: take first two points and iterate for others, first one that is not on the same line = got valid triangle.

    2. Iterate over all other points. Check if point is inside triangle, if so — replace one of old 3 points with new one so we will have valid triangle again.

    UPD: In second step more precise description will be: "Check if point is inside or on the edge of triangle".

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

      This solution is wrong when between first two points exist the thrid one and all three are colinear.

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

        Nope it is not.

        Maybe I wasn't too clear with description, in second step it is more precise to say that "if point is INSIDE OR ON EDGE of triangle".

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

        All N points are never collinear . It's mentioned in the statement .

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

      I thought about O(N log N) : I sort the points by distance from the first point.

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

      I solved it a bit differently from yours in O(N):

      The first point in answer is the first point in input data. Then choose closest point to it from others. Then choose closest point to the segment of to points that we already have. Also, this third point mustn't lie on the line made from two already choosed points. Got AC, but your solution, I think, more easy to prove and understand.

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

    i did the same it was accepted , the approach is correct http://codeforces.com/contest/618/submission/15660749

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

You forget about overflow and you get Wrong answer on test 93 :/

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

round is rated or unrated ????

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

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

    A lot of test cases and big timeouts (2-8 seconds each). E.g. right now some E solution is running on test case #53 and each could be 8 seconds. And it is only one participant.

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

Int fu**ked me on test case "93" problem C

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

    Same here ! Submitted C thrice ( once after getting hacked ). All that for a WA because of overflow :(

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

And congratulations for 51st place to: FatalEagle!

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

    For the past 5 minutes I was watching aropan's submission, hoping that test 67 might be some strong TLE case.

    Nonetheless, congrats to aropan for that incredible luck in server timing :)

    Edit: Reached IGM for the first time, so this contest is still a success for me!

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

      For the past 5 minutes I was watching aropan's submission too.

      Thanks for the congratations.

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

    FatalEagle be like

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

Давненько я такую грязь не засылал

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

Somehow I thought that in problem D there is no Hamiltonian path avoiding edges of path on 4 vertices. That is the only testcase my solution fails.

This case wasn't in the system test, but sadly one other competitor in our room made the same mistake and I hacked his solution. As you probably know, successful hacking cases are added to system test.

If I didn't hack him, we would probably both passed :-(

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

    lol

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

    I thought that too. In graph 1->2->3->4 there is not Hamiltonian path if you start from vertex #1, But if you start from 2, 2->4->1->3 is possible path.

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

    I think you did the good thing in that situation. Of course in hindsight you shouldn't have hacked, but in contest you couldn't know how common that bug was (so other people would make these hacks) or that there weren't 4 node test cases. If you were at a harder problem, which few people submitted, then that's another story.

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

That's why I like TC SRM the most :( no problem for int or long long .

WA at 93th

AC

whatever my logic was right. I should be happy :)

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

    You probably should add after "I will always use scanf and printf", "I will always use at least int64 type" :)

    Really almost every contest have int32 overflow in some form. And in many tasks it is present to cut some specific fast algorithms, like counting in array where index = value.

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

      True :) Actually Div 1 & Div 2 combine contest never went good for me. Today i was hoping to break this :p Anyway it was a great contest .

      Thank you lewin :)

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

What is wrong in this approach for problem C? First i am finding two leftmost points i.e. points with minimum x co-ordinates. Then i check for all other points such that they donot from a line with these two points and r1 ^ 2 + r2 ^ 2 is minimum where r1 and r2 are distances of the point from first and second point.

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

    E.g. if you have 5 points with the same X value you just pick first two, while other three could be inside them. So they will be inside the triangle that you've found.

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

      But in that case, whichever triangle you form will have zero area. That is not valid.

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

        E.g. you have points:

        0 1
        0 3
        0 2
        1 1
        

        Your algo will pick points 1 2 and 4 as a result. And it is wrong, because point 3 is inside this triangle. Valid answer will be 1 3 4 or 2 3 4.

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

          Thanks for that case. But i am still getting wrong answer. Now i am finding two points with minimum x and if they are equal then i am finding points with minimum y.

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

            I'm not sure, but it is possible there are two triangles (p1 p2 p3) and (p1 p2 p4), where distance from p3 and p4 would be equals and p4 would be inside (p1 p2 p3). But I'm not sure.

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

              Thanks a lot for debugging! :)

              I guess the condition r1 ^ 2 + r2 ^ 2 should be minimum was wrong ( I don't know why ). I just changed it to finding third point with minimum value of x and minimum value of y and it got accepted.

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

            didnt debug your code . Just wanted to suggest that finding 2 points with minimum x coord can be done easily by sorting and picking the first two points . Refer this .

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

Can any body tell me why my approach is wrong for C

sort point by x .

for each 3 consecutive points make sure that their not in the same line ( horizontally or vertically ) if its the case print these 3 points and return .

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

    It was the right idea to solve C . May be Int flow issue was there same as me . btw its not essential that only they will only horizontally or vertically in line . point ( 0 , 0 ) , point( 1 , 1 ) and point( 2 , 2 ) can also form a line .

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

    if you only sort by x , then you could choose 1 point on a vertical line ( P ) and 3 on the next one( P1,P2,P3). In that case, you may choose P , P1 and P3 where P2 is inside of the triangle(on the border). You should sort by y too

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

    It's not enough. For example, points A(0,0), B(1,1) and C(2,2) can't form a triangle, in spite of they don't have the same x or y. You should check that the area of that triangle is 0. If it's not 0, print that 3 points.

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

    The approach is broadly correct. I just implemented it to test: 15667843. However:

    1. it's not enough to sort just by x (or y) coordinate; points that have the same x coordinate should be sorted by y coordinate (x, respectively).

    2. points can be on the same line that is neither horizontal nor vertical; this case should be recognized and skipped.

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

When the T-shirts will be announced?

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

Hello...this is my third contest on codeforces. In my first two contests I only solved one question. Today I solved two but my rating decreased! Can somebody explain this to me ? Is it because that this round is a combined round ?

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

    Rating increases if you solved better (more tasks OR equal, but faster) than the participants with the same level (or greater) as you.

    And it decreases, if you solved lesser or slower.

    So it is not based on the amount of solved tasks itself, but on the comparison on your peers.

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

    The Rating increases does not depend fully on how much problems you have solved in the round. It depends also on the time you have spend solving the problems. Try to solve problems fast.

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

good contest

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

Problems with awesome quality. Nice, lewin. And for me drawings in E were extremely helpful. Thanks for a round.

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

Hello, what can i do to make my code more efficient? thanks. http://codeforces.com/contest/618/submission/15668412 it's O(nlog) 0.5 seg on test 4

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

Finally returned my yellow, thanks for the round! And like it if your first submission for problem D was a diameter too!

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

    First idea was diameter, was about to code it, but then looked at the case with 2 large chains and realized that it's something else.

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

I got Wrong Answer on test 15 in problem C, but when I run it with the same code in my computer, I get a different output. How is it possible?? this is my submission http://codeforces.com/contest/618/submission/15662738

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    1. Precision
    2. Wrong dmax

    15672460

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

      Thank you, I will be more careful with precision and bounds. By the way, #define double long double ???????? I didn't know that it's possible to do that.

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

        C preprocessor operates with text, nothing more complicated. It doesn't know what the double is so you can replace that way anything you want.

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

In problem C, my submission gives output 1 1 2 in CF . But, in my pc it gives 1 2 3 . Why is this happening ?

http://codeforces.com/contest/618/submission/15671958

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

    Whenever there are large value such as 10 ^ 9 you should use double constant instead of default float constant. Change 1.0 to 1.0L to get accepted.

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

    Short answer: precision. Your solution with long double passed 15672148.

    Long answer: try to avoid floats as much as possible. For example in my solution 15657222 I use fact that you can compare the squares of the distances to determine which is shorter so there is no need to take root. Also I search third point by comparing areas of triangles and they are always N/2, where N is some non-negative integer, so I simply doubled them. Owing to those facts I have only integer operations, no EPS, no precision problems, also faster solution.

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

I was trying to solve question D. On codeforces it shows runtime error on test case 1 while same code gives correct output in ideone. Here is my ideone solution link. IDEONE

Here is codeforces solution link Codeforces

PLease help.

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

    This line is incorrect: height[v] = 1 + dfs(node[v][1].first);

    Arrays and vectors in C/C++ are zero-based, so if node[v] has size of one, there is a single element here of index zero, not one. That's undefined behavior and you was lucky enough to get a crash instead of spurious wrong answer. I would recommend you to adapt zero-starting arrays instead of trying to enumerate everything starting with ones.

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

For problem C , I am sorting all the points by the distance from origin and then choosing 3 points closest to origin but it seems to be giving WA 4.This idea will fail if three points are colinear but the reason for WA — 4 mentioned by CF judge is triangle is not empty.I am unable to figure out how this idea fails in situation where 3 points found are not colinear. Here is the wrong code http://codeforces.com/contest/618/submission/15677172 .Thanx in advance.

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

    This is a wrong way of comparing longs. Contract for comparison methods in Java is that they return either zero, or something positive, or either negative (depending on relation). a - b is not ok even for general integers, and here you subtract two longs, get some big result (which may not fit into int) and then truncate it with explicit typecast with data loss. Simply, overflow. You do not have control over sign. Correct way is to use Integer.compare(a, b) or Long.compare(a, b).

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

Congratulations to winners I'm so happy to them

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

DELETED

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

When will be T-shirts sent?

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

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

I have great news! WunderFund approved additional 43 t-shirts for all participants shared the same winner places! So random t-shirts will be sent to: