Автор zeliboba, 9 лет назад, По-русски

Привет, Codeforces!

4 февраля, в четверг, в 20:05 MSK состоится AIM Tech Codeforces Round.

Раунд подготовили для вас сотрудники компании AIM Tech: Kostroma, riadwaw, yarrr, ArtDitel, ValenKof, bobrdobr, agul, gchebanov и zeliboba. Раунд пройдет во время Петрозаводских сборов, спонсорами которых наша компания стала в этом году.

В каждом из дивизионов участникам будет предложено пять задач и два часа на их решение. Разбалловка будет статическая.

Мы постарались сделать задачи проще, чем в прошлый наш раунд, но не менее интересными. Окончательная разбалловка будет опубликована прямо перед раундом, но сразу сообщу, что сложности задач C,D,E первого дивизиона отличаются меньше обычного, поэтому рекомендуем сначала прочитать их все.

Благодарим Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces, координатора задач Codeforces Глеба Евстропова (GlebsHP) и Марию Белову (Delinur) за перевод условий на английский.

Наша компания занимается проп-трейдингом, ключевыми понятиями в нашей работе являются big data, low latency и high frequency. В нашей работе важно алгоритмическое мышление и умение писать эффективный C++ код, поэтому у нас работает много спортивных программистов. Чтобы придумывать hft-стратегии нужно обладать хорошей математической интуицией и умением подходить к задаче с разных сторон, поэтому их созданием в нашей компании занимаются в основном олимпиадники-математики. В свободное от работы время мы участвуем в разных соревнованиях по программированию и не только, вместе ходим в походы и путешествуем. Прочитать подробнее про нас и наши вакансии можно на сайте aimtech.com. Можно отправить нам резюме через эту форму, даже если вы не участвуете в раунде.

Всем удачи и высокого рейтинга!

P.S. Для участников петрозаводских сборов в пятницу 5 февраля в 19.30 вечера будет организован фуршет в Пауланер Бройхаус.

Разбалловка

div2: 500 — 1000 — 1500 — 2000 — 3000

div1: 500 — 1000 — 1750 — 2000 — 2250

Разбор

P.P.S. Авторское решение div2A имело погрешность 5e-7, поэтому мы решили пореджаджить эту задачу.

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

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

Будем надеятся, что либо ваш фуршет закончится после 11, либо в Пауляйнере в это время можно будет поесть обычным порядком. А то ласточка приезжает только в 22:55

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

    Я думаю, что мы будем там до закрытия, но кухня принимает заказы до 23:30, так что лучше сначала зайти к нам, а потом заселяться ;)

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

      В прошлый раз вроде успели даже после заселения

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

I hope that the all problems will be more interesting;)

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

GL & HF

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

В последнее время всё больше раундов проходят под знамёнами IT-компаний, что не может не радовать, учитывая уровень и качество задач этих самых раундов

Всем удачи! :)

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

А есть какая-то связь между Aimtech и Wunderfund?

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

    Это разные компании, если ты об этом спросил.

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

      Спросил, потому что вы раньше назывались Aimfund, а по описанию обе компании очень похожими вещами занимаются.

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

Why does it say "February 22" when it actually is on February 4th ?

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

It would be great to make one division contest like previous round :) I think that is more interesting for everybody.

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

А можно вместо прикрепить файл, сделать ссылка на резюме (опционально)? Это намного удобнее на самом деле. О вы проводите hftbattle, случайно заметил пост. Для многих будет интересно, думаю стоит закрепить в посте.

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

    Про hftbattle будет отдельный пост. Пока можно оставить свой email через форму на сайте

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

    Про него будет отдельный пост, когда назначим официальную дату начала.

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

It says the scoring system will be static, does this mean that the points for submissions of a problem won't decrease as time goes by?

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

    As far as I know, No it means that the scores of problems won't be changed during the contest ,this means if problem C is for 1500 points before the contest it can't be changed to 1250 or 1750 points during the contest even if number of submissions for that problem increase or are relatively less.

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

