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

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

Привет всем!

Сегодня состоится Codeforces Round #276, который пройдёт в обоих дивизионах. Время старта — 19:30 по московскому времени (перейдите по ссылке для просмотра времени в других регионах). За помощь в подготовке контеста спасибо Zlobober, за перевод на английский спасибо Delinur, и спасибо MikeMirzayanov за сам проект Codeforces.

Желаю всем удачи, надеюсь, вам понравятся задачи :)

UPD Разбалловка в обоих дивизионах будет динамическая (подробнее об этом можно почитать здесь). Задачи будут упорядочены по возрастанию сложности, тем не менее, не забудьте прочитать все задачи до конца контеста.

UPD Контест окончен! Спасибо всем, кто решал задачи несмотря ни на что. Разбор будет опубликован позднее.

UPD Разбор можно найти здесь. На моё удивление задача div1C оказалась довольно сложной и по количеству посылок сравнялась с div1E, а во втором дивизионе эту задачу вообще никто не сдал за время контеста. Удачи вам в покорении разбора :)

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

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

Please short explanation for problems. --> Because read story of problems is too tedious.

Also explanation of sample tests. For better understand problems.

" THANKS FOR READING

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

Блин , время стандарта изменилась для нас ( Россия же перешла на зимнее время ) :(

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

Please give me '-' till my contribution reaches 0 and then stop.

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

Now I know the reason behind late , Bug oversolver

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

1 hour later is not good for me

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

I am new to code forces.What is div 1 and div 2 in round #276?I could not register in div 1 so have registered in div 2 .May i know how div 1 and div 2 users are distinguished

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

Думал написать контест вместо лекции, а ее отменили:( Как думаете, писать теперь или нет?

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

    Думал написать контест вместо лекции и отменил её.

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

your last contest(#256) has nice problem.thanks~

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

What's a good tool to visualise the call graph of my code as it solves a sample test case? And that won't take much time overhead to use during a contest? (For Python or C++.)

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

    so for simple:

    foo() {
        bar();
    }
    main() {
        for ( int i = 0; i < 10; ++i ) foo();
    }
    

    you want to see what?

    main
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    	foo
    		bar
    

    ?

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

    In Visual Studio you can see good visualisation (screenshot is in previous edit) Is it what you want?

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

      I cannot see the screenshot (in Rev. 1)...

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

      Something like that. But also a bit different: it should be a graphic so I can take one look at it and know what went wrong. I think I'll have to write my own. It would be easy to parse the output such as what appears in your screenshot or of a profiler for either Python or C++.

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

Hope short and simple problem description just like the announcement :)

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

Very bad time for Asian participants

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

Куда ушел Gerald?

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

not able to wait..

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

1 hour later is very bad for China. It is 0:30 for us, what a sad story!

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

I hata the start time, it's too late in our country

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

Ненавижу voting-систему codeforces, точнее голосующих. И пофиг, что меня заминусуют.  Если фото не загружается

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

    Слабые, зависимые от чужого авторитета личности смотрят исключительно на цвет пишущего. Вот это скорее всего заминусуют:)

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

I'm Unlucky in dynamic score :(

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

Please unlike me :) Plz

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

I am always curious to know why do the authors declare the score distributions at the last moments. Has it anything to do with the number of registrants??

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

    I am always curious to know why do the participants care about score distribution before the last moments

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

Hope to see a nice problem-set and +ve rating growth.. Dynamic-Scoring has always haunted me :P

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

Server is too busy and can't open any of the problems, is it only me?

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

I don't know what happened, but there are more than 1000 submissions waiting for judging.

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

Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue

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

Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue

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

I can't send any problem. Is the round going to be rated?

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

Is it rated today?

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

In queue

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

It's 11 p.m. I tired to wait. And I'm going to sleep.

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

Nice set of problems, but the system is making it almost impossible to compete.

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

Good short statements ;)

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

