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

Автор Errichto, 9 лет назад, По-английски

Hello Codeforces.

The CF Round #356 will happen on 8-th June (exact time). You will get five problems to solve in two hours. The round is rated.

I encourage you to read other problems if you don't like or can't solve something. The scoring distribution will be announced.

MikeMirzayanov and GlebsHP make the round possible. Also, thanks for Radewoosh, kostka, johnasselta, AlexFetisov and (more to be added?) for their amazing help. And I want to thank my girlfriend because there would be no Limak without her.

It's my first standard round. Still, you should get nice interesting problems. You will meet Limak, who is usually a little polar bear. Here he is, preparing one of problems.

I wish you great fun and no frustrating bugs.

EDIT — It's recommended for both divisions to read the Interactive Problems Guide before the round.

EDIT2, SCORING

div2: 500-1000-1750-2250-2750
div1: 750-1250-1500-2000-2500

EDIT3

The editorial with codes is ready.

WINNERS, congratulations!

  1. Petr
  2. ainta
  3. halyavin
  4. jcvb
  5. brandnewnode

and Division 2:

  1. Y_UME
  2. kaq
  3. BehtarinFake
  4. Zoli9
  5. Jeannette

Thank you all for participation and see you next time. And regards from Limak, a bear.

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

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

Looking forward to it! Such a long time since the last Div 1 round.

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

    I am taking part in the College Entrance Examination in china.

    But there is a conflict between the Examination and this contest.

    But nothing is more important than become a purple boy.

    So I give up the College Entrance Examination.

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

      I have seen your big font several times, and I think it isn't beautiful...

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

        WOW

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

        He's just very afraid of gaokao (高考) )))

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

          I apologize to all the English-speaking, below I will explain for Russian — that such GAOKAO

          Поясню для тех, кто не в теме, китайский ГАОКАО (高考) — это аналог российского ЕГЭ, только намного круче и ответственнее. И он проходит единым экзаменом в один день по всей программе, а не как в России разбит на предметы. Китайские школьники сдают этот экзамен на стадионах, гигантских актовых залах, часто не в свое городе, чтобы не было возможности "договориться". По результатам набранных экзаменов идет распределение во вузам, техникумам, училищам. Вроде тоже самое, что и у нас в России, НО — всего 5-7% выпускников китайских школ имеют возможность продолжить учебу в учебных заведениях. Остальные — работать на фабрики, поля и улицы! Поэтому истерика при сдаче просто сумасшедшая. При этом корочки ВУЗа дают высокий шанс на успешное будущее. На фото — проводы выпускников на экзамен

          Вот поэтому и я понимаю, почему КРУПНОПИШУЩИЙ нервничает ))

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

      Retarded

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

      why you can comment on this blog during the math exam...

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

You are a programmer AND you have a girlfriend!!!

you are my role model dude.

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

"And I want to thank my girlfriend because there would be no Limak without her." congratulations on becoming a father!

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

You are my favourite problem setter! Too bad I will miss this round.

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

Looking forward to "Bear and Forgotten Tree Girlfriend"! :)

Anyway, this contest will surely be great as always. Thank you Errichto!

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

Yes! The stories with Limak are always nice to read :)

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

Errichto be like, Petr's getting closer to me on the contribution list, lemme prepare a new round and make his mission impossible lol .
You always come with great problems, eagerly waiting for the round and hope I'll be able to participate, thank you .

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

    You don't seem to know how big difference it is (currently between 162 and 175). Function contribution(upvotes on blog, upvotes on comments) is rather like a cubic root or logarithm rather than linear :P.

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

I'm looking forward to it. You wrote some very nice problems in the past. I hope there will be many algorithmic problems :D

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

Limak has a great subliminal message. Reverse it first: Kamil. It is the name of first Turkish polarbear manufacturer.

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

my 1st div1 participation , am I gonna go back to div2 ?? I hope not :p

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

Errichto, Your Problem Statements are So clear to me. I Solved Your problems in Hackerrank too. Thanks You.

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

Good Luck & Have Fun!

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

We get it, you have a girlfriend.

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

Tbh, Limak scares me. The later problems turn out to be DPs, which are scary for me. The quality of questions are great, though.

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

That's GOOD

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

Guess there will be statement like that:

As Limak is a bear and he can't solve the problem by himself, so he ask you for help. Can you help him?

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

    i think it's a Plan to Strengthen relations Between Polar Bears and Humans

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

      or maybe the polar bears are some kind of alien and Errichto is one of their top spies sent to invade the earth he has already attacked Swistakk (notice the polar bear in his hands.) soon the polar bears might invade the earth. that would be unbearable

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

