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

Всего через 6 с половиной часов начнётся Раунд 2 чемпионата по программированию VK Cup 2016! Если вы не зарегистрировались на раунд — не беда! Есть дополнительная регистрация!

В этом раунде могут принять участие все те команды, которые отобрались в Раунде 1 или в Уайлд-кард раунде 1. Участников ждет соревнование по правилам классических раундов Codeforces. Одновременно с основным раундом будет проведена интернет-трансляция, которая представляет из себя обычный рейтинговый div1/div2-раунд по правилам Codeforces. В трансляции может участвовать любой участник, не зарегистрированный на основной раунд в составе отобравшейся команды.

Раунд для вас подготовили AlexFetisov и winger. Это первый для нас раунд на Codeforces в качестве авторов. Огромное спасибо Глебу Евстропову (GlebsHP) за долгое сотруднечество и помощь в приготовлении раунда. Глеб делает колоссальную работу, и я хотел бы это отметить еще один раз! Также большое спасибо Kamil Debowski (Errichto), Mateusz Radecki (Radewoosh), Боре Минаеву (qwerty787788), Паше Кунявскому (PavelKunyavskiy) за прорешивание задач и дельные советы. Огромное спасибо Мише Мирзаянову (MikeMirzayanov) за все, что он сделал для всех нас!

Напомним, что в Раунд 3 пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 100-м месте. Также обращаем ваше внимание, что все команды, проходящие в Раунд 3, получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

Желаем удачи и интересной борьбы!

Обновление

Раунд завершен. Надеюсь, задачи вам понравились! Поздравляем победителей!

