albertg's blog

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

Hi!

On 3rd December, 18:00 at Moscow will be Codeforces Round #281 (Div. 2). As usual Div. 1 contestants can take part out of contest.

This is my first Codeforces Round and I hope that this isn't the last one :)

Thanks to Maksim Akhmedov (Zlobober) for the help in making contest and MikeMirzayanov for Codeforces and Polygon platforms.

UPD1: The scoring will be dynamic.

UPD2: Contest is over. Thank to all participants. I hope you liked my contest.

UPD3: Editorial

UPD4 Top-5 contestants, congrats

  1. ShiXingxing15

  2. ganar27

  3. Tim_LinYd

  4. coolwyj

  5. gaoyihan

Also congrats to gaoyihan, who solved problem E.

UPD5 Hack stats by kostka.

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

Comments Comments (129)
| Write comment?
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Fixed :D

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

you must be confused

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

Tow blog ? why?

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

Wow, what an intriguing round number; 281 is the sum of the first fourteen primes!

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

    Yes... And its sum of digits is a prime really interesting

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

    and its number of ones in base 2 is a square such an interesting number

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

      this number also represent the area of a square with side length

      it is also the 281st natural number.

      it also can be written as sum of two numbers!

      also you can notice that if you added 5 to this number then subtract 5 it will back to the same number 281 !!! What a magic !

      WOW the number 281 has a lot of nice properties which make it very interesting number! this is impressing!!

      I feel this round will be very special because of this number!!

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

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

        Wow, I also noticed that 281 is either an interesting number, or the first non-interesting number, by induction!!

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

        That's why you are the king of numbers :p

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

        You are exactly the King of Numbers. You know a lot of special things about numbers :D

        P/s: HidenoriS was a bit faster :(

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

        u cant find so much thing for 282

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

        Someone wanted Codeforces div.3 to appear. I think I could compose some problems using this amazing piece of enlightenment:
        1. Given a square side length, which is represented as square root of the some natural number, write the area of given square. 2. Given an array of numbers, where each array element equals to its index, write a 281th element of array. 3. You are given an interesting number 281. Each test case contains a number X. You should know that when you subtract number X from 281 and later add X to that result, you have the same number — 281! But you are to test vice versa. You firstly try to add number X, and only later you subtract number X. If you gain number 281 output "I've found 281 has an amazing property!", otherwise: "I still need to learn some math basics". 4. Output three numbers: two numbers which sum equals to number 281, and third number: base that represents these two numbers. Be careful! Both numbers which sum equals to 281, must have the same property, that thay can be composed of two other numbers.

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

    Also

    281 = 9*8 + 7*6 + 5*4 + 3*2 + 1 + 2*3 + 4*5 + 6*7 + 8*9
    → Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

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

    Also hope to see a nice problem-set and rating growth..

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

This contest's registration will be end 30 minut before the contest Be careful!!!

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

Good time for Asian participants :)

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

PLZ unlike me :))))) PPPPLLLLLZZZZ

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

Hope more than 4000 contestants.All the fighters fight each other. Happy Coding.

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

Hello Every Body

I Love Codeforces <3

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

I want unlike plz unlike me (:

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

Dynamic scoring and 4000+ contestants?! Lets hope that the testing system wont crash. Good luck everyone and to a higher rating!

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

What does dynamic scoring mean?

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

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

what does locking a problem do???

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

    to be able to hack others solution in your own room

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

Hacks and Hacks in Problem B. I didn't see such amount of Hacks in a problem.

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

    Many people forgot to implement all the conditions to break the ties and decide a winner. I got 2 good hacks with the case:

    2 -1 1

    or

    2 1 -1

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

Guess what -33 submissions on E and growing ... solving E isnt worth a penny anymore its score will be like 150 to me...

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

Sweet, sweet revenge :)

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