No T-Shirts ?? Your past contest had 200 T-Shirts which was really awesome.

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

    Next time we are going send T-shirts again =) This round is created mostly for participants of Petrozavodsk Training Camp.

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

In fact I havn't received the T-shirts prized for AIM-FUND ROUND yet! :D

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  1. difference in complexity between problems C, D and E may be less than usual in Div2
  2. difference in complexity between problems C, D and E may be less than usual in Div1
  3. C div2 = A div1, D div2 = B div1, E div2 = C div1
  4. difference in complexity between problems A, B, C, D and E may be less than usual in Div1
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

сложности задач C,D,E отличаются меньше обычного Речь идет о первом дивизионе?

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

what is high frequency rating?

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

As far as I remember, your previous contest was very good.I hope this one will be better.

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

    I think you mean very tough.

    In div 2 the standing was very unusual, from the 27th to the 1500th all of them solve A and B only !!!

    very easy A,B and very hard C,D,E. I think the difference in difficulty should be normally increasing not exponentially.

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

Здравствуйте, подскажите пожалуйста, какой дивизион для более слабых? Второй, как я понял? В первый не пустило.

И всем удачи :-)

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

Be rated or not ?

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

Will it be a rated contest like division 2 contests ?

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

Will the score obtained will depend on the time of submission just like any other round?

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

Если у двух участников одинаковое количество баллов, то они занимают одно и то же место?

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

when I try to submit a code it says i'm not registered !!!

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

    you must be registered before start of the contest. usually register is open 24 hours before the contest begin.

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

      he/she registered in two contest before how could he/she doesn't know about this

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

Что за фигня — я задачу B даже не сдавал, а пришло сообщение что мое решение B взломали?!

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

Сложный контест для div1

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

And here is when I hack Um_nik ! :)

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

Невозможно сломать вообще, сайт тупо по 5 минут открывает чужое решение( Стратегия со взломами вообще невозможна при такой обстановке, нужно как-то решать этот вопрос.

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

How to solve problem D div 2 ?

Nice problemset !

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

How to solve Div2C?

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

    First observation: each 'b' symbol will be connected with every other symbol in the string.

    So, find all symbols connected to all others and add them to first set ('b').

    First symbol that is not 'b' will be 'a'. Add this symbol and all symbols connected to him to a second set ('a').

    All other symbols not in first two sets will be in third set ('c').

    Now validate sets 'a' and 'c' so each symbol in the set connected to each other (set 'b' is valid by its definition). If not — answer 'No', if yes — print the answer.

    Complexity is O(N^2).

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

      Now validate sets 'a' and 'c' so each symbol in the set connected to each other (set 'b' is valid by its definition). If not — answer 'No', if yes — print the answer.

      Oh, and now I realized my solution is wrong, because it's not enough to check this. You also must validate that any 'a' and 'c' are not connected.

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

      My alternative solution:

      1. Obtain reverse graph. (not connected graph)
      2. Try to color it in with 2 colors when no edge is connecting 2 nodes with the same color
      3. If failed -> No solution. If colored, pick any color as 'a', other colors as 'c'. All non-colored nodes as b.

      EDIT: probably bad idea, got Wrong Answer on test 26 because I forgot to check that any two different colors are not connected

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

        Additionally, in step 2. you need to ignore nodes without edges, so they can be colored as 'b' in step 3.

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

          Well, these would be ignored anyways as all 'b' nodes would not exist in the reversed graph (because 'b' nodes are connected to every other node).

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

            It depends on your method for generating the reverse graph. If you don't remove the nodes that are not connected to any other node, then there is a risk of coloring them as 'a' or 'c' in step 2.

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

        I got AC with this kind of solution, I checked the string 1000 times to try to find new symbols, then filled the rest with 'b' and checked the answer: 15798901

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

      I had brute force solution, lol :))) Of course, it is named as "backtracking", but, anyway, it was too stupid. TL on test 15

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

