Sereja's blog

Codeforces Round #167
By Sereja, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #167 will take place on Wednesday, February 13th at 19:30 MSK. This is my fourth Codeforces round and I hope not the last.

I'd like to thank Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values will be standard in both divisions.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over. Congratulations to div1 winners:
1). tmt514
2). tourist
3). scott_wu
4). rng_58
5). dreamoon_love_AA

and div2 winners:
1). yefllower
2). Harlos
3). pseudopodia

You can view tutorial here.

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

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

Are you sure about this date : "Sunday, January 13th at 19:30 MSK"

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

Guys according to your date the contest has been completed... because your date Sunday, January 13th at 19:30 MSK is gone....

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

After 7 rounds, all the 3 digits of this round is strictly increasing :)

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

    Here 167 is a prime , 67 is a prime && 7 is a prime as well :D

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

scoring??

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

    they'd say if it was unusual (i mean it wasn't 500 1000 1500 2000 2500)

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

Rishat_Ibrahimov used #define long unsigned long long and that costed me a wrong challenge, shouldn't that be considered code obfuscation?

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

div 2 D,can it be solved w/o chinese remainder theorem(CRT).

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

    Let's sort all pairs. There can be equal ones, which can be now easily recognized. If there aren't — the answer is (n+m)!, obviously. But if there are, we should divide our (n+m)! by number of equal pairs (since 2! = 2; if there were equal triples, we might have divided by 6). Division goes using Fermat's little theorem since we're using modulo.

    Edit: forget about the theorem, those 2's are from factorials, as MohallaBoy noticed.

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

      What do you mean by (n+m)! ？Can you show some details?

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

        I'm very sorry about misinformation — only yesterday before resubmitting D I realised that I wrote incorrect part of solution here. Please disregard it :) There's an editorial for now.

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

    basically you to find values like (n! / (2) ^ k) % m You can do this by removing 2's in the numbers which are used for calculating factorials. and taking then modulo m.

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

      first recognize all equal pairs, then for each repetition of the x term we calculate (length)!, omitting a 2 for each pair earlier. Although im 100% sure this is the solution i didnt implement it well enough for pretests :(.

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

    When we calculate factorial let's just divide each factor by 2, if there is any pairs left. Even if we use chinese remainder theorem, we can't calculate modInverse of 2 if 2 is divider of our modulo.

    long f(long n) {
	long res = 1;
	for (int i = 2; i <= n; i++) {
		int k = i;
		while (k % 2 == 0 && badCount > 0) {
			badCount--;
			k /= 2;
		}
		res = (res * k) % MOD;
	}
	return res;
}

    The answer is integer so when we got our answer badCount == 0

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

any ideas for solving C Div 1 ??

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

    Edited : I was wrong !

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

    Randomly distribute horses in 2 parties. Now if each horse has at most 1 enemy in its party, this distribution is correct. Otherwise, there exists horse A in party 0 that is enemy with horses B and C in the same party. Now move horse A to party #1 and it'll have at most 1 enemy in its new party. To prove this solution works, just define an invariant as count of enemy pairs in same party. Observe that after each move, this invariant decreases and hence our procedure is finite.

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

      How do you prove that if this method fails to find a partition, then a partition is impossible?

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

        Actually, when our invariant decreases at each step, it'll eventually reach 0 which means we are left with a correct distribution of horses in 2 parties. Possible partition always exists and it may not be unique but our algorithm guarantees to find one :-)

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

          Sorry for being picky but I think it's variant, not invariant.

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

            You're right. Thanks for pointing this out. Topic of this problem in Combinatorics is invariants and that's why I confused them :D

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

            I think it is called monovariant.

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

      Imagine, that all the horses are in part 0. According to your alrorithm, firstly we move horse 1 to part 1 (enemies 2,4,5). Then we move horse 2 to part 1 (enemies 3,5). Also we move horse 3 (enemies 4,6). Horse 2 now has 2 enemies (1,3) in its part. So, it doesn't work. Maybe I've misunderstood you, so please, can anybody explain me the correct solution of this problem?

      UPD: All right, I understood you. But it was not easy to push it through TL (3126714). Maybe it's because of Java. Is that an optimal solution?

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

        Complexity is O(m) and the idea behind this solution comes from a known graph problem. So I reckon this solution is optimal.

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

Sorry for tourist. How fast he was. But even this didn't help him to pass Pretest 0 ( Compilation ). 3123727 and 3123677 :)

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

:S DIV 2.B: Any one have an idea that why 3122613 has wrong answer on pretest #8?! I'm really sure that it should produce a correct answer. :S

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

    ans++ , seriously , it will TLE

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

    You shouldn't continue on a[i] == a[j] at line 40.

    And you use insertion sort which is O(n^2). I think it will timeout before finishing input.

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

DIV1 D is an original problem.

http://community.topcoder.com/stat?c=problem_solution&rd=14422&pm=11179&cr=10574855

TopCoder has its harder version.

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

one of the best contests ever..!!

well balanced on thinking and data structures...

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

wasn't anyone fool enough like me to use segment tree for div 2 C.

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

    well, i used BIT

    submission in queue...

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

    I used Fenwick Tree for that problem :)

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

      and fingers crossed.....:)

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

      I think you don't notice A[i] <= A[i+1] , I'm too) But I did it after writing void build(.... )))

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

        But even if it wasn't A[i]<=A[i+1] you can create sequence B such that B[1]=A[1] and B[i]=max(B[i-1], A[i]), so this assumption wasn't really necessary ; p.

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

    No, you weren't :/ Segment tree consumed all of my time — I should have read D first...

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

    lol, i wanted to code it, but then i saw a number of acceptions for this task.

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

    I use segment tree, too. I've got some MLE after some TLE and finally I forgot to use long long.

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

    same here :) I got it Accepted and also I apologize to Segment tree for using it in this easy problem

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

      atleast u got AC,long long cost me WA....:(

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

    I was fool too :(

    I didn't notice that the stairs are sorted

    I also didn't notice that boxes fall from the left until I coded it

    anyway I was fooler because my code was fail on test 45 because of overflow :(

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

It looks like the only difference in kissbuaa's and xiaodao's 2000s is the link in the beginning.. ..which is pointing to the same solution, yep. http://mirror.codeforces.com/contest/273/submission/3115085

http://mirror.codeforces.com/contest/273/submission/3114783

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

I have seen Div 1 C problem in Soviet math olympiad in 1979. This problem is "Proof that there always exists answers."

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

I've accepted problem C Div 2 at 1:29:22 ( Only 30 seconds untill the end of contest) ! I wonder if it was a record!?

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

How to get test case data on which our program has failed.

Since test input is large so It is showing only part of it.

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

    i was about to ask the same question !!!!

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

      it's not possible in CF :)

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

    An untidy way.. but if u really really need it you can make a hack.. Just print say 20 tokens once (or whatever size fits in the screen), then next 20 and so on..

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

76 contests and 18 months of ups and downs and finally I get to taste Division 1 in Codeforces, the place where I started online programming.. May be small thing for others but it means a lot lot to me because this is where I started from.. Sometimes getting close and then falling back and sometimes no where near to the horizon..Yes... Now I can proudly say that I am Div 1 in codeforces and topcoder together .. I dont know how long I am going to stay here but just being here is a great feeling... :) I hope I will never see Div 2 again.. Thanks to the author Sereja and Egor as always for CHelper

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

Gotta thank Sereja for the best contest in my whole life. Couldn't be better than this for me! :D

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

    It's because You became candidate master and solve five problems?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it
      • A contest that was based on Combinatorics and problem solving skills and didn't need hard and famous algorithms to be implemented. A brain challenging one.
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Well if You can solve C segment tree with updating on segments, it doesn't seem so simple. And if You solve D in few minutes to the end, it doesn't seem so simple too.

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

I did problem D in div2 carelessly and WA for 4 times in the contest. At last I only got 880 for this problem... But my rank seems OK...

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

    Ignore it, I didn't understand you.

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

    The same to you. I solved the problem D 5 minutes before contest just because of my carelessness.

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

what happened to your tutorial link?

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

    The tutorial is written in Russian, it hasn't been translated now. Only Russian vision is visible... So just wait them to translate...

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

http://www.codeforces.com/contest/272/submission/3128898

i don't understand the fail of my solution ?

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

    As you use C but not C99 you must declare i and j before the loop:

    int i;
for (i=1;...)
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give me a small test case where my submission fails. Thanx in advance

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

        There is a problem:

        int cnt = 0;
...
nans *= ((cnt*(cnt-1))/2);

        cnt can be equal to 105, so overflow will happen.

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

By python, I can not solve C in Div I! If anyone know, please post it!

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

    The input is n<=3*10^5, m <= 9*10^5, about 10^7. It's just too large for python. My C++ solution cost 375ms and my python solutions are always 10 times slower. So I guess python need about 4 seconds for each test case.

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

      yes, I think so. I also meet this issue. I implement C++ and python with the same algorithm. The C++ code is accepted in 500ms, but the python one is not.

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

        can you explain about the second argument in your change function? Your solution is recursive. I can convert it to non-recursive version if I understand the trick.

        → Reply