Good bye blue color see you again :(

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

This feeling...

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

So, what were the horrible tests at B? It seemed pretty simple to me and my solution wasn't hacked but boy, there were tons of hacks. So any specific corner cases?

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

    overflow?

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

      Well, I'm impressed by the amount of overflows then :D

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

    Overflow on a test like this:

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

    Probably overflow in sum calculation?

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

    I managed to hack two solutions with

    4
1
5
-2
-4

    because lexicographic comparison wasn't implemented correctly.

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

    Many people forgot to implement all the conditions to break the ties and decide a winner. I got 2 good hacks with the case:

    2 -1 1

    or

    2 1 -1

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

    Participants tried to concatenate two strings and compare them lexicographically. So for example I hacked with that test:

    4
11
1
-9
-3

    11 > 9 => true, but 111 gt 93 => false

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

How to solve E ?

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

    Firstly, from P(t) = a, you should notice that sum of all coefficients of P(x) should not larger than a. Secondly, from P(a) = b, you can find the minimum of sum(noted as S) of all coefficients occur when you decompose b into base a and all coefficients are smaller than a. And for other type of decomposition of b, the sum of all coefficients will be at least S+a-1. So when S>1, you only need to check the decomposition of b with minimum sum of coefficients. And discuss special case when S=1.

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

      Oh, that's a cool solution, I was sure it'd be some difficult math on polynomials, but it seems like it was easier than expected.

      And wow, aren't you unlucky to fail E because of one line of code :P

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

Is D really such sort of trololo?)

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

    Well technically if you don't come up with the idea it isn't clear that it's so simple. And also dynamic scoring makes it possible to give such a problem, since if it turns out to be too easy, the score will just go down :P

    Though it's cooler to give such problem to contests where you don't see a global ranking, since when you notice 800 people solved it, you'd think it's something simple, and you might even get it right without any idea why it works.

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

If you can give me an anti-case for the solution below of problem D, I can give you hundreds of System Test Failure:

if(n%2) cout<<"black\n"; else cout<<"white\n1 2\n";

Thanks for having such a funny problem! :)

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

    It is a correct solution :)

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

      I submitted the problem based on a hunch and without calculation, was really surprised after it passed. Then tried to make counter cases but failed to do so :p

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

      I sent this solution, but can anyone explain why is it correct?

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

        If n % 2 == 1 then black can use symmetrical strategy. If n % 2 == 0 then white can do step right, forgot about leftest column and do the same symmetrical strategy.

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

    No one can find "anti-case" of correct solution :D

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

Tell me, that solution for D is not:

    if ( (n & 1) == 1 ) {
        System.out.println("black");
    } else {
        System.out.println("white\n1 2");
    }
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It certainly is! =))

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

    Having (n <= 10^9) in this kind of problems might indicate a simple solution ;)

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

