Yury_Bandarchuk's blog

Codeforces Round #332 (Div. 2)
By Yury_Bandarchuk, 9 years ago, translation, In English

Hi, Codeforces.

I am happy to say that Codeforces Round #332 (Div.2) will take place November 20th at 19:35 MSK. This is my second Codefocres round and I hope not the last.

Thanks a lot to Dmitry Rozhkov (rui-de) for solving these problems, also thanks to Vlad Vishvevski (Vladik) for cool pictures. I'd like to thank Gleb Evstropov (GlebsHP) for help in round preparation. And, as usual, big thanks to Maria Belova (Delinur) for statement translation and to MikeMirzayanov for such great systems as Codeforces and Polygon.

The duration of the contest is two hours. What about tasks, it's not a secret that you can find Spongebob's pineapple and a restaurant with strange name "Crasti Crabs", cosy beach and Jellyfish Meadows on the bottom of the ocean. Spongebob and his friends need in your help, help them!

I strongly recommend you to read all the problems and, probably, you will find something right for you.

As usual, scoring distribution will be announced later.

UPD: Score distribution — 500 — 1000 — 1500 — 2000 — 3000.

Editorial.

Div. 2 Winners

jerjerismygf

rakhashov.maksat

jeremy624lolz

Div. 1 Winners

MrDindows

anta

ngfam_kongu

Congratulations!

  • Vote: I like it
  • +415
  • Vote: I do not like it

Comments Comments (137)
| Write comment?
»
9 years ago, # |
  Vote: I like it +167 Vote: I do not like it

First problem be like:
Spongebob and Patrick like to light fire under the ocean when it's cold! ...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Spongebob was developed for mentally retarded children..

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are many hacks in this contest.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      And there are many wrong answers on main test too I didn't join the exam but i see "Wrong Answer on Main Test" when i check somebody's wrong code...

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +38 Vote: I do not like it

I won't see SpongeBob anymore if I lose rating in this contest :/

** And you're the reason Yury_Bandarchuk :'( **

UP: I won't see SpongeBob anymore :/

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

Good way to celebrate children's day :D

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a nice idea. Good luck to everyone

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Good Luck All ^_^

→ Reply
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

is it only me who hasn't seen SpongeBob? :P

→ Reply
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Not sure if it's codeforces or cartoon network

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Did you mean Nickelodeon? :P

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      yup my mistake :p , i'm not a big fan of cartoons .

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is Codeforces just probblemsetters adding this pictures(or cartoons pictures) just for fun.It is more enjoyable for coders!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Especialy when you have to wait longer to download 1st problem

      → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

i hope short problems statements :)

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Time shedule change. Today's contest time 19.35 . I hope next contest time 19.35(1/2).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I love Spongebob and I hope " I love this contest " too :D.

→ Reply
»
9 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Two Future Contest already Announced , So Nice :)

→ Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Thanks to autors for Round!!! Good luck all contestants

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Spongebob is love, Spongebob is life. This contest's gotta be good.
Someone dare to say "I hope Spongebob dislikes math?"
(Downvotes swarm incoming...)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    If he dislikes maths, he'd ask you to solve his math problems. If he loves maths, he'd be too busy and he'd ask you to solve his math problems. It's maths either way.

    → Reply
»
9 years ago, # |
  Vote: I like it -31 Vote: I do not like it

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Oh God... Codeforces should restrict such big images.

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Yah :) A coding month :) Just love it :)

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Have a nice evening and good luck everyone~~~

→ Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

if you see this coment and you will have a increase of rating！you Konw I am lucky star!

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wish Mr.Plancton doesn't have a evil plan for your rating! good luck all CF members! :))

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

