gen's blog

Codeforces Round #165
By gen, 12 years ago, translation, In English

Hello everyone!

Codeforces round #165 will start today at 19:30 in Moscow time. It will be a round held in both divisions, the first one after a long two-week break for Div I participants. :)

This time the problems were prepared by me, Evgeny Vihrov (gen), and Krisjanis Prusis (cfk). Apart from competing together in ACM ICPC this year, we are also colleagues in a project that involves much algorithmic thinking. Actually, some of the contest problems were born during the work on this project.

In this contest you will get to know a legendary hero Emuskald of many talents and help him complete his ingenious ideas. The problems cover a multitude of algorithmic concepts, so as always we hope that each participant will find a problem that matches his taste.

Big thanks to Gerald Agapov (Gerald) for help during the preparation of this contest, to Maria Belova (Delinur) for problem statement translation and also to Mikhail Mirzayanov (MikeMirzayanov) for the excellent contest-making platform for Codeforces — Polygon.

We wish you an exciting round!

UPD1: Score distribution:

DivII: 500 1500 1500 2000 2500

DivI: 500 1000 1500 2000 2500

UPD2: Congratulations to the winners!

Div I

  1. PavelKunyavskiy
  2. Egor
  3. tourist
  4. rng_58
  5. tomasz.kociumaka

Div II

  1. woxihuanni
  2. mnbvmar
  3. QLSpirit_011
  4. PraveenDhinwa
  5. leviathan

UPD3: Tutorial is available.

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

Comments Comments (77)
| Write comment?
»
12 years ago, # |
  Vote: I like it -41 Vote: I do not like it

I love contests !!

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

Remarkably the two of our problem setters Evgeny Vihrov (gen), and Krisjanis Prusis (cfk), have exactly the same rating, besides being project mates.

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

求轻虐>_<

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

why is the handle changing item removed???

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

    So slow... Handle changing has opened in first 10 days of New Year.

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

Another rated contest for the div1 contestants after 2 rounds.

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

Ideas generated from project, I am pretty sure that problem statements will be long. :( .

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

    I was wrong. Problems were short in length. Nice.

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

What will be the point distribution ?

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

After a little break, I'm going to write today's contest... Good Luck

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

"the first one after a long two-week break for Div I participants."

This touched the bottom of my heart...! :D

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

I haven't wrote contest almost 2 years

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

WOW number of registered in Div1 reached 850

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

is something wrong with the judge or this is normal??

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

This contest should be declared unrated as the server was down for a long time as well the verdicts came late :\

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

I hope it'll be declared unrated

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

What is the notorious pretest 4 for problem A in div 1?

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

    1

    3 1

    Answer : 4

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

      Even simpler, 

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

        1

        0 1

        I also think the answer is: 1 Could you help me explain it?

        yes, it is true. it can not contain itself.

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

      wow! Didn't notice the "strictly less"... Back to division 2 then, I guess :D

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

      UPD. understood

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

      Through out the contest I considered that the largest box could have been used as the final packing box and so I output 3 to the above case. And Now I read "He has decided that the best way to pack them would be inside another magical box" :(

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

        The correct reason is "strictly less than" not "another".

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

          I personally interpreted the problem as ->if the largest box can fit in all other boxes, then why go for an even larger box and not take it only. So for me, the reason is "another". Dont know about others.

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

    Hey there, i had the same problem too. Turns out i did not read the problem statement carefully. :(

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

Today I couldn't hack from Firefox (the popup window didn't move and "Hack" button was below the bottom of the computer screen).

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

    I experienced this before. Click 'Tab' several times until the hack button is highlighted, then click 'Space' or 'Enter'.

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

      yup,i can never hack from chrome,the same problem,i have to use IE -_-

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

        IE?! :)

        What can IE do except making your system stop working? :)

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

      You can press F11 and "hack" button will be seen.

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

    I came across the exact same problems several times on Google Chrome before.

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

    You can also decrease the scale of the page content until you'll be able to click the "Hack" button.

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

