gojira's blog

Codeforces Round #164 (Div. 2)
By gojira, 12 years ago, translation, In English

Hello everyone!

The Codeforces Round #164 for Div.2 participants will start in several hours. Traditionally, the other participants can take part out of competition.

The hero of today's problems is Manao, which has been straining Georgian fellow programmers' minds for several years already. He made it to Codeforces pages thanks to Gerald and Delinur, who have assisted me in round preparation. The problems were also tested by Seyaua, sdya and Aksenov239.

The scoring system will be a little unusual: 500-1000-1500-2500-2500.

Good luck :)

UPD: The contest is over, congratulations to the winners:

  1. first_love

  2. dianbei_10

  3. yefllower

  4. dpij

  5. cenbo

You can find the tutorial here.

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

Comments Comments (54)
| Write comment?
»
12 years ago, # |
← Rev. 3   Vote: I like it -41 Vote: I do not like it 
get(PlaceinRound);
while(TimeLeft > 0)
{
     SuccessfulHacks++;
     PlaceInRound--;
     ProblemsSolved += min(TimeLeft / 30,1);
}
ProblemsSolved = min(ProblemsSolved,5);
Cout<<"Good Luck!";
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Infinite while, place in round decrement with only one when winning 100(successfull hack)+nb_point_of_problem, Problems solved over 9000 before "ProblemsSolved = min(ProblemsSolved,5);" and "good luck" after the end of the contest... And yes, I am very fun at parties.

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

Hi , gojira First contest at codeforces written by you :) , Looking forward for it. Some day I believe I will also write a contest for codeforces :)

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

Who is eligible for round preparation?

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

    They have not mentioned any age restriction on the FAQ page. So I believe that there is no constraint except your problems should be interesting.

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

    Let me know when you get the answer

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

    and what we will get in return...?

    → Reply
»
12 years ago, # |
  Vote: I like it -14 Vote: I do not like it 
Round 164 'A' - 1  (Div 2)
164 == 
2 * 82 == 
2^1 * (1^2 + 9^2) == 
2^2 * (4^2 + 5^2)) == 
2^3 * (4.5^2 + 0.5^2) == 
2^4 * (2.5^2 + 2^2) ==
2^5 * (2.25^2 + 0.25^2) ==
2^6 * (1.25^2 + 1^2) ==
2^N * (a^2 + b^2)
1 < N < 60;  a,b = ?
→ Reply
»
12 years ago, # |
  Vote: I like it -23 Vote: I do not like it

when i became a red coder :(

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

This is round 164 & 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 Here , 12+4+2=10+8=18 Again , 164 = 13^2 — 2^2 — 1^2 = 14^2 — 6^2 +2^2 Here , 13-2-1=14-6+2=10 What a combination :D

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

    As, 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 , the problem points could be distributed like this --> 3000,1000,500,2500,2000 , as 3000:1000:500:2500:2000 == 12:4:2:10:8

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

pages of in queue. judges are down?

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

I hope I wasn't the only one who didn't know what expected value is :(

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

Combinatorics round with nice problems, I liked it! Thanks to the creators!

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

Can anybody help me in understanding the reason behind using comparision function ??

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

    The change in expected total length from swapping the order of adjacent tracks [i] and [i-1] is equal to

      track[i  ].length*track[i  ].chance*(1-track[i-1].chance)
- track[i-1].length*track[i-1].chance*(1-track[i  ].chance)

    since [i] might now be repeated due to [i-1], but [i] can no longer cause [i-1] to be replayed. Swapping has an effect on the expected playtime of these two tracks alone, so it's always best to swap pairs for which such a change is positive.

    You could intuit that continuing to make such swaps would look a lot like bubble-sort (or rather, is bubble-sort); more rigorously, use some simple algebra to show that the expression above is consistent as a comparator.

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

      and how do we calculate the expected total length?

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

        A song will be replayed every time it is liked but a later song is disliked, plus the once the first time it is seen. We take the chance of being liked multiplied by expected number of later dislikes and add one:

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

I am new to codeforces , can anyone tell by when my rating willbe update :) ?

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

nice problems, enjoyed the contest

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

Hi gojira,

I really enjoyed the problems, thanks for the contest. I saw a lot of hacks for 3rd problem, that's good, thanks again ;-)

B.

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

Love win =) standings(смотреть среди официальных участников)

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

9 successful hacks in problem C :D it was really funny :D

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

whew,that was really lucky for me,first time contest writer from my country first time div 1 ^_^

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

Could not understand Problem B — Buttons. Can anyone explain it? words "push" and "press" are same? "some" does it mean single button or can be group of buttons?

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

    Yes the words "push" and "press" mean the same. You can only push one button at a time and you need to output the maximum value of the number of times you can push the button, before getting the right permutation.

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

My submission with id 3029515 got wrong answer on first test case. But its giving the correct answer in my system

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

    How is that possible?

    http://mirror.codeforces.com/contest/268/submission/3029515

    It really returns 2 on your system?

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

      It returns 3 on my system which is the correct answer. On the judge it returns 2. It is pretty weird.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it 
        return pow(sqrt(ds),2)==ds;

        Are you sure? This line doesn't really do anything except check for floating-point error...

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

        On my PC it works too, but on ideone it does NOT — http://ideone.com/ooqeop

        In debug mode there is different output:

        ideone:

        a=(0, 1)
b=(0, 2)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(1, 0)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(1, 1)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(1, 2)
(pow(sqrt(ds),2)==ds)=1
a=(1, 0)
b=(1, 2)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 0)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 1)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 2)
(pow(sqrt(ds),2)==ds)=1
2
0 1
1 0

        my PC:

        n=2, m=2
a=(0, 1)
b=(0, 2)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(1, 0)
(pow(sqrt(ds),2)==ds)=0
a=(0, 1)
b=(1, 1)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(1, 2)
(pow(sqrt(ds),2)==ds)=0
a=(1, 0)
b=(1, 2)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 0)
(pow(sqrt(ds),2)==ds)=0
a=(1, 0)
b=(2, 0)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 1)
(pow(sqrt(ds),2)==ds)=1
a=(0, 1)
b=(2, 2)
(pow(sqrt(ds),2)==ds)=0
a=(1, 0)
b=(2, 2)
(pow(sqrt(ds),2)==ds)=0
3
0 1
1 0
2 2
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the information. but this is very strange.

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

    In 268A, I submit 3 times and get WA on test 6, which have the right answer is 6, but the system returns 83. Anyone can explain that for me ?

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

      lines 27-28: instead of 

      long n, res;
long a[mxn][2];

      should be 

      long n, res = 0;
long a[mxn][3];
      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please can someone tell the way to solve problem C...

→ Reply