In last minute i could not submit my code for server (page Loading) problem :(

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

For anyone asking, yes, the solution for D is that simple (4 lines of code).

If n is odd then black can mirror moves, and as soon as white takes something from the middle column, black can take white.

If n is even, then white can play "1 2" and ignore column 1 for the rest of the game. In this way you can view it as if they are starting a new game on nx(n-1) field and black is first. Now white can use the above strategy since the number of columns is odd.

It's good that the problem had dynamic scoring, else it would've been a messy competition.

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

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

    and i failed on A and C XDD

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

    i saw more than 100 too...but finally his code got present pass...

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

A and B was easy. C was interest. hope my C will survive in system testing

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

How I can solve problem B?

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

    Literally follow the statement and do every check as it says.

    First check who got more points. If it is equal, check which sequence is lexicographically larger. If it coincides, check who had the last technique. Simple as that

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

Oh my... I misunderstood B "lexicographically" as appending all scores into string then compare them...

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

Can someone give a proof for D? :D

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

I'm not a professional hacker. Could you please tell me why this is getting invalid input for C?

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define ll long long 
ll dp[6000];
int main()
{
	cout<<200000<<endl;
	for(int i=0;i<200000;i++)
		cout<<1999999999<<" ";
	cout<<1<<endl;
	cout<<2000000000;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Possibly there should be a new line between the "1999999999" numbers and the "1" number. Your solution has 3 new lines in total.

    Though I have no idea if that is the cause.

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

    Because on second line you output 200001 numbers

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

    Change cout<<1<<endl; to cout<<endl<<1<<endl; and try then.

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

    Codeforces validators are very strict. You can't print a space after the last number and each line must end with EOL.

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

is it good practice to always use long long instead of int to avoid overflow problems like in problem b?

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

    I had such period in my programming carrier where I would use only long long. On first glance it seems like a good thing but on more serious competitions such as IOI or ACM requiring some tough data structures or time limits on the edge, then long long can make the difference, as it takes twice more memory and is considerably slower than int when doing a lot of operations, so I stopped using it.

    However in Div2 A,B,C, I think using long long always shouldn't have any drawbacks.

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

    It depends. Sometimes it might slow down the program (operations on long long aren't as fast as on int) or exceed the memory limit (long long is a 64-bit data type while int is a 32-bit type).

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

    testing system has 32 bit processors, so use 64 bit integers only if necessary.

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

Oh, I didn't notice "If there are several such scores, find the one in which number a is maximum." in C :(

I didn't notice to use something like long long instead of int for B :(

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

Very good, balanced contest! Congratulations, albertg

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

don't care about high rating this time ... just adore to remember submitting any solution and get pretests passed and laugh xD xD

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

test: #38 in the problem B

input: 3 -12 3 9

output: second

why is second and not first?

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

I just didn't passed problem A and i had error ... so i left the contest...

Maybe contest was good but i don't know why i was like this... :(

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

My 99th rated contest. bye bye div 2....!!!! Nice to have 100th round in div 1...!!!

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

Is it contest too??? Why, problem D very simple, than A,B,C?

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

    Problem D doesn't need being harder than A,B,C. Take ACM/ICPC as an example, the problems aren't sorted by difficulty. That mean you should read all the problems first.

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

I liked this contest. Although I didn't done it well, but I think the fact that all the problems have such simple answers and they didn't need using any special structures was interesting... ! :D Well done albertg and thank you for this contest : )

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

For problem A I got wrong on pretest 6. How can a football player get two red cards in the same match ??? Isn't it a mistake when input makes us realize that in a football match one player can get two red cards .... how funny -_-

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

    In this problem player will not be removed from the game after a red card :/ Kinda weird

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

From the statement of problem E, I couldn't understand that ai are non negative integers. However, after a time, I noticed that they were, but still, they should've mentioned it...

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

I have one small doubt in problem A. I had used variables t (its value is either 'h' or 'a') and card (its value is either 'r' or 'y') to represent team and type of card respectively. If I keep there data type as int then the output shows runtime error. If there data type is used as char then the code works fine. From my understanding, variable of type char can also be represented by int. Please correct me if I am wrong.

Thanks

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

    When you read an int the system will try to find an integer — not a character. For a char, the system just find the nearest char after \n or ' ' to read.

    When you call for an int input, since the int was never found (for example, the last line of input) your program returns runtime error.

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

      natsukagami: Thanks for your quick reply. It would really help if you could elaborate your answer a bit as I could not understand much.

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

        Representing a char as integer is fine, inputting it however isn't.

        If you have characters in the input you can't read them using int variables. You could read them by char. Later on, there's no problem to store it in int variable, but the way input works won't let you read characters as int.

        That's what I believe natsukagami meant :)

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

          Actually, I myself was wondering this:

          int a;
scanf("%c",&a);

          Will it work?

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

            No it does not. If you print the value of a, it prints some random value and not the one that you gave as as input.

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

          Enchom : Yes I also believe the same. Just curious to know more from the C++ perspective.

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

Shouldn't it be forbidden to talk about contest in blog's during contest? Some posted information can be accidentally useful for someone. Comments about hacks and predictions of problem price dynamics can serve thoughts how to use competition time more effective to achieve better performance. Nor it is a table of results, there are not shown analysis, predictions or breakthroughs from these results, and if participant want, he should do it by himself. If participant reads, that many hacks are made on problem X, this can save him time to search by himself which problems are hot on hacks. And if participant reads that there are many hacks on problem Y, this can save him time for not searching manually that statistic in many pages of results, even if there are no hacks in his room.
http://codeforces.com/blog/entry/14959#comment-199414 on 1h 55th minute of contest
http://codeforces.com/blog/entry/14959#comment-199415 on 1h 56th minute of contest
http://codeforces.com/blog/entry/14959#comment-199416 on 1h 56th minute of contest

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

I got a wrong answer at final test on problem B because I used longint instead of Qword...

A big lesson for me in next contest.

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

For problem A I never knew that if a player got a red card, he/she can still get a red card, which fails my solution. Forgot to use long long for Problem B :( Knew how to do E but fail and some case. :'(

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

http://pastebin.com/UjZFdCXR

Why with this code I take wrong answer in testcase 6. Could anyone help me,because I cant find my error for some hour... Thanks !!!

→ Reply