Gerald's blog

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

Good Day!

The next Codeforces round will start soon. It will be held by usual Codeforces round rules.

The author of today's round is Mykhailo Granik (Fcdkbear), he is listening the lecture at the Winter Kharkiv Programming School now. Great thank him for this contest!

The score distribution will be standart: 500-1000-1500-2000-2500.

Good luck to all!

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

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

Good Luck Every One!:D

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

waaah, I hope, I could get better rank than last contest.. :D

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

    we all hope same thing will happen (to us), good luck ;-)

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

Too bad, there's only Div. 2.

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

I didn't find any other contest with his name as a problem setter.I hope to see some great problems and a brilliant contest. HF & GL.

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

I hope I can get the good grades :) I am in China, so the local time in there is 11:30 pm. T_T but I still like attending the Competition like this to improve my Programming skills and English !

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

    I know that feel, bro. I'm in Indonesia and its local time is 22:30.

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

      I'm vietnamese, the same time with you Ariza :D. So tired but may be I will learn some thing good :D

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

    It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-

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

      I think it's better for you to hope to not sleeping at work. Trust me..

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

Hello, can you please explain why on task C the answer to the first test is 25 and not 26?

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

    becose you can reorder array (5,3,2) and get (2,5,3) ans=3*5+2*2+2*3; this is most most optimal way to get max ans

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

I can't hack problem C due to file size restrictions, currently 256kb... This code:

int main()

{

int i = 1;

int n = 2 * 1e5;

int q = 2 * 1e5;

cout << n << " " << q << endl;

for(int p = 1; p <= n; p++)

{ cout << i; if(p == n) cout << endl; else cout << " "; }

for(int p = 1; p <= q; p++) cout << i << " " << n << endl;

}

generate a huge input (about 3.3 MB), it's a special input with maximum numbers for the queries and values N and Q, 2*10^5.

Currently, there is no way for send this input, or the code generator... :( ... then, I can't hack solutions, that surely get TLE on the finals tests.

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

    this issue has been discussed many times.

    you should use generator.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it 
    #include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	printf("200000 200000\n");
	for (int i = 0; i < 199999; i++)
	{
		printf("200000 ");
	}
	printf("200000\n");
	for (int i = 0; i < 200000; i++)
	{
		printf("1 447\n");
	}
	return 0;
}

    I sent this test to hack one solution of task C and got the incorrect test verdict with the message: FAIL Expected integer, but "#include" found (stdin) [validator validator.exe returns exit code 3]. Can someone say what's wrong?

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

      You submited it as test, not test generator. So it was got to validator as is. #include, which is first token is not an integer. Message informs you about it.

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

      There are tabs for that purpose ;)

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

Nice problems, Unfortunately I misread problem B so that I didn't solve it until last 15mins.

anyway I enjoyed the contest :)

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

    yeah, same here. but still a good contest with clear problems.

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

I submitted problem C a lot of times, but every time judge gave Wrong answer on test case number one. As test number one is same as given in the sample input , I checked on my computer. It was working fine.

I could not even run my code on custom test because Custom test did not work properly and issued an error : Form elements must not have name or id of "submit".

Could anybody tell me what the problem could be ??

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

    did you make sure that you give your variables and arrays initial value 0 ?

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

      All the arrays were globally declared. I am only using the indices of the array on which I am overwriting data.

      Do I explicitly need to make all the global variables zero ??. I think they are zero by default.

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

        I don't know why this is happening to you,

        but sometimes I face the same problem so I give zero value to arrays and it will be solved

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

          I am not able to use custom test due to error "Error: Form elements must not have name or id of "submit".".

          It gave output 21 on the test case no one as shown in the final tests. I really do know why it showed output 21 ??

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

    In your compare function, what happens if a.value != b.value and a.type != b.type?

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

      Oh yes, this is where the actual problem lies. It was somehow working fine on my computer. Thank you very much :)

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

    I suggest you to test your code on custom test to see how it works on CF Compiler. I faced the same issue earlier and they told me to do it when I asked in clarification.

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

I think these problems are very good without problem statement of B. I'm not good at English, so I used translate system. But I couldn't understand problem B at all. I wish there had been an explanation for samples...

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

I DP problem C but it seems like there is a trick for this problem :(

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

    this is not DP.

    you should see the indexes that has most frequent and assign the biggest numbers to this indexes.

    it's Greedy.

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

      I have Solved it by using DP, you should see my code! :)

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

        maybe there is DP solution, but I see that greedy is easier.

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

          You have one solution,how i saw(nhandi,kingofnumbers) and you are talking about different solutions

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

            I am not able to read his solution because of strange language but my solution is not DP!

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

              non dp : for(int i=0;i<=n;i++){ w+=ct[i]; ct2[i]=w; }

              his dp : c[0] := 0; for i := 1 to n do c[i] := c[i — 1] + d[i];

              he just store what he found before in c[i]; while on the other hand (on non dp), we just need one variable w to store the previous value

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

        It is the same solution for both of you, and it's greedy :)

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

It is the first time that I solve all the problems in a Codeforces Round! THX!

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

    you should try div2 contest more often :D

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