I knew How to solve E....

If I had just 5 minutes more...

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

Can anyone give me an idea for B div.1 ? :'(

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

    Factor a[0]-1,a[0],a[0]+1, a[N-1]-1,a[N-1],a[N-1]+1. Then for each prime from that factors, do:

    • in first pass count best solutions for left prefixes
    • in the second (reversed) pass get best solutions for suffixes and join with the best solutions for prefixes.

    Solution for prefix is basically a run of modifications such that gcd(run) = p and then run of deletions. Deletions from prefix solution join with deletions from suffix solution.

    PS: there may be a mistake in idea, I didn't get AC.

    PS: it's actually easier to make one pass of DP for each prime

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

    My idea was that either the left element or the right one will be present in the final array, so try for every prime factor of those numbers (plus 1 and minus 1 too) the minimum cost to build an array with all numbers multiple of that prime.

    I did it with prefix/suffix DP and some operations of addition in between. I don't know if my solution is correct though.

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

    Note that you only need to consider prime divisors of a1, (a1 - 1), (a1 + 1), an, (an - 1), (an + 1) as possible GCDs. Trying all the possibilities should be easy enough.

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

Anybody got stuck too at Div1B — 9th pretest?

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

    Stupid mistake, when factoring by trial division forgot to check if the rest of the number is > 1 and then it should be added to prime list too.

    9th test is the first when a large prime appears.

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