Hey , i was getting badway 504 in last two minutes of contest. And in the last two minutes i was waiting to submit my solution to 3rd but couldnt do it due to that 504 error. Please Please please consider my solution for C now as i had completed it in time ,else it will be unfair .

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct logr {
       double k;
       double x;
} box[50];
bool key(const logr &a, const logr &b) { return (a.k < b.k); }
int main() {
    float min;
    int n;
    cin>>n;
    for (int i=0;i<n;i++) cin>>box[i].k>>box[i].x;
    sort(box,box+n,key);
    for (int i=0;i<n-1;i++) {
        if ((pow(2,box[i].k)*box[i].x*pow(2,box[i].k))>(pow(2,box[i+1].k)*box[i+1].x*pow(2,box[i+1].k))) {
           min=(pow(2,box[i].k)*pow(2,box[i].k)*box[i].x)-(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x);
           min=ceil(min/(pow(2,box[i+1].k)*pow(2,box[i+1].k)));
           box[i].x=(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x)/(pow(2,box[i].k)*pow(2,box[i].k));
           box[i+1].x+=min;
        }
    }
    min=pow(2,box[n-1].k)*ceil(box[n-1].x/2);
    min=ceil(log(min)/log(2));
    cout<<min<<endl;
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I vote for considering his solution and I'm not afraid of negative feedbacks ^_^

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

    sorry mate , It would have got run-time error, max size of box is set to 50 :P

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

    anyway you got Wrong Answer.

    1
10000000 4

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

      Yepp, i know , there was a correction in the 2nd last line , instead of divisoion by two , square root would have come ^_^

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

        no, whole your code is wrong.

        you need to solve the problem without using pow or log because of big constraints

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

I mean, seriously, are those statements supposed to explain the problem, or confuse it even more??

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

    Sorry, they were shorter in the beginning, but we had to explain some subtle things and they grew in size... :/

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

      I am not talking about length, I am talking about how much useful the information you put, was aiming make clearer the task itself. Let's mention for example the task Div2 B, the definitions of updated or not are so misleading.

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

      And this coordinates in Div1B ; /... I've read description 5 times to be sure that these coordinates are just a mislead :d... Not a funny joke, but pretty confusing :d

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

        Why do you think it is a joke? Determining what data do you need is an important part of solving a problem.

        Also, I think that all statements were rather clear and unambiguous. (Div2 at least)

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

        I can understand that can be frustrating... But there were reasons for coordinates:

        1. Just by looking at the sample, you can tell that one can replant a plant anywhere at real coordinate.
        2. The origin of the problem had coordinates also, so they were kept.
        3. It is often quite valuable to tell that some data is redundant, and is a good reminder to trust your reasoning.
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it -37 Vote: I do not like it

          Anyone, who isn't a monkey, will immediately know that if you can replant them into any real coordinate (what was clearly stated in description), exact coordinates are redundant. Putting something like that in the description won't take any positive effect. It causes thoughts like "Either I am dumb or author thinks that I'm dumb". Reading the description few times took me more time than solving+coding :/

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

            That wasn't the intent. :D But I'll try to make short and clear statements in the future, this time it just was an experiment for us to write extended legends about one hero.

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

            So, in your opinion reading the task is not included in solving it. I would beg to differ. Understanding the statement is a first step in solving every task. Hence, if you rushed too fast or haven't done it well — sorry, there's no one to blame except you (except if the statement was way to unclear, but it's not the case here in my opinion). Well, I have seen quite a lot of tasks where some information doesn't matter — it's your task to decide what you need and what you don't. Some perfectly valid tasks could even be one-liners, where all you need to do is to understand the statement. Why not?

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

              You're all talking "determining which data is important" is a part of solving task. But in this case this was so obvious and it hasn't caused effect "Oh! I'm so smart, I figured out that this coordinates are not important! Such a nice result!" but "Probably I didn't read description carefully, because it would be too obvious if those coordinates really were redundant."

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

My solution for problem C wasn't rated. http://codeforces.net/contest/269/submission/3052470

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

    Tyle przegrać!

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

    I still don't get point for my solution ;/ It is correct. I resummit it and i get AC.

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

I think Test #12 in problem C is wrong, because "If there are several solutions you can print any of them."

Edit: Sorry guys i get it!.

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

    But the sink will be node 2, the problem specifically says that the sink is node n.

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

    "Vertices 1 and n being the source and the sink respectively."

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

    In this problem, there cannot several solution because there cannot appear cycle.

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

What's the idea behind div1-B and div1-C?

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

    Div 1 B-> Just have to take out the Longest Non-Decreasing sub-sequence(k). Since you can move plants to any real co-ordinate, there are plenty of them. And the answer becomes n-k

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

      Can you tell me what the coordinates which given in the input used for?

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

        I believe they are just to trick you into thinking you need to use them ;D

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

I can't understand why the coordinates are given in problem div1 B

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

    "Because fuck you" :P. Poor joke. Just to mislead contestants ; /

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

    You don't need those co-ordinates to solve the problem

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

    Well they matter because the plants need to be sorted in ascending order in order for N — LIS to work.

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

      Yes, but they are already sorted on input.

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

Hi. Does anyone have any idea how the code in below could work correct in my computer and get WA on pretest 2 on CF? I checked it with MS and GNU and they gave Compilation Error and WA on pretest 2 respectively. here's the code: 3060066 thanks.

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

Can anybody tell me what were the bugs in Div1 C, which weren't detected by pretests, what caused so many succesful hacks? I'm pretty curious about that.

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

    When we use BFS we shouldn't add vertex number N to the queue. You can view test 12, it is quite small.

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

link to editorial please?

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

    In the Russian thread gen has said that it's not ready yet, so it'll be tomorrow.

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

thanks for nice problemset. I realized I shouldn't pass a round even if its writer is Purple.

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

    Thanks, glad you liked it!

    → Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +4 Vote: I do not like it

Testcases in Div2.C are not strong enough.

My code got AC, but fails on this test:

2
0 1
1000000000 1

link: http://codeforces.net/contest/270/submission/3062842

BTW, if youare interested why it fails look at this line: ll xarisxi = pow(4, 1.0*(V[i+1].first-V[i].first)); where I calculate 4 to the power of the difference between two quantities of boxes.

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

Congratulations to kelvin to be the first participant who has successfully upsolved the hard problem 269E - Теория струн: 3062253!

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

    Thank you for the congrats and for preparing a great contest! During the contest, I was very happy to find out that I know how to solve the hard problem, but equally sad when I (after 30 min or so) find out I probably cannot finish it in time :p

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

Div 2 was really good and amusing contest , questions were just so cool , i loved solving them , thanks gen :)

→ Reply