Here's an unofficial editorial: http://www.codeforces.com/blog/entry/6778

Great round!

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

OMG someone fake me

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

    there is a different one letter :)

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

    It's different in all letters, If you use a strict checker. :D

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

    I think, they have to ban him

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

      What about your ID? XD

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

        Someone took egor, I take that login name everywhere, but I couldn't do it here. So I liked someone has that number, so I took it too.

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

          me too me too~~~~~

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

            You are fake!

            UPD: Oh, may be you aren't. tourist50216

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

              I can't believe that it's coincidence that new three users have similar names in one contest.

              this is not coincidence, this is happening on purposes.

              furthermore both have the same number 50216 !!

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

    I always wanted to ask, does your nickname means anything or it's just random letters?

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

    What about this one(WJMZ8MR)?

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

Can someone explain why my solution http://codeforces.net/contest/276/submission/3189675 gives output '141517992919' on Codeforces compiler and '9382' on my compiler (which is the expected answer)? I am using i686-apple-darwin11-llvm-g++-4.2 compiler.

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

    On this test your program produces

    /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/debug/vector:336:
    error: attempt to subscript container with out-of-bounds index 65, but     
    container only holds 65 elements.

Objects involved in the operation:
sequence "this" @ 0x0x8058170 {
  type = NSt7__debug6vectorIiSaIiEEE;
}
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On my computer it also gives output 9832. I do not why this is happening. Same is happening with me in problem C with test case number 1. :(

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

    I have same problem with problem — C . My solution 3189369 failed on Test-3 ( According to Codeforces ) , But its giving expected 9382 on my pc( Ubuntu-12.04 ).

    When i tested here , its giving different result . Can anybody help me to point out errors in my code ..?

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

Thanks for the contest, very nice problems, everything clear in the statement. I enjoyed this contest ;-)

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

http://codeforces.net/contest/276/submission/3188798

For fun.

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

My submission 3189731 failed for test 20. What's wrong with my code? On my pc it gives the correct answer.

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

the problems is very good for me

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

Funny, the same algorithm gave me TLE in java but not in c++. java -> http://ideone.com/wkFEuE c++ -> http://ideone.com/fsUknS Good Codeforces, nice way of discouraging non-c++ coders on your platform

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

    You have to know, that Arrays.sort in Java works in Theta(n^2) time for some arrays of n elements. Learn Java.

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

    sort() in java might degenerate to O(n^2), if it applies on an array of primitive type

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

      So, should I use Integer wrapper? it does not pass either.

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

        I recommend you to shuffle array before sorting.

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

          Is there any method to confirm if shuffle will always lead to a better performance? Also what exactly could be the cases when the Arrays.sort() leads to O(n^2). I am asking as the description given on official Oracle page is quite blurry.

          This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

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

            What is the probability that from a given worst case — order of elements, doing shuffle you will obtain the same order? The probability to win lotto is bigger than that :)

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

            Theoretically you can still hit the worst case after shuffle, but the probability of this event is negligible. You can see the anti-Java-sort testcase generator here.

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

              Actually, my generator is not working properly: recursion's depth is not maximal. There's a bug somewhere but I couldn't find it :(
              Nevertheless, it works about 2.5 sec. on Codeforces servers.

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

                :-(

                I still consider it a very valuable effort.

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

For problem B, what is the answer for "aabb" ? Below is what i feel, please correct me

The first player can for palindrome "abba". He takes off 'a'
Second player can form palindrome "bab". He takes off 'b'
First player cannot for a palindrome and hence Second player wins.

But correct official answer says "First". What am i missing ? Can some body explain how First player can win ?

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

    The first can already reorder the string to a palindrome.

    "If the player before his turn can reorder the letters in string s so as to get a palindrome, this player wins."

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

    The first player can for palindrome "abba". He is a winner! Second — losе

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

    player wins if he CAN form a palindrome before deleting operation

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

for problem D... can anyone tell the answer of input is 15 and 17..?

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

Why did this submission generate WA? 3186879

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

    You have a mistake.

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

      Which one? because this one generate an AC 3187782

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

        Bad-bad bitsets? Visual C++ can't even compile this code.

        UPD "no operator found which takes a right-hand operand of type '__int64'"

        So, the problem is between long long and bitsets...

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

The author's Editorial in Russian : Codeforces Round #169

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

Screencast of me solving this round.

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

Hi, I would really appreciate some help debugging my code to problem E. I guess my idea is basically something similar to other people solutions, here is a poor described sketch of it (I apologize for that): ... (if you want to read it it is on the previous versions of this post ;) )

Edit 1:

Got Accepted! After debugging for 5h I made some small modifications and it passed the tests.. I am too tired now to check what the error was, I need some sleep :p, I will check it tomorrow and update this post!

Here is the accepted submission: ACC

Edit 2:

Found it! It was a very silly mistake (embarrassing), on naming who is the tail of the current branch. Thank you all and sorry for bothering :)

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

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

    English editorial was published 2 days ago. Please check my blog before making such funny jokes.

    → Reply