Официальный VK Round 2:

  1. Who`s On First Base!: -XraY-, ershov.stanislav
  2. Beer and lemon tea: sankear, Zlobober
  3. MYCOPOBO3: V--o_o--V, LHiC
  4. Never Lucky: subscriber, tourist
  5. 33% less bad jokes: ifsmirnov, Arterm

Результаты Div1:

  1. anta
  2. jqdai0815
  3. Petr
  4. dotorya
  5. ikatanic

Результаты Div2:

  1. alexrcoleman
  2. nherceg
  3. santjuan
  4. mkisic
  5. unused

Разбор

http://codeforces.com/blog/entry/44538

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

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

Auto comment: topic has been translated by AlexFetisov (original revision, translated revision, compare)

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

Stay away tweety :p .

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

What the difference between the VK round 2 and the codeforces round. Like for example if a div 2 coder participated in the codeforces round and solved few problems can he participate in VK round 3 or do I have to participate in VK round 2 exclusively. And can't I just participate in VK round 2 AND codeforces round so if I solve a problem in one of them I solve 2 so my rating will go sky high. :-)

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

"Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well"

Is there a mistake here?

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

    "All teams advanced to Round 3 and TOP-50 participants of online-mirror of Round 3 will get t-shirts."

    (Translation from Russian)

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

      Does it make sense? Shouldn't it be TOP-50 from today's contest? Top participants from VK round 2 are awarded with shirts, so why unofficial round 3? Am I right?

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

      Does that mean I won my first shirt ever??

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

is Div 2 for Russian speakers only ?

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

.

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

First: I have opened the announcement. Second: Ctrl+F Rated, Ok, then let's go on.

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

Wtf?

What is it???

A rated CF contest???

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

how can i delete my comment?

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

No skeleton images saying waiting .... till now .
Wierd!

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

rated round??? is that an extinct dinosaur ???

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

что-то никто не спрашивает про количество задач и разбаловку:)

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

Если вы не зарегестрировались

за долгое сотруднечество и помощь в приготовлении раунда

:)

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

The number of downvoted comments is too high!

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

The first rated round in forever and I can't compete! This sucks lol. The wait for Friday begins.

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

Scoring — standard or dynamic?

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

    How to solve it.

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

      You can sum all the rotations and remember that value. And for swaps, only parity of the current rotation sum matters. When you do two swaps with the same parity, they cancel each other. So you simply need to count the final number t of non cancelled swaps, and the parity of the first swap in this sequences.

      Each number goes to t positions left or right, depending on the first swap parity and the parity of the number. And then you rotate the whole array by the sum of all rotations.

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

        Solved it in 5 minutes, spent the rest of the contest debugging. Fix a test another one fails, fix the other the first one fails. I wanna kill myself >_<

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

          very well , do it.

          maybe we will get more rated contests :v

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

          Was similar for me. I had the solution which passed all samples and all my tests. But got 7 WAs. And 3 minutes before the end I realized that parity of the first swap matters, and managed to submit it.

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

      just store number of moves for odd positioned boy and even positioned boy and finaly calculate the position of all I don't know its right or not but it has passed pretest :)

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

Was it possible to avoid TLE on problem D with a O(n+q) solution ?

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

Очень некрасиво давать задачи, где решения без printf/scanf получают TL. Дизреспект.

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

    У меня решение работало за ~1900. Перезаслал на всякий случай :(

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

    Подтверждаю.

    В задачах C и D слишком большой ввод-вывод

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

    Плюсую! 31 контест из-за этого слил(

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

    зажрались вы со своими cin/cout'ами

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

      те, кто на Java и Python пишут, тоже зажрались?

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

        Где я упомянул про эти языки?

        На самом деле, к ситуации с java уже все привыкли, а вот к cin/cout ещё нет.

        И ещё, одно дело жаловаться, что решение не прошло, а другое — обзывать из-за этого авторов. Вот я и написал, что настольно зажрались, что грань не видна.

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

          "обзывать из-за этого авторов" -- Чего? Где вы видите обзывательства? Мне ваши замечания про настольное зажирательство что-то совсем непонятны стали.

          Я всего-то написал, что некрасиво давать задачи с такими ограничениями, где меряется не эффективность алгоритма, а скорость считывания данных. Очевидно, что для тех, кто пишет на Java и Python это крайне существенно.

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

            А ещё ты написал "дизреспект". Раз не понимаешь — то у нас разные взгляды на мир, не иначе. Я когда получаю такой TLE, виню в первую очередь разработчиков языка/компилятора, НО НИКАК НЕ АВТОРОВ ЗАДАЧИ. Сейчас, для меня, это так же смешно, как "у меня в решении вместо int[] написан map<int,int>, я получил TL, плохая задача, много инпута, дизреспект". Несколько лет назад такая ситуация была с векторами против массивов — сейчас всё ок.

            Вообще не очевидно. Обычная читалка для java, которая есть у всех, кто выбрал этот язык как основной, быстрее cin'a — значит у джавистов проблем с этим нет.

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

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

              Успокаиваю, дизреспект -- это не обзывательство=)

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

How to solve Div2E?

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

    Hash table mapping an integer to a binary search tree of integers.

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

    Hi, My solution was maintain a Binary index tree with unordered_map<int,int> in each node, which is o(1) , then just do classical update, query on it.

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

    I used one Segment Tree for each unique value. Just store  ± 1 for each insertion/deletion and perform sum queries.

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

    I used STL map which maps each integer to a set of time.The solution passed pretest but it got TLE in Test case 11.

    I think that this solution take O(n*(log(n)^2)) Can you please tell me time complexity of the solution that uses segment tree or fenwik tree?

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

      Mine is O(nlog(n)) using Fenwick Tree

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

        Ok, Thank you. I tried another solution where I stored pairs of integers in c++ STL sets and this solution is O(nlog(n)) still it is giving time limit exceeded. Can anyone explain why the solution is slower than than other O(nlog(n)) solutions?

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

          Your submission is actually N^2; std::distance used on set iterators takes time linear in the distance between the two iterators.

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

      My solution with Segment Trees: 17494007

      This is O(NlogN)

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

I have a doubt : Sometimes like today's D scanf/printf seems to perform exceptionally well over cin/cout. Though I was using ~~~~~ ios::sync_with_stdio(0); ~~~~~

with no endl i.e. flushing of output yet my program ran in about 1.9 seconds changing cin/cout to scanf/printf reduced time by 3.

What is the reason behind it? I lost more than 150 points due to re-submissions

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

I realy don't understand why linear solution for D (O(n + q)) gets TLE...

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

    You need very optimized I/O... this particular problem pushed the limits of what can be done in 2 seconds in that regard.

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

      I always use C#. And never got this problem before. Something went wrong today...Of course i will investigate the problem after systests. But I think time limit should be such that the solution has passed not only on C++...

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

        I passed it with Java but needed to do several things I wasn't used to with the I/O (namely, use a BufferedReader directly instead of a Scanner, and use a BufferedWriter rather than println()ing a string made with a StringBuilder).

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

    got 4 TLE on pretest 11, even by using ios::sync_with_stdio(0) on a O(n+q) solution. But as anh1l1ator told that scanf/printf were running on time, I think it was more of language based question.

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

Am I the only one who consider that precision problems in div1C were more than annoying? I still don't consider I've made any mistake and I don't know why sometimes I get WA on pretest 8 sometimes on 9...The intended solution was with product and sum of the partial sums?

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

    Div. 1 D maybe?

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

    Its very weird. My solution with long double didn't pass pretests but when I changed it to double it did. B/w I also did the same thing.

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

      ... Nice avatar :)

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

      My solution uses long doubles, fails pretests under G++, passes pretests under MS VC++ (when all else fails: change compiler :) ). Let's see after systests, though...

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

        Btw, MSVC doesn't have long double type, it's the same as double on it.

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

    I also got a few WA on pretest 8. It seems it was because I was taking the square root of a negative number when it should have been 0.

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

I tried to hack a solution with O(n) on problem A div2 but it was unsuccessful (n=10^9) :(

why?!

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

How to solve problem 4 Div 2. i was encountering the problem when x is odd.

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

Свапнуть бы D и E.

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

I think ABCD should be circular-shifted.

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

In problem B div2, little artem and grasshopper,

second sample test 3 >>< 2 1 1 area starts from 1 and ends at 3.

start from cell 1, jump 2 steps right, reach cell 3. direction is again right, jump 1 step ahead reach cell 4 and get out of the area. but the note in the problem says, Second sample grasshopper path is 1 — 3 — 2 — 3 — 2 — 3 and so on. can someone explain why?

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

    Because each cell had a direction and length associated with it... this was not a sequential list of commands but rather the grasshopper sees a sign on the cell giving the directions... the problem asked whether the grasshopper would ever step out of bounds or whether it would keep hopping in an infinite cycle.

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

      In the example given, the grasshopper sees a sign on the first cell saying to go right 2. Then it sees a sign on the third cell saying go left one. The dutiful grasshopper then sees a sign on the second cell saying go right one. These last two loop forever, and hence the solution is infinite.

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

    No you should move in the direction of the '<' in cell 3 you will back 1 cell so you will be in cell 2

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

Solution to problem E: #66TUPO

I mean you really think it is a bit hard? Or I should expect some unexpected verdict?

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

    Nice! I mapped each x to a segment tree :D

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

    I didn't write the round, but it's the first thing came into my mind. Very straightforward. Even without this cheat, coordinate compression + fenwick trees don't make it less straightforward.

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

    This problem is very hard when you are shocked by unknown WA of C. (and this problem makes one angry, when you realize some crappy precision error was the one who blewed up such easy problems)

    Actually, I searched for your policy-based data structure article in contest — because n <= 1000000 and segtree solution will get MLE. (I calculated 240MB with dirty compression) sadly OSX clang can't compile gnu__pbds, so I used ideone to debug — it was painful.

    Soon it turned out that these efforts were useless because 1. n <= 100000 2. I read statements wrong.

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

      I can't compile that either, but what I do is use a set and once I'm sure it works I just change the code to use the policy based ds, which should be around 2-3 lines, go into custom test and check if my code still works, worked fine for me during contest :)

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

Too bad there wasn't a lot of hacking happening this round — strong pretests I suppose

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

На не-плюсах в C и D ( O(N) ) вообще реально получить AC?

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

Edit : Div2 A

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

Div1 C:

Also, probabilities should be non-negative and their sums should differ from 1 by no more than 10 - 6

I wonder, how many solutions will fail because of this case? Mine certainly will :/ EDIT: Actually, it seems like I passed.

https://www.dropbox.com/s/08m764rlxuvnd6q/hack.txt?dl=0

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

    I will get WA too. I tested it on your hack and my program output all nan. It was meant to be purely a math problem, not a programming problem -_- EDIT: I somehow passed systests...

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

    Is there anything specific in this case? My solution works fine with it.

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

      I think people who use sqrt function in their solution will see something like 1.00007 and 0.999934 when they add up the sum of their output, which will be > 1e-6 error.

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

    I can see that you did not make any hack with this case.. Thank you, I can still hope to pass systest! :)

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

    Is that a good probability? They are produced by my solution that passed pretests :P

    a[i]=15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000, b[i]=-15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000

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

    What is the correct answer to this test? My solution said that there is no such one, because of negative discriminant(it is not precision issue).

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

      According to statement,

      The answer will be considered correct if each value of max(a, b) and min(a, b) probability distribution values does not differ by more than 10 - 6 from ones given in input.

      When each die has equal probability for each number that condition is satisfied. Specifically, 12500-sided dice with each number occurring with probability 8 × 10 - 5.

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

        Yes, but that doesn't say anything about validity of the input. Values from the input should represent exact probabilities of min(a, b) and max(a, b). So I assume probabilities from your input are rounded probabilities for the dice you described.

        Problem would be way harder if you just had to find probability distributions such that min(a, b) and max(a, b) are within 10^-6 from ones given in the input.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        import sys
        sys.stdout = open("input.txt", "w")
        a = []
        
        n = 12500
        for i in xrange(n):
            a.append("%.20f" % (((i + 1) ** 2 - i ** 2) / 1.0 / n / n))
        print n
        print " ".join(a)
        print " ".join(reversed(a))
        

        This generator produces right probabilities. My solution works ok on such test.

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

Announcement that n is up to 1e6 not 1e5 in D after 1h and 20 min passed, really --__--???

EDIT: Ofc, I meant the other way around xD

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

О чём авторы думали на счёт задачи A,D ну и E,в плане большого ввода. Из-за этой проблемы я сегодня стану не серо-зелёным,а светло-зелёным. Прошу переделать и всем у кого из-за этой ошибки выводился вердикт "Превышенно ограничение времени на претесте 8",на вердикт "Претесты пройдены". Спасибо за внимание.

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

    Предлагаю вам изучить вопрос ускоренного ввода на языке Java( к примеру открыть решения топкодеров пишущих на Java, к примеру:Petr, Egor). И да, вердикт осуществляется тестирующей системой, и менять его никто не будет (:

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

I don't know why i read rotation being done as right rotation instead of left rotation initially in Div 2 C.

How to solve Div 2 D?

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

    The relative positions of boys at odd position will remain same and boys at even position will remain same. So count shifts of odd places and even places individually. After counting, just check from which position you have to start.

    Code

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

Why did this solution of mine get TLE on pretest #9 on problem div1C? (I can virtually see no way it will do worse than O(n))

http://codeforces.com/contest/668/submission/17498093

Or pastebin: http://pastebin.com/0hCpNWx6

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

Can not wait for system testing!

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

What was the pretest 4 Of Little Artem And Dance ?

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

    I don't know what exactly was the test case, but my solution which failed on test case 4 gives wrong answer on this test.

    6 2
    2
    2
    

    The answer should be 1 2 3 4 5 6

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

I got TLE on pretest 3(problem F). I tried to optimize my code in ~20 min, finally found(after contest) my code failed on testcase n=1,k=1. T_T

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

Can anyone explain why this solution gets WA3 and this solution passes pretests?

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

Can someone explain why my solution with scanf/printf gets WA on pretest 6 and the exact same solution with cin/cout passes the pretests?

http://paste.ubuntu.com/16038368/

http://paste.ubuntu.com/16038378/

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

как решать Д?

я в цикле от 1 до н составлял два уравнения: для максимума и минимума, от туда получал квадратное уравнение и главный вопрос как выбрать знак при дискременанте?

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

    У меня прошло претесты, когда я всегда выбирал знак одинаково. Почему, не знаю.

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

      Утверждается, что если нужно выбрать порядок в парах pi, qi так, чтобы pi ≤ pi + 1, qi ≤ qi + 1, то можно просто брать в качестве pi меньшее, а в качестве qi большее — если решение вообще есть, то нет никакого смысла брать разный порядок в соседних парах — если минимум одной пары не меньше максимума другой, то первую пару можно располагать как угодно.

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

      я пробовал всегда плюс — не проходит ВА 3

      добавил проверку, если меньше нуля или больше единицы — меняю знак — не прошло ВА 3

      идти с конца — не прошло ВА 8

      идти с конца проверить решение -если не проходит — идти с начала — ТЛ 9

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

Can anyone tell why did I get MLE verdict on my solution of Div2B 17492812 ?

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

what was the pretest 6 of div2 C

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

Could anyone solve F with matrix-tree theorem? It seems possible but when unfortunately diagonal cell becomes 0 modulo 10^9+7 I cannot continue anymore...

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

    I think the solution is based on tree decomposition. The tree width of this graph is very small.

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

      What makes you think the treewidth is small? I can't really construct a good example (always hard with treewidth) but it seems to me that you could make some very unfriendly graphs.

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

        Because it's k.

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

          The treewidth is k? How would you construct the decomposition? I'm guessing every time you add some vertex you want to put it in a bag with its k neighbours, but how would you build the tree?

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

            Think of it as following:

            • for k = 1 you will always have a tree
            • for k = 2 you will always have a planar graph whose dual is tree (the graph where triangles are vertices and edge means that two triangles share a side)
            • for k = 3 you will always have a 3-d structure constructed of several tetrahedrons sharing their faces. Its dual (the graph on tetrahedrons where edges denote that tetrahedrons share a face) is also a tree
            • similarly, for k = 4, 5 you will get a tree on k-dimensional simplexes where two simplexes are connected if they share a (k - 1)-dimensional face
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

              Ah, I get it now, thanks :) Then the DP-state for a bag {v1, v2, ..., vk + 1} in the tree would probably be something along the lines of: for each partition of the bag into non-empty subsets: in how many ways can we create a spanning forest covering all vertices in the subtree rooted at the bag, according to the partition we are considering (that is, two vertices are in the same set in the partition iff they are covered by the same spanning tree). Does that make sense?

              EDIT: Nevermind, you overestimate the answer a lot this way, for some edge {u, v}, u and v may be in a lot of different bags together, and this way you're counting adding this edge (between two spanning trees) in a lot of different bags. You probably have to somehow single out the one vertex that is added each step.. I'll think about this some more :)

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

                Maybe solution can be obtained on the following way. DP over the tree decomposition. State is a bag + some tree that spans vertices from the bag. And in transitions one should preserve edges which are already added in the parent bag. Number of states would be N(k + 1)k - 1 ≈ 1.2·107 and one should be careful with transitions (perhaps some precomputing will help). Does it make sense?

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

Gah... cin and cout in Div 2 D

Well I guess lesson learned: Be wary if they put such an easy problem as a Div 2 D. It literally took me 3 minutes to think of. This means that there's a trap.

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

It's jqdai0815 to start system testing!

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

Please start system testing, I wanna go to bed :-(

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

Требую повышения квоты за конченные косяки в условиях, которые изрядно подпортили положение нашей команды. (Задача E и C)

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

    И провести потом раунд 2,5.

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

    В задаче Е все было норм. Нормальное решение и для 10^6 тоже будет работать.

    Разве что для тех, кто пишет на Java немного неудобно было.

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

      Да, но мое решение которое я придумал сначала, было за n log^2 n, и соответственно не проходило. Я думаю на соревнованиях высокого уровня, такие косяки просто недопустимы.

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

    Все были в одинаковых условиях!

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

      Когда я начал ее решать на 25 минуте, а изменения пришли только в 1:30. Думаешь это правильно и все в равных условиях, если кто то дошел до нее только в 1:30? Время было потрачено зря.

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

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

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

Waiting for sys testing is worse than waiting for game of thrones season 6 :/

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

Waiting for sys testing is worse than waiting for game of thrones season 6 :(

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

From now on, I will try not to trust problem setters' problem difficulty estimations.

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

Wrote a wrong and unnecessary special case. FeelsBadMan

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

 really..

when you find out that you mistyped m to n in problem A after the contest had finished.... Nezzar

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

Ребята, нажмите кнопку "НАЧАТЬ СИСТЕМНОЕ ТЕСТИРОВАНИЕ", плез. Неужели только один Мирзаянов может на нее нажать?

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

Problem B write too difficult to know :( :( At least for me... And I waste so many time to understand... Down to 1k5 again :(( :((

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

Could anyone find the contest on contests page? Has it gone???

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

Здравствуйте Мы писали контест VK Cup 2016 — Раунд 2 и у нас появилась чужая посылка . Можно ли ее убрать?вот эта посылка

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

waiting for t-shirt...

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

any hacks on Div2 B?

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

Someone please tell me... is System Test starting or should I go to sleep? :(

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

1:38 AM in Bangladesh. Still waiting! Hope

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

In Div2D=Div1B it is algoritmically easy to find O(n) solution, but what the hell the bounds of input are of order 10^6?? Very intelligent method to make the problem more difficult:( Is it really interesting to play a game "Who didn't forget about scanf/printf?"?

(I have 1964ms on pretests using cin-cout with standard accelerators and I noticed that it is so close to TL only after the end of the contest.)

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

4:46 AM here, wating for system test.

By the way, my mid-term exam starts at 1:00 PM..... (cries)

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

В проге на С++, заходит ли программа в assert или нет?

То есть с -o2 вроде же не должен туда заходить, не так ли?

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

    У меня на assert'ах RUNTIME_ERROR иногда вылазил. Думаю заходит

    PS: помню даже один раз выкорчевывание ассертов сделало AC из TL. Правда не уверен что на кодфорсах

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

      Печально, когда ставишь assert(D > -1e-9) в задаче D :C

      UPD: Здорово, когда это решение все равно заходит:D

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

    Зависит от компилятора. Стандарт не регламентирует, что с какими-то уровнями оптимизации assert не должен выполняться, в g++ это не так, а вот в Visual Studio в Release действительно все assert выпиливаются.

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

System testing of div 2 finally started!

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

I had some difficulty in understanding DIV 2 E / DIV1 D's problem statement.

1 1 1

2 3 1

3 2 1

Should the answer of this case be 1 or 0?

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

    The answer is 1.

    You add the number at time 1 and remove it at time 3. So the number is in the multiset at time 2.

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

Когда поймал Мирзаянова)

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

I got TLE in fourth task. I think it isn't possible. My complexity is O(n+q) + I done it in Pascal and I don't have bad loops.

My code

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

why did O(n+q) get TLE in div 2 D? And we weren't even given any warning to use faster I/O :(

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

System testing pausing at 95% is like watching a football penalty shootout and boom, there comes the blackout. T^T

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

Разница между 100-ым и 101-ым 1 балл :)

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

Рейтинг будет сразу?

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

Frankly saying, it would be good to have it unrated XD (inb4 I'm 29th, so that's not that bad). That one zero too much in D's (or E's) was really something with very bad influence on contest (n<=1e6 and TL=1s doesn't look like even n log n should pass and it was announced after 2/3 of contest has passed) and tests to C were really weak. I got AC in C, however in test posted by FatalEagle here my solution produces completely shitty output and I expect a big part of solutions having similar precision issues which are really hard to omit in that problem (which is pretty sad, that makes this problem a bad fit for a contest).

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

    Also using cin and cout with ios_base::sync_with_stdio(0);cin.tie(0); passes pretests in div1B but fails system tests...

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

      I got lucky, because I got TLE on pretests xD. But if it is the case for some people then it really sucks.

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

    On FatalEagle's test case, I got WA too. In addition, it took about 5 seconds to run, and n=12500,so I have no idea how I didn't get TLE for n=1e5.

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

    I am getting a deja vu. Tweety is that you?

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

    And I used to think that people in Poland find giving TL=1s, n<=1e6 for NlogN solutions completely OK, after looking at some of your problemsets :)

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

Let us be able to practice please.

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

How to solve E(about 2-SAT)?

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

    Build directed graphs like what we usually do in a 2-SAT problem.

    Claim: If u is reachable from not u, u must be true. After you deal with these variables, you can assign other variables in any order you like.

    First you should check whether they are satisfiable. If both of them are satisfiable, check whether there exists a vertex pair (u,v) s.t. v is reachable from u in one graph but not the other. Then set u=True and v=False, and find a solution in the graph where v is not reachable from u.

    I haven't got AC though :p

    Edit: AC :)

    Note: I use bitset to build the transitive closure too.

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

    Suppose that both expressions are satisfiable. Let's try to find a solution for the second expression that doesn't satisfy the first one (then we can swap the expressions and repeat this again).

    If the set of variables doesn't satisfy the first expression, there should be a clause which is equal to false after substitution. Let's iterate over all clauses from the first expression and try to find a solution of the second expression which makes this clause's value equal to false. If the clause of the form (a or b) is false, we know the values of these variables (in this case they should be both false). So we need to check whether there exists a solution for the second expression in which the values of these two variables are fixed. Let S(a) be the set of nodes that can be reached from vertex a in implication graph (the graph where each variable has 2 vertices and where we add edges !a -> b and !b -> a for each clause (a or b)). What we need to check is whether contains both x and !x for some x.

    We can use bitsets to find transitive closure of the graph and also we can use them to check if contains a pair of x and !x. If it doesn't, then we know there exists a solution where the values of the given two variables is fixed and we just need to find any such solution. First, we need to fix values of the variables reachable from a and b. Then we can repeat the following: pick any variable which is not fixed yet, try to fix any value for it and then fix all values of the variables reachable from it. If there's a contradiction, flip the value of the current variable and repeat the process again. Note that we don't need to do dfs for this as we already have transitive closure computed.

    Overall complexity is O(N3 + M·N) which is fast enough if you're using bitsets (my solution got AC with time 378ms).

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

Хочу узнать мнение Codeforces: хорошо ли, что все претесты в B были квадратными?

Мой небогатый опыт подготовки раундов подсказывает, что баг forn(j, n) заслуживает бревна на претестах, но никак не на финальных тестах. А что думаете вы?

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

    Если в этой задаче сделать претесты не квадратными, то вообще одним тестом обойтись можно и тестировать нечего будет. С другой стороны, надо хотя бы сделать неквадратный тест в сэмплах, отражающий неквадратность матрицы в целом.

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

This is my first win on a rated (don't make it unrated please) Codeforces round ever!

In problem F, my solution will fail on a test case that their answer is 0 (a multiple of 10^9+7) (I could add one line to fix this bug). Can anyone construct a hack input?

PS: I was wrong. The condition of the bug of my solution is not just "answer is 0" but that must satisfy a specific condition in addition to that.

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

Why can't I submit solution to problem E now?

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

Please don't make this round unrated. As is codeforces has very few rated events nowadays. Yes there was a minor issue with testing in problem C, but when people take time out of their schedule for a rated contest, it's really disappointing to see it made unrated just because the problem setters didn't make good tests for one problem.

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

Tutorial please !?

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

Was reading comments... All these people saying things like "oh lord so many numbers, i'm too slow for it", "it's not right", "it's not fair!!!!!", "oh look at me I'm little girl and bad authors gave me too much numbers", "CF servers isn't good enough to provide fast I\O so my perfect solution pass all systests". Guys, are you OK? It's your problem that you didn't know that 4·106 I\O operations work not really fast. It's only your problem, not author's fault, not CF's slowness, it's your amateurism, that's all. If you want to improve your skills, stop crying like a little girls, blaming everybody for you fails and start learning from your mistakes.

When I started to code on Java, I looked through code of people with high rating, found out some hints and of course took fast I\O from Petr's code. And I'd never had problems with I\O. Same with C++: when i started to use this language, Burunduk1 showed me his fast I\O template, I really liked it, and since then I use it almost always. It's nice and several times faster then usual I\O, so I never think about I\O time.

What about contest... I hate myself so much! I ruined it for my team by planting amazing bug in my C solution. if (x % 2 == 1) changeParity(); See what's happening here? That's right, bullshit (-1 % 2 == -1). And I was searching for this bug more than a hour of contest. My teammate also wasted a lot of time helping me. Finally I wrote stress-testing and first test with query 1 -1 failed my solution.

In conclusion I would like to say that contest was good, problems were interesting, just don't understand why E is E, but it doesn't really matter, such things happen sometimes and don't spoil anything. Thanks to authors! Now looking forward to marathon, hope I'll have chances there.

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

    Thanks! That comment made my day :)

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

    I used x & 1 instead of x % 2 so hadn't any troubles :D

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

      Oh, i told this short stupid boring story to my teammate after contest:

      In my Java-days I was always using bitwise operations, because it worked faster. But in C++ x /= 2, x *= 4 and all other similar operations work the same time, because of compiler optimizations. So when I started using C++, I stopped using bitwise operations and began to use usual operations, because it looks clearer and more logical, as for me. And today, when I was writing this if, at first I wanted to write x & 1, but then said to myself: "Come on, boy, why do you need to do this? Use division, it looks nicer, but works just as well". So I agreed with myself and wrote x % 2 with stupid smile on my face (I'm sure it was stupid).

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

    Come on, why should "little girl" know when this freaking CF compiler work slow(Normal gcc's IO is not as slow, with speed approx. the same as scanf), which functions it doesn't support just because it doesn't (I'm about to_string, for example), etc

    After all, that's an algorithmic competition, where ability to construct algo's is intended to be checked not the knowledge of pitfails of specific wierd compiler

    PS: checked all your public c++ submissions, and didn't see anything like fast template.

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

      Normal gcc's IO is not as slow

      And what if next contest will contain a problem with 107 I\O operations? You'll also be talking about freaking CF compiler getting TLE with cin\cout? What does "Normal" mean? On your computer? I think you know that CF servers are not your computer, maybe have different compiler options and for sure different perfomance. So if you see some weak parts of your code which can cause some negative verdict, you should perform actions to prevent it. I think none of people who was thinking about I\O time on contest and knew how to read and write numbers fast didn't have problems with it.

      In my opinion, it would be more correct to say "Competitive Programming". Programming. So to participate well you need to know your language well: speed of I\O, precision of sqrt and all other features, which can be abused by problem's authors. And I also think that's sometimes authors must give problems which requires accuracy or maybe even additional efforts while using some usual built-in methods, so people know how does their language work and not just write some keywords having no idea why does it work.

      I don't know what did you check, my last public submissions contain it. For example: 17076273

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

        Normal means this one and it means on pretty much every Linux or MacOS computer(and probably any other PC that support gcc itself)

        There's a difference between the language and compilers, you know.

        Your submission was not shown in submission tabs because it's unofficial one anyway, you said you've used in

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

How can Div2 D be solved?

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

    I solved it this way:

    Notice that, no matter what operation you do, the odd and even numbers will always be in increasing order ({1,3,5,7,...}, {2,4,6,8,...}) (in a circular fashion), and the whole array will never have two consecutive even or odd numbers.

    So you can keep track of where the 1 and 2 are after all the queries. Then you can deduce the position of the other elements.

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

    Let’s notice the following:

    • offset is the same for all elements of the same parity
    • when a swap operation happens, we have to swap the offsets for odd and even guys, adding or subtracting 1 to denote the swap
    • when a shift operation happens, we simply have to add the same number for both odd and even offsets and swap them if the shift value is odd.

    Then all we have to do is print the offset values for each guy, remembering to do it in a fast way, as n can be big enough for iostream to be too slow.

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

Задача 641D - Маленький Артёмка и случайные величины

Посылка 17499640, использующая стандартный sqrt из cmath, получает WA 8.

Посылка 17499630, использующая вручную написанный m_sqrt бинпоиском, получает OK.

Уважаемые авторы задачи, вы действительно хотели, чтобы участники писали свой sqrt? Очень хотелось бы понять, ЗАЧЕМ в этой задаче такие ограничения, и какие неправильные решения они отсекают.

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

    Стандартный sqrt не работает с отрицательными числами, даже если это, на самом деле, 0 — eps. Возможно, в вашем решении достаточно учесть этот факт.

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

Why are we still not allowed to practice?

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

Что за 11 тест в задаче "C — Маленький Артёмка и Танцы"? Почему используя cin/cout я получаю WA, а с scanf/printf TL ?

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

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

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

Автокомментарий: текст был обновлен пользователем AlexFetisov (предыдущая версия, новая версия, сравнить).

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

I am not able to see others code. Is it just me or is it not unlocked yet?

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

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

    newbie question: after contest, looks now I can only view myself's source code? when I try to click other people's submissions, I can not view the source code?

    is there any way to view other people's source code? thanks.

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

Контест в целом хороший, но ошибок бы поменьше, и было бы вообще здорово :)

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

WTF?! Is E is actually E?! I didn't read it during contest because I thought that it was something like Div.1 E. After contest I read it and just wrote solution in 5 minutes using std::map<int, std::map<int, int> >.

I will always read all problems during contest... :-(

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

Someone please share your code of Div2 C so that others can find answers to their test case.

Thanks.

My Code

Now we can see others code!

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

Почему не получается посмотреть коды других участников ?

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

Автокомментарий: текст был обновлен пользователем AlexFetisov (предыдущая версия, новая версия, сравнить).

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

@AlexFetisov: It should be noted that mkisic also solved everything within an hour :)

KILE ANIMAL!

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

Добавьте, пожалуйста, задачи контеста в Архив.

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

Problems were really good. but getting TLE (in problem B Div1) because of not using "scanf" was really unfair! I used cin/cout without syncing with stdio and got TLE...

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

    I think something is strange going on in CF compiler or server. On my PC scanf/printf works as fast as cin/cout.

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

In Div-1 C, when we are solving the quadratic equation to calculate the probabilities of the two dices, can we select either one of the two roots as the required probability, or does it matter which root we select?

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

    It can be easily proven (Well I didn't think about it, I just realized) that this equation either has one answer or one of its answers are not valid (and it is 0 I guess). But in the first equation there are two answers which are the two numbers we want. (Because of symmetry).

    Many people failed this problem (including me) because sometimes we encounter sqrt(0 — eps) which is produced by double errors and the return value will be nan instead of 0.

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

      How can we prove that only one of the answers is valid?

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

        I didn't prove and maybe I'm wrong, as I said before I just guessed :-D, also I think if there exists another valid answer, we can continue from that and find anohter answer for the problem which is a valid one.

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

in problem B div2, when I run this code in my computer gives correct answer "INFINITE", but, when codeforces run this code gives "FINITE" and I receive WA.

this problem happens in the Test Case 2. someone can explain to me?

3
>><
2 1 1

17484721

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

There is something that i thought was weird during the last round after solving the A&B problems it locked to try hacking other solutions and when trying to open the submission i couldn't so i tried to open and see the hacks and i could see no hacks was there something special about this round that i missed or was there something i did wrong on my behalf?

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

А что в топ-30 изменилось? Рейтинг пересчитали, на место хуже стали в контесте.