is it spongebob photo album or round announcement ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why late 5.00000 minutes.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what about scoring distribution?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    As usual, scoring distribution will be announced after the contest.hahaha.......

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Forgot to register, NOOOOOOOOOOOOOOOOO!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is scoring distribution?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Spongebob and his stupid friend Patrik are here to challenge us quite interesting!!! :-)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When do you want to announce the scoring distribution?contest is starting :|

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It was published in Russian version of the post, but the author forget to add it to English one.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      When are you going to remove Russian Codeforces?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why would we do this?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          To save the amount of work and reduce the level of confusion. Besides I've heard some time ago that Russian CF was supposed to be removed.

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was hacking test of prob B?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wish I knew it :(

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      It's difference between Ambiguity and Impossible. Example

      3 3

      1 2 1

      3 3 2

      Will give Impossible but your code maybe giving Ambiguity.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    2 2

    1 2

    1 1

    ->

    Possible

    1 1

    2 2

    1 1

    1 2

    ->

    Impossible

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think if the case is "Ambiguity" and "Impossible" at the same time, it should be "Impossible".

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Actually I just realized that 

      5 5
1 1 1 1 5
5 5 5 5 5

      should give "Possible". I'm printing "Ambiguity" even if the b sequence doesn't use the ambiguous key.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    In that case when answer is possible but you have printed Ambiguity even it is not appeared in B.

    3 3

    3 2 3

    2 2 2

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used this

    3 3
1 2 2
1 2 3

    Most of the codes (including mine) give "Ambiguity". But the correct answer is "Impossible".

    PS — I hacked 3 codes using this test case.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    Edit: C has more successful submissions then B :| :|

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3 3 3 3 1 3 3 2

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone else got WA #16 for E? I am really curious about that test case.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is D all about a cubic equation?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup. Wish I clicked on it sooner. I clicked on it literally 2 minutes before end. Couldn't solve C, or B.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Solved the problem D 2 sec late hope my solution idea will be wrong. Edit: Solution is wrong:)

→ Reply
»
9 years ago, # |
  Vote: I like it +52 Vote: I do not like it

This always freaks me out before realizing that System Test hasn't got to my correct submissions yet.

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

after this contest i will never see Spongebob :((

→ Reply
»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Nice problems, superfast editorial and superfast system testing! This contest can't get any better! :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B isn't written well, I don't understand it until now

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it's written perfectly well, and it's crystal clear.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Number of AC solutions in B indicates that there is something wrong only 1100 AC solutions in B is a very small number compared to previous contests

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's because the pretests were a little weak.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Look again

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, counting the solutions AFTER the contest (i.e. all the people who fixed their solutions and submitted) is really dumb.

          Go here and turn unofficial results OFF, and you will see that B was solved by 984 participants while C was solved by 1043 participants.

          Indeed, the rule about Ambiguity > Impossible was not clear.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 2   Vote: I like it +3 Vote: I do not like it

            The statement says "(...)If there are multiple suitable sequences ai, print "Ambiguity".(...)"

            When the answer is "Impossible" the number of suitable sequences is 0.

            My first solution for B was hacked but I must admit that the statement was clear, the problem was my lack of attention.

            I think that the low number of AC's was due the difficulty of the problem, it's harder than expected for B.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry, I didn't know that. After all, I am a mere Pupil. :)

            → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    f is a function means that the ith f equals to f(i),so bi=f(ai). And I was confused too. But problem B is nice.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's well written. It's just tricky. I got hacked and I couldn't figure out my mistake during the contest. Turns out it is wrong to immediately print "Ambiguity" after finding more than one such index. This is because at such point, it is still possible for the answer to be impossible, i.e. there exists no such sequence a.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Got Runtime Error in test case 33 for Question C. But, my program is able to solve problems for higher n without runtime error. How is it possible? http://codeforces.me/contest/599/submission/14373631 Sorry found the mistake.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Interesting round! "weak" pretests, many hacks at the end :)

→ Reply
»
9 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Bad contest :|

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

But...But anta last visit at 25 hours ago

→ Reply
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

why is still system testing for me and can't submit anything, but number of accepts is getting more and more?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You are not alone, so silly things are happening right now..

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WTF???

      Ratings changed but I still can't submit...

      And also there isn't any friends rating changes in standings.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mine is still at system testing too.

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

For problem D
for(i=2; i<10e6; i++) : WA65
for(i=2; i<2*10e6; i++) : AC (after contest)

:( my calculations gave cube_root(x); it turned out to be 2*cube_root(x);

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you must do it to 1442251, because it can be ans for x around 1e18

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A gray participant who solved all 5 problems. Just wow.

→ Reply
»
9 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Didn't expect such a good problemset from the fan of the cartoon for idiots.

I had a really good time, thank you! Look forward to see your next contests!

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

D was much easier than B & C.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm sad to get WA on test 65. I'm extremely sad that there isn't test 66 after I accepted it! :(

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Congratulation rakhashov.maksat for solving all five problems. From today you are my new inspiration :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    From today (s)he is my favorite troll :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also surprised to see his ranks. How it possible ? In CF round 325 he was newbie, But in 332 he collects 535 rating. What occurs in last 7 contest for him ?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

easiest contest i ever solved

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That moment when u are confused about ur own solution's time complexity...

Submitted it assuming it to be O(sqrt(x))(expecting TLE)

but it was O(cuberoot(x))

a confusing loop:

for(i=1;i*i<=x && (x/(i*(i+1)))>=(2*i+1);i++)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (x/(i*(i+1)))>=(2*i+1) ---> x>=(2*i+1)*(i*(i+1)) Now it's not confusing ;)

    → Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Yesterday I was 16 and today I am 17.
Yesterday I was expert and today I am candidatemaster.
Come on!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On the proble C: Tests was less than need. That is cod TL 14376989

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is generator which it kod get TL

    include <bits/stdc++.h>

    using namespace std; int main() { int n = 100000; cout << n << "\n"; cout << n << " "; for(int i = 2; i <= n; i ++) { cout << i — 1; if(i != n) cout << " "; } cout << endl; }

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

why it's "Practice is allowed only for finished and unfrozen contests"?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I have this problem too . what should we do !? UP : It's fixed now (at least for me !)

    → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

+535 New Record Oo

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Here is my vision of the problem A.

By any means we should get to the Shop 1. How many ways to do that?

1. Paths to Shop1

2. Paths to Shop2

3. Now, get back Home :)

And the code looks like this:

int min_path_to_shop1 = min(d1, d2 + d3);
int min_path_to_shop2 = min(d3, d1 + d2);
int min_path_to_home  = min(d2, d3 + d1);

int total_path_travelled = min_path_to_shop1 + min_path_to_shop2 + min_path_to_home;

I've solved just A. But I hope that at least I could be helpful to those who struggled with it :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It might have been more fun to make pretests for A weaker. I actually thought about only two situations at first, but I realized that there were another two, not using either the path to A or B. It was kinda tricky. But the problem B also had some hacks, so... NICE CONTEST!!!

Also jellyfish for the next time...?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any thoughts, when will we get a tutorial for this contest's problems?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its already there. Check editorial link

    → Reply