Solutions for Div1 D? Being solved way more than Div1 C for some reason, is there some easy solution?

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

    I am not sure why it should work, but here is my approach, which passed pretests. First of all guess each friend once (order doesn't matter now). After that I always greedily guess the friend which gives me the biggest profit as a matter of probability that you win in that turn. I simply do that with a heap and while I have enough time.

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

      Let pi denote the probability that we've already caught the i-th person. The probability of winning right now is p1·p2·...·pn. For each i we can consider ri — the probability that we've already caught this person or we will catch him/her in this turn (assuming that we're going to try to catch him/her now). The probability of winning a will change to where c denotes a person chosen in this turn.

      Why can we greedily choose the biggest ? I won't show the formal proof but the following two arguments are enough:

      • the probability of winning in some turn is equal to the product of chosen values
      • For fixed i the value of is decreasing as we choose this person again and again.
»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Today Codeforces was extremely slow :( I was hacked and didn't refresh manually. It took 25 minutes for Codeforces to warn me :( I went to other heavy websites but my connection was totally okay :(

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

    I had the same problem: my A solution got hacked 9 min before contest's end, but I got the notification only when it was over :( So I spent 9 last minutes on D rather than finding bugs in A. Seems like manual page refresh is a must :(

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

На чем ломают Сdiv2?

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

    Я на этом тесте

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

    Ответ No

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

Div2 B hack:

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

в Б катит динамика dp[i][j][curGcd] = мин стоимость если мы рассмотрели первые I чисел, их НОД был равен curGcd, и j ==0,1,2, в зависимости от того, мы не удаляли отрезок, щас удаляем, или уже закончили удлаять. Ну и там памяти не хватает поэтому по слоям надо писать?

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

    gcd можно рассматривать только из простых чисел взятых из факторизаций a[0]-1,a[0],a[0]+1, a[N-1]-1,a[N-1],a[N-1]+1.

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

what is test 6 of div1 C?

I think this the worst decision I make in my life choosing to solve C first!!

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

Wow. You really can't make easy contests.

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

Скажите пожалуйста, как во втором примере в B div 1 получился ответ 7?

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

Another contest by unusual scores and difficulty of problems... at Div. 2 Problems A,B was very very easy and so Problem C a little ... for this a lot of people solved problem A,B,C and the force(competition :D ) of contest was for a few of Time!! All are the same !! :|

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

    Well I think ABC tasks was very good for div2: difficulty is raised from A to B and from B to C significantly (there were like 3000+, 2000+ and 1000+ solved participants).

    But D and E was too hard (only 15 and 1 solved). Imo, D should be actual E and there needs to be a simplier task between C and D to be perfect problemset for Div2 :)

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

      Now I see Problem C has just about 500 AC after system tests... This mean that Problem C was not normal so... Now All the same at solve Problem A && B :D !!

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

      actually A-> 3200 B->2500 C-> 500 . Not a good distribution.

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

In E, my solution was binary searching the answer . To check if that answer is possible or not, I found a upper bound of y for every y[i] , i<=N . Then Finding the corresponding points on x-axis , I checked if that answer is possible or not. The, I rotated the axes , and checked for the answer again . The minimum of those answers are the desired answer .

Is the idea wrong ?

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

My hack case for C :

4 3

1 4

2 3

3 4

I even hacked my own solution with it (i.e. discovered it after locking -_- )__

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

По-моему получилось не сильно проще чем в прошлый раз :-)

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

Another contest with weak pretests.

GL hackers!

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

wow! so many failed C(div2). and the whole time i was trying to hack with B -_-

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

My hack case for A(div 1) C(div 2) :

5 9

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

bbbac or bbbca

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

I thought the string in problem A can have any character from a to z. So I solved the harder version and failed system test. After contest I changed upper bound of character from z to c and got AC :(

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

    I think I also had it bad. Forgot to print "Yes" in the special case ( n = 2 and m = 0 ) and got WA78. But I fixed it after the contest and it got accepted. I kind of hate myself right now.

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

      This kind of mistake may sometimes be avoided by having only a single line in which you output Yes and No. If you don't have any "return" statements above the line has to be executed always.

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

        Yes, you're right. It's entirely my fault that I implemented the code like this with multiple Yes or No lines, and avoiding it is actually very easy, but I think I'm way too lazy for that kind of "refactoring". I mean, it's the "accept rush". But just seeing your solution fail simply because you didn't format the output properly is a real pain in the neck :/

        Also, the "Yes" bit is really redundant. It should've been the string / No from the start.

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

          I understand the "accept rush":) And if the code is already written then there is obviously no time for refactoring. But if you start writing the solution by introducing the bool variable and then serializing it to "Yes/No" only once at the end, it somehow makes it more difficult to forget to set it properly. And there is no chance of forgetting about the output, because it's always there at the end.

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

lol, in A we should use 'a'-'c' only... I should read statements sometimes.

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

Uhh... thank you! :D

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

Получил по C wa17 на претестах. Думал, что решение какая-то шара (а оказывается похоже на авторское) и кинул еще две посылки "на авось". Первая прошла, а вторая получила wa1 по B (не туда отправил). Порадовался, что первая зашла и не стал посылать вторую (разница в бинарном поиске >= и >). В итоге wa40 на сис.тестах, а вторая верная. Обидно :( А можно было в одном решении записать сразу оба варианта и выбрать оптимальный... Не стать мне красным :D

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

Hm, ok, that was fast!

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

Woww. Rating lost after one contest = Rating gained after one contest! :P

Such stability. Much wow. :P

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

Aw...Fast system testing and fast rating changing .. good :)

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

Can someone tell me how to deal with precision problems at div1E? I was using FFT(but had same big values due to modular inverse) and modulo being very big, I was getting values with a big error.

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

    There are two possible solutions: the first is using Chinese Theorem (calculating the answers modulo some numbers about 106, then obtaining the answer in long arithmetics), or using the next trick: take and represent each coefficient as ai = bi·M + ci, where ci < M and bi < M. Then the multiplication of polynomials with coefficients ai is reduced to 3 or 4 multiplications of the polynomials with coefficients bi and ci. There coefficients are less than M, so the usual FFT in doubles is OK for them. For instanse, check Endagorion's solution.

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

      I was thinking about Chinese reminder theorem too but it seemed too slow and hard to code. I'll try to implement the trick tommorow(hope it'll work). Thanks

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