This may be strange, but I'm becoming a fan of Errichto, his posts, comments and problems. :)

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

Wish me good luck guys I really feel like I'm gonna make it!!

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

I'm wondering if this little polar bear is preparing a problem about powers of prime numbers ? :p

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

i really hope that the pretests would be strong enough , because it's sucks when you spend a lot of time working on Problems and gets the same position of someone spent all the time refresh room page to hacks someone else solutions.

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

    Hey, hacking is hard work! It's much harder to get 500 or 1000pts by hacking than solving a problem. Besides, once you get the hang of it it's super fun. Also, it's good to learn to code without relying on strong outside tests if you're ever gonna do coding outside of competitions.

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

Hope I can get my first 4/5 at your round, after 4 unsuccessful try -_-

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

What do you mean by "your first standard round" — were the others prepared by you a non standard?

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

    He has prepared Educational Rounds, VK Cup, India Hacks, Thanks-Round. Go to Problemsetting tab. So this is his first Standard Round.

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

It's fun that the last CF Round I took part in is on the Chinese Spring Festival, and this one is on the Dragon Boat Festival.

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

Thumbs up for those playing cards from World Finals 2012! :)

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

It's recommended to read the Interactive Problems Guide prepared by Mike Mirzayanov.

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

i think the second problem will be interactive as second card is hidden in the image .

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

    The interactive problem will be both for Div. 1 and Div. 2, according to the main post. So, it cannot be the Div. 2's second problem.

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

So it is not a standart round as well :p

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

Having interactive problems adds to fun of Competitive Programming. :)

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

It's about time I left the green phase without a second comeback

Good luck everyone

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

Oh, div2 C scores 1750, I have a bad feeling..

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

    C is easy just like typical rounds. But D and E, too difficult for me. the 5th unsuccessful attempt to get a 4/5.

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

Feels like experimental round, poor you Errichto

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