It's a bit frustating to have busy server when contest are going. Hope for extra time, and fixed system soon.

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

seems round will be unrated ;( ... anyway, keep solving!

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

Раунд будет нерейтинговым ??????

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

unrated :)

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

"This round will be unrated due to technical issues."

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

if contest rated , I will up rating, but it is unrated. I am very sad !

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

How about providing the problems in pdf, as in the gym, along with the online version, so that if server is getting overloaded then people can do with them (download that file initially as a back up)

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

After the contest started I thought, "Awesome problems, awesome statements. I really hope I everything goes well today! :)" An hour later... "Long queue, contest is unrated for technical issues". Now I'm thinking, "Why did I have to jinx it?! :(("

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

this round is like BAYAN contest ... great problemset but ...

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

And a buggy round by oversolver :(

Waited long for a DIV2 round and got this :/

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

    I don't think that it's oversolver's fault

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

      No, but the irony in his handle :D

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

      I know it's more like a server fault. But I noticed that Div2A points were changed twice. First it was rated 1000, then 500 and now 1000 again. So, I do suspect that some way or the other, oversolver is at fault, if not majorly.

      Update: It's 500 point problem again.

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

        The points are changing only because the score distribution is dynamic. If C is solved by many people by the end of the round, it will probably bring only 500 points.

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

          I know its dynamic. The guy in the top of my room had 900+ point in problem A. Now he has 480 points. The score of an individual changes after correct submission too? I'm sorry, I didnt knew about it.

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

            I don't think you know the correct meaning of dynamic scoring. The scores change based on the number of correct submissions on a problem. The lower correct solutions, the harder the problem is thus higher the score and vice versa.

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

        this is normal to happen in dynamic score, first the score is 1000 then more people solved the problem makes it 500 then more people make wrong submission as a first submission(or solved another problem) which increase number of participants making the points of the problem back to 1000

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

          Oh thanks. I didnt knew about it. I take my criticism back :P

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

            In Soviet Codeforces, you can't take it back.

            Aren't you aware of the Russian proverb: "a word ain't a sparrow: once released — it can't be recaptured"!

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

    Such a pain, when there's finally div1 contest where you can participate... and clar says it's unrated :'(

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

del, всё ясно.

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

    Надеюсь, больше не будет комментариев от тебя.
    oversolver, все отлично, задачи классные.

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

If only I can punch person to death I will punch myself. Such a waste of precious sleeptime.

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

Стоило Fefer_Ivan уволиться — тут же раунд нерейтинговый. Подозрительно.:)

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

Говно контест..... жалко(((((

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

    убейся

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

      Не офигел? Умный что ли?

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

        что-то ты плохо старался

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

          Говорит человек, который не сделал ни одного сабмита в контесте

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

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится -19 Проголосовать: не нравится
            Комментарий удален по причине нарушения правил Codeforces
»
10 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Сколько еще должно пройти таких нерейтинговых раундов из-за сбоев, чтобы можно было перестать обновлять страницу каждую минуту? Когда Codeforces перестанет тормозить, это далеко не самый высоконагруженный в интернете сайт? :\

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

    Я уже тут полгода, и до сих пор сайт не застрахован от наплыва каких-то пяти тысяч человек, его же можно тупо заддосить посещением на контесте!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -31 Проголосовать: не нравится
      Комментарий удален по причине нарушения правил Codeforces
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Не жалко времени было создавать аккаунт для примитивного троллинга? Уходи в свои раковальни, или хотя бы друзей в реале найди

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

ПОТРАЧЕНО

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

    Она со мной, углепластик, так охладите сервер, я рассматриваю ее пользу!

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

Лично мое мнение..вам, товарищи, нужно вообще-то радоваться,что кф вообще существует, засирать любой горазд!

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

contest is unrated . . . keep calm and . . start self mutilation. . . :-"

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

Solves div2 C in 5 minutes -> unrated round.

Tough luck =(

Is anyone having trouble locking problems? i want to try to hack some solutions, but i can't seem to find the button to lock a problem.

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

Раунд нереитинговый

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

Well, I decided to improve my ranking. Not destiny :)

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

5th November of 2k14... the day that Codeforces died...

http://i.imgur.com/LN2DJZV.png

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

    "Remember, remember, the fifth of November" Codeforces Edition

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

      Keep calm friends. I know codeforces is not doing well today, but instead of backfiring at it why dont you try to solve the problems, or even go to sleep, than blaming contest writers, platform etc. Remember, the joys the platform has given you, the job you got by practicing at this platform, the money, fame so many things. And one day it is bad and you show this attitude towards it. I am sorry If I sound harsh, but it preety much shows people's character.

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

    Somehow it reminds me about Black Day of Codeforces

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

Ow God knows when the next contest will be ... :(

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

ridam to contest :) tnx

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

Remember, remember the fifth of November, the Gunpowder treason and plot; I know of no reason why the Gunpowder treason should ever be forgot!

I guess Codeforces system blew up in the spirit of Guy Fawkes Day!

But in serious matter, there were 5000+ competitors and this is the 276th round. One would expect the system to be more stable by now. I personally feel sad for oversolver because that was one good problemset and I think he deserves some credit and I'm quite sure that it wasn't his fault at all. And about changing problem scores mentioned above, scores are dynamic, of course they will change!

Well, anyway I liked the problems so thanks for the good problemset :)

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

it is my worst contests always "Busy Server" or "in queue"

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

I`m so sorry but I have to give up this contest for many reasons:-( Expecting next competition ! :)

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

http://hsin.hr/coci/contest1_tasks.pdf 2 задача и B задача этого контеста, ухх

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

Is hacking disabled due to the contest being unrated? I cannot lock my problems

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

There are still 40 minutes remaining, but I'm very sleepy. I will sleep now.

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

Sorry, guys. It seems that it was my fault. I don't know all the reasons why everything happened bad. The main reasons are:

  • ext4 partition on one server switched to read-only mode because of unknown reasons (I will try to diagnose this),
  • judging code used old version of our http-wrapper library with resource-leak.

Sorry again about it. I apologize to the writer oversolver he did his job great. Be sure, some sleepless nights are waiting for me!

P.S. Fefer_Ivan, it is hard without you...

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

    I also want to say thank you for those who didn't stop participating just because of contest being unrated and who continued solving nice tasks that oversolver prepared.

    I hope that we will see new contests set up by him again!

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

    no problem at all

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

    Nothing to sorrow. At least I learned something by trying the problems. Just it will be nice if we have the upcoming contest soon. Thanks! :)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится
    ext4 partition on one server switched to read-only mode because of unknown reasons

    The kernel remounts a filesystem read-only if it encounters an I/O error on the underlying device. If this is what happened, then the kernel log should contain the details.

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

Блин, что-то не оверперформится мне на нерейтинговом раунде)

Хотя если вспомнить мою формулу рейтинга контеста

R = 2^A + Q, где

A - количество accepted

Q - quality

то все хорошо, можно ложиться спать с хорошим настроением, пока не подоспели систесты)

UPD не смог не дождаться систестов) ABCD сдались впервые) Пусть и не оч честно (D по сложности лишь немного выше С и времени было больше), но мне пофиг, спасибо oversolver :D !!

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

how to solve div-1 d .

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

    You want to partition the sequence in subsequences each of which will be "going up" or "going down". Solution is a DP where you state is (position, down or up).

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

    My solution (possible solution, I don't know if it's the correct one) was the following: - You can build a DP like dp[i] = min j < i(dp[j] + maxValue(j + 1, i) — minValue(j + 1, i) - The solution above is too slow O(N²), but you can notice that maxValue(j + 1,i) — minValue(j + 1, i) is increasing as we decrease 'j' and that dp[j] is increasing as we decrease 'j'. The sum of one increasing function with one decreasing function is a function that increases and then decreases. - Given that fact we can actually do a ternary search on the maximum 'j', so now we reduced our solution to O(N log N)

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

      "The sum of one increasing function with one decreasing function is a function that increases and then decreases."

      Are you sure?

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

        Not so sure, that's why I don't know if my solution is actually right.

        My intuition was telling me to assume that dp + max — min is a function that can be ternary searched.

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

          It's actually false: Sum 1 3 7 9 and 9 8 3 2

          yields 10 11 10 11 which increases, then decreases and finally increases again.

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

            Yeah, you're right. I guess the lesson is not to trust your gut at all times, they may be wrong!

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

      The sum of one increasing function with one decreasing function is a function that increases and then decreases

      Nope , you're wrong take this example:

      A= 10 20 30 40
      B= 50 45 25 20
      Sum= 60 65 55 60
      
  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    DP. Sequence rises up and down.And the key-point is you will never separate a continuous sub-sequence into more than one sub-sequences if this sub-sequence is straight up or down.For example:

    -2 4 5 1 -7 3 6

    you should divide them into :

    -2 4

    5 1

    -7 3 6

    or

    -2 4 5

    1 -7

    3 6

    or something like that.

    You can figure out that the only thing you need to handle is which part should the peak and the bottom of the sequence belong. Turns out a DP problem.You can check my code.Hope that helps.:D

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

    Also it has simple O(N) solution:

    x = -a[0];
    y = a[0];
    ans = 0;
    for (int i = 0; i < n; ++i){
    	ans = max(x + a[i], y - a[i]);
    	x = max(x, ans - a[i + 1]);
    	y = max(y, ans + a[i + 1]);
    }
    cout << ans << endl;
    
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Could you please explain why this works? I looked at it for a long time, but I can't figure out what x and y represent. Thanks in advance.

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

        In optimal answer any segment that making a group contains their minimum and maximum values on borders. So, we can write following dynamic solution, which find answer on each prefix of array:

        or

        Therefore it is sufficient to remember and update the maximum values of ansj + aj + 1 (y in my code) and ansj - aj + 1 (x in my code) at each step.

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

Заметка на будущее — это плохой код.

int64_t x;
__builtin_popcount(x);
»
10 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Классные задачки, но почему-то нерейтинговый раунд. Обидно.:( А автору спасибо!

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

When will system testing begin?

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

i really loved the C Problem, i'm not sure why, but i just loved it :D

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

No rating is not bad for mee, round was difficult... waiting system test...

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

How I solve problem D?

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

Thanks for the Nice problemset oversolver , I just wanted to tell you that I enjoyed the round despite the technical difficulties that were being caused by codeforces .

PS:If you like what I have said above then give it a '-' .

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

Is there some tricky case for Div1 A/ Div2 C?

I solved it as follows: let the answer be stored in res. go through the bits of the 2 numbers(from left to right). If the current bit is 1 in both then set that bit in res. If it is 1 in r only then set it to 0 in res and make all next bits 1. In the end count the number of 1s in res and the number of 1s in r. output the one with the max.

What's wrong with that?

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

    So... I have finally seen the test that failed me and it seems to work fine locally but outputs a wrong answer in Custom Test... Can anyone tell me what could've gone wrong here? Submission

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

    i had the same problem but i fixed it, you must think what happens when you have a case like this:

    Left = 6 ; Right = 7

    6 is written in binary like 110 7 is written in binray like 111

    following with your approach you will go to the last bit and set it as 0 then all the remaining bits as 1, but in this case you will return 6 and the correct answer is 7. So, you must care the case when it is the last bit, if they only differ in the last bit you must return Right

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

      Actually not... As I said, at the end I count the number of 1s in r and the number of 1s in res and print the one with more 1s... In this case, I'd print 7 :D

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

contest had many bugs bugman! :)

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

All problems are very interesting! Thanks to oversolver.

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

All problems are very interesting. Thanks to oversolver.

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

(http://i.imgur.com/nvtu5ZI.png)

still waiting for my first hack attempt :D

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

When you are as bad a coder as me then technical difficulties are not such a big problem for you! :P My only submission was Div2 C at 2 hours 7 minutes past the start of the contest and it got tested without any delay.

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

    My only submission was Div1 A at 0 hours 6 minutes past the start of the contest and it got tested without any delay :D

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

Div1 D:

We can prove that each groups must be increasing or decreasing. So we can solve it in O(N) with using ordinary DP.

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

    Or the problem is just asking to traverse the array from left to right choose some numbers and add to solution and some other numbers and subtract it from solution such that at any time during the traverse number of numbers that you added to solution differs from number of numbers that you subtract from solution by at most 1 but at the end the two numbers should be equal , this can be solved by very simple dp my code 8576807

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

      Lol, how simple. Reminds me of 383D - Antimatter with a long explanation for the official solution and a short one for the one most people found.

      (It's not like DEGwer's version is much harder — you just need to think when it's better to split/merge a group and it follows almost immediately.)

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

    I like D , I tried to solve it ( but got TL ) with DP , ternary search and segment trees.

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

I have seen Div1 B in a Japanese high school programming contest.

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270

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

Awesome problems. Variations were really good. Problem A was tricker than usual. Problem D was a very creative one.

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

За сколько работает этот код???

for(int i = 2; i <= n; i++) { int j = i; while(j <= n) j += (i — 1); }

у меня вроде такая же сложность как у цикла этого, но ТЛ 7 ловлю(B div 1).

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

Nice problem at all, thanks for the contest. Btw, someone can describe the solution of problem Div2C/Div1A? Please)

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

    greedy will work :). let b = number of bit in R (upper bound).

    now start from res = (1<<b)-1. (all the bit 1) now start removing power of 2 from right to left until you have res in the given range.

    If removing a power of 2 gives you a number less then lower bound L then do not remove it, try next one...

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

    go from li to ri increasing the number of ones in his binary representation :

    for example

    li = 0010001 -> 0010011 -> 0010111 -> ...... until it reach some number equal or greater than ri

    ri = 1010101

    when I say increase number of 1s , I mean add 1s in the 0-positions from right to left, every time you add an 1 digit the result number is the minimun number with 's' 1 digits ( s = current number of 1 digits in the result number ) greater than ri , you can prove it.

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

Good problems. Bad network.

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

Как div. 1 C?

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

How is Div2-D / Div1-B to be solved?

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

Thank you oversolver for this amazing round. I took the best place I ever had, and that gave me faith. My self esteem is in your debt.

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

Why do we need to run the loop 'm' times in Problem A of Div-2?..

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

    in case we have 65535 65536, Answer is "Yes". so , we must check until m or else we may get a wrong answer in this brute force method .

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

Thanks oversolver for great problems. I was sad when I read announcement but I was happy after system testing (because my solution A failed) :)

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

Thank you oversolver for such an awesome problemset! If the servers didn't have issues during the contest and ran smoothly I think it would've been an even better one. I hope we'll see more rounds from you in the future! :)

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

Quite a nice contest :) My first hack ever! Thank you oversolver.

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

nice contest and fast editorial

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

Why rating system is too slow? Or is it a unrated contest??

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

Just wondering, is this the first time for a contest being unrated? Anyway the div2 problems are as good as your last contest. Thanks, oversolver.

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

8573331

Output
qertwy
qtewry
qetyrw
Answer
qertwy
qtewry
qetyrw
Checker comment
wrong answer 1st lines differ - expected: 'qertwy', found: 'qertwy'

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

My rating didn't change after the contest...

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

Country wise rankings have been updated for this contest. Although I know many people left the contest half way, including me, but still had to update the site.

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

next div 1 contest after two weeks...

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

when will the ratings be updated?

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

fuk u