Hacked B(in Div.2) three times. Problem C could have been just a little more easier. PS: Thumbs up for the fast system testing and ratings.

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

Well, screwed up somewhere in A and couldn't find the bug. Would have to start over so skipped. Messed up my approach to B.

Looked like I might score zero for the round.

I checked the C, D, and E problems just in case one of them was easy. Bingo! Problem D was a very easy one hidden among the toughies.

So I end with about 1300 points for solving one very easy problem and screwing up another very easy and an easy. I really thought it was going to be a disaster of a contest after the first hour with nothing to show at all. Instead I ended up in the top 15%.

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

    Either use cin or cast to double when working with long double. It's known problem on Codeforces.

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

During the contest, I received an announcement saying that my B was hacked, but it wasn't.

What could it be?

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

Я синий! Эксперт! Еще месяц назад я был безнадежным новичком, а сейчас поднялся на 3 уровня выше) Когда была возможность временно сменить цвет хэндла, я выбрал специалиста — это был предел моих мечтаний на ближайшее время. Но сейчас я превзошел все свои ожидания) Невероятно всем благодарен. Удивительно, как многое для меня стало значить какое-то число на каком-то сайте) З.Ы. У меня достаточно интересный график.

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

I liked the contest, congratulations.

Also I want to say thanks to Codeforces team, and community, for making this a nice place to study and improve. This was my 50th contest and I got (+51) in my contest rating :D

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

So I did the Div2A in the practice room and got WA when just using "cout" for the answer. Got AC with printf(".6lf").

I read the statement carefully and it says if "absolute or relative" error does not exceed 10^-6. So why is the printf needed instead of just cout? I would think the extra digits after the 6th digit would be less than 10^-6 and thus OK within absolute error tolerance.

Should it be both absolute AND relative error < 10^-6? Or is the example about checker saying that for results < 1 it will use relative error?

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

    I think you should use statement like: cout << fixed << setprecision(10) << ans << endl;

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

      Well I know how to print the answer to get accepted, but I am asking WHY it has to be printed to exactly 6 decimal places, because the statement says "relative or absolute" are both OK.

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

        If you don't output at least 6 digits after decimal then your output can fail both the conditions (i.e. relative and absolute both). Just like if you see your submission with cout, correct output is 2.6666670 and your output is 2.666670. The relative and absolute both the errors are >= 10^-6.

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

The biggest mistake to make during rounds is to not read the problem carefully. Could not solve B because I missed I can make those operations only once. Any ideas about the solution if I could use them infinitely?

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

    Haha glad i wasn't the only one. The only solution i was able to come up with is n*sqrt(max(a_i)): go over all the possible divisors up to sqrt(max(a_i)) and for each number a_i, calculate if it's best to delete this number (we can do deletions infinitely so we don't need to care about contiguous segments) or to change it to be divisible by the potential divisor. At 30 billion such operations this is too slow for the given time limit though. We can improve this by taking only into account prime divisors, which brings it down to at most 3 billion operations, which is also too slow, but getting close at least.

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

I think it‘s a bit difficult for me,but anyway,I think it's a great round.

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

wat

how is this possible

i don't even

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

Any ideas about Div2 E? I passed 8 pretests and then got stuck at 9. I don't know if my idea is totally correct :/ or there could be some mistake with the implementation :( but as it is so hard, I think an amateur like me obviously can't solve it. So, I guess I passed the 8 pretests submitting totally wrong code :/ anyways, ideas please? I have mu exams going on so I don't wanna check the tests which failed me right now. Will do it 2 days later. Meanwhile, please help :)

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

Why have ratings been reset ?

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

I think div1 problem C has a little bit weak testcases.

My 15925572 code got accepted even though I think it has some mistakes.

Maybe some hero could add more testcases or correct me.