Bad feelings :(

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

I had great fun solving Div2/C. Thanks for the nice problems, Errichto!

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

My solution to problem C.Whenever i tried to submit it , my browser get stuck on the same page. More interesting part is that submitting this solution to any other problem results the same.

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

Why am I getting WA for Div2 C?

int sieve[1000];

set st;

bool isPrime(int num) {

return (st.find(num) != st.end()); 

}

int main() {

//t(); 

st= { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; 


vi v; 

for (int i = 2; i <= 10; i++) {

    cout << i << endl;

    fflush(stdout);

    string s;
    cin >> s; 

    if (s == "yes") v.pb(i); 

}

if (v.size() == 0) { cout << "prime" << endl; fflush(stdout); return 0;  }

if (v.size() ==  1) {

    if (!isPrime(v[0])) { cout << "composite" << endl; fflush(stdout); return 0; }

    else {

       cout << v[0] * v[0] << endl;
       fflush(stdout);
       string s; 
       cin >> s; 

       if (s == "yes") { cout << "composite" << endl; fflush(stdout); return  0; }

       else { cout << "prime" << endl; fflush(stdout); return 0;  }

    }


}


if (v.size() > 1) { cout << "composite" << endl; fflush(stdout); return 0; }



return  0;  

}

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

i got stuck on C because i didn't take perfect squares in account

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

How to solve Div 2 — D?

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

    What I coded up and finished a bit after the end was this:

    First, generate first few terms of sequence, and oeis the rest: http://oeis.org/A055402

    Then hardcode those values, and for a given m pick the best value you can. Call this best value v. Decompose v into its cubes, then(from highest to lowest) try incrementing each cube(n^3 becomes (n+1)^3) while making sure the sum doesn't exceed the given m. Then output this sum. I didn't get to submit, so I'm not sure if this is completely correct

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

      Oh, I knew I weren't the only one who tried to look up this very sequence in OEIS.

      Came up with almost the same approach and got WA 4 (see 18325136).

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

According to me , the 3rd problem should be able to differentiate between coders and the number of people who solve should be <=700,800. That was definitely not the case today.

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

 image 2 of my submissions were submitted at the exact same second . Can one of these be removed while considering penalty >.<

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

Problem Div2 C was really easy for hacks, because it had week pretests! For example, I hacked two people using "94" as a hack because they didn't check for 47. Another hack was "49", so no perfect squares.

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

TNX for your perfect contest and fast editorial guys.

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

After try spending 1 hour and 45 minutes on Div1-B:

I'll need to train harder next time...

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

    Dont Worry the number of the contests coming are more than those which have passed :) All of us needs to train harder :)

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

    I couldn't think of a legit solution either...

    I ended up using a really sketchy solution in which I check the 500000 numbers below m and take the optimal value (can't prove it's correct, let's see if I AC).

    edit: darn got WA

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

    Why didn't you try div1-C then?

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

    Spent whole contest trying to solve B and then solved C in 20 minutes after the contest....

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

Errichto when can we expect system testing? In 5 minutes or in a hour?

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

А все потому что закончились шишки и приходится курить табак((((( никогда не курите ребята!! никотин вреден для мозга я тому пример седня!!!(((

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

I want to know why my solution got run time error for div2 b. can anyone pls take a look? link to submission Thanks

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

I completely forgot to input m as a long long for problem D.

At least my solution probably had a bug somewhere else!

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

Again, A massive gap between Div.2 C and Div.2 D ...

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

Вобще блин так растроился(((( Теперь рейтинг точно упадет(((( Нада к Майклу в сазанку ехать он стопудово надрочит меня задачки щелкать на раздва(((

Ребята поддержите меня пожалуста мне грусно!!(((((((

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

    Желаю, чтобы если и падал, то только рейтинг, а не как это обычно у спортсменов бывает

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

      Это да у нас в качалке на одного гантеля упала пришлось скорую вызывать(((( но он сам дурак знал же свой рабочий вес но нет мгновено шварнегром стать решил. но все равно жалко пацана(((

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

I managed to find number of cubes in D and minimal volume. Was it the right way or this information is useless?

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

Forgot «47» in C... short div[] = {2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49} Frustraiting...

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

Can anyone please explain how to obtain the 0.916666666667 in the 3rd sample test of problem D?

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

    If I remember correctly, you should twice use BCD in city 1. If you get distance 0 then you win immediately. Otherwise, for sure Limak moved between cities 2 and 3 — guess one of them.

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

hacked two solutions in div2 C and then realized that i was screwed ! 25 and 49 will hunt me down tonight . :(

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

Now-a-days contests have become extremely rare. And then to provide a contests like today is so disappointing...To do so much upsolving preparing for contests..for what? An interactive problem that almost 70% of the candidates can solve? Noooo...This is just not done..

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

    Speed matters too you know !

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

      Absolutely....I wasted too much time on C and got stuck on 1200 position...if i would have solved it faster...my position would have been under 500 as I had a lot time for C :(

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

        You could also use hacks on Div2 C even if you had lost some time, there were many participants with wrong code because the pretests were weak. After submitting my first 3 problems I ended up being somewhere near place 250, but with 3 hacks I got to the place 47 and thus I am Div1 now :)

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

    If you would've solved problem D, you wouldn't be complaining. Keep upsolving, and you will keep do better and better :)

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

Thank you for a wonderful round!)

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

Thank you very much, Errichto! I loved the problems!

I came up with the efficient approach for C right after the contest ended and it took me some 10-15 minutes more to code it, but I enjoyed the contest nevertheless :D

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

my eyes almost got cancer from debugging this.. only realizing my l and j is swapped after the contest is finish..

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

The waiting for rating change has just begun.

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

Thank you for participation and for kind words. Also thanks for bad words (as long as it's something constructive/reasonable). Btw. div2 participants can now check again a picture from the blog. Do you know why is there one card hidden?

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

    Congratz for the contest, it was really good in my opinion (maybe difficulty raise was a little too high between div2.C and div2.D, but still I really enjoyed this contest).

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

    Because you hided it??

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

    Because

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

Awesome contest!!! :D Solved 3. Coded brute force dp for 4th one but failed to find a tiny bug in time which was resulting in wrong answers for the tescases :/

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

My view of the points system this round 500 — 750 — 1250 — 2500 — 3500

Honestly, I miss the dynamic scoring.

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

18329338 -_- It gives a proper output in CodeBlocks but wrong in CodeForces !!! But why ?

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

a moment of silence :D

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

This contest was outstanding.

It's the first time I solve C during the contest and I turned green :)

thank you Errichto.

hope to see you make new contests soon. :)

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

Awesome round, especially Div2/C. Looking forward to seeing more interactive problems in the future! :)

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

Наконец-то фиолетовый апнул, найс раунд.

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

Very interesting round! The most interesting round in a while for me. Thanks for the interesting problems! Wish I could've solved div 1 C :/

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

I think Div 1 C/D may be easier than Div B :)