pkhaustov's blog

Codeforces Round #242 (Div. 2)
By pkhaustov, 11 years ago, translation, In English

Hi, everyone!

Regular Codeforces round #242 for participants from the second division will take place on 25 April, 11:00 MSK. Participants from the first division are able to participate out of the competition.

The contest is prepared by programmers from Tomsk Polytechnic University: Pavel Khaustov (pkhaustov), Olesya Golub (Taube), Nickolay Kuzivanov (Carups), Dmitry Savvinov (Dsavvinov), Alexey Vetrov (noxwell).

Special thanks to Vladimir Chalyshev (cmd) and Alexey Dergunov (dalex) for their impact.

Also, thanks to Codeforces team and, especially, to Gerald Agapov (Gerald) and Maria Belova (Delinur).

Points distribution: 500-1000-1500-2500-3000

Good luck!

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

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

Why are there so many contests at 3 AM US time. :(

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

    In china,we usually play it at 23:00!Sometime,we can't help falling asleep at that time.

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

I think most of the contestants aren't comfortable with the time of the contest start , it's been like this with coder-strike too

Please reconsider this in the next contests .

And many thanks to the authors

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

    I am sorry to hear that you feel uncomfortable with the time.

    However, I like the time very much :) It is 15:00 in Hong Kong (UTC+8), but I will be at school as it is Friday... The usual time of contest will be at 23:00 in Hong Kong and I can't help falling asleep at that time.

    I hope that the time could be modified so as to cater most people's need.

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

    In Romania the contest starts at 10AM, but I have school then. Hope that the old hour(6PM in Romania) will be used more in the future :D

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

Div1 users won't be rated? Only div2 users will be rated with a separated ranking?

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

Am I the only guy who read pkhaustov as Khaustov Patel? :P

PS: Khaustov Patel is a typical Indian name.

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

This time is ok, if it's not friday. Friday is Jummah day(a special day for the muslims). And in Bangladesh, the time when contest will be started, is the jumma time. :(

So going to miss this contest... :'(

*** If anyone wants to know about Jummah, can check it here

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

I'm sorry to to hear that many people feel uncomfortable with the time.

However, it's obvious that the time can't make all contestants happy and some people participate the contest at midnight.

The usual time will be at 23:30 in Beijing.When the contest ends,it will be at 1:30am.And I think it's more uncomfortable for Japanese and other east Asian countries' contestants. But there are still many east Asian countries' contestants to participate the contest. I think the reason is that we love coding and enjoy the contests. But I have to say the usual time of the contest is better for most contestants. Hope we can understand author and understand each other.

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

I am happy with this time. It will be 3 AM EST here in FL, US but it is a good time to write code relaxed, lol. The usual time is complicated (11:30 AM EST) for me because either I am working and I can't focus very well or I am at home where my daughter doesn't stop playing with me while I am solving the problems. As always, enjoy the contest, GL & HF!!!

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

    Same point of view here. I prefer midnight contests to daytime contests, too. Fortunately, regular Codeforces time favors me well (11.30pm). Typical coders don't go to bed early, right? :P

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

      Yes. At the end, coders don't go to sleep early. I would like to participate in more contests after midnight.

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

I prefer 3 AM to 11:30 AM because I'm more likely to be awake at the former time ;)

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

Our mid-term exam is about to finish today morning, so just be able to take part in... Sorry to hear that it' s an uncomfortable time for others. (Start at China Standard Time 15:00)

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

Unfortunately cannot participate in the contest cause its jummah time .

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

30 mins to start the contest .... It will be a good contest as always . wish you luck all :)

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

How did you solve Div 2 C?

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

    I received time limit on pretest 12.

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

      What did you try? Bruteforce will fail obviously.

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

    q[i]=p[i]^(i%1)^(i%2)^...^(i%n) Q = q[1]^q[2]^...^q[n] = (p[1]^...^p[n]) ^ (^ for i=1..n for k=1..n (i%k)) = (p[1]^...^p[n]) ^ (^ for k=1..n for i=1..n (i%k)). Let P=p[1]^...^p[n]. So, Q = P ^ (^ for k=1..n for i=1..n (i%k)). Now we have to calculate these xors for all k: (^ for i=1..n (i%k)). ^ for i=1..n (i%k) = 0^1^2^...^(k-1) ^ 0^1^2^...^(k-1) ^ ... ^ 0^1^2^...^(k-1) [(n/k) times] ^ 0^1^2...^(n%k) = ((n/k)%2)*(0^1^2^...^(k-1)) ^ (0^1^2...^(n%k)). We can pre-calculate all xor sums like (0^1^2^...^(k-1)). The rest is obvious.

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

      Also there is a formula for prefix xors 0 ^ 1 ^ .... ^ k:

      int xorUpToK(int k) {
	switch (k % 4) {
		case 0: return k;
		case 1: return 1;
		case 2: return k + 1;
		case 3: return 0;
	}
}
      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you explain this formula?

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

          This is a nice formula for long values of k . To prove it you take

          F(3) = 0 ^ 1 ^ 2 ^ 3 = 0

          because in binary

          0000 ^ 0001 ^ 0010 ^ 0011 = 0000

          and operating BIT for BIT

          F( 7 ) = F( 3 ) ^ 0100 ^ 0101 ^0110 ^ 0111 = 0000

          F( 7 ) = F( 3 ) ^ (01)00 ^ (01)01 ^(01)10 ^ (01)11 = 0000

          We can note that () repeats four times , and four is even then (x)^(x)^(x)^(x) = 0 is ever zero

          But in this problem is not necesarry because we can precalculate al values <= 10^6

          A problem that you really need this formula.

          Link to problem

          PSDATA: you need know nim numbers before solve Industrial Nim.

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

            Awesome, thanks! I know this problem just needed a simple precomputation, but it's still nice to understand this formula.

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

          I think that most coders have checked this post

          But without this, you can also do a precomputation :D

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

      could you please format your comment to make it more readable. thanks!

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

    We know that xor is asociative then we can reagrup de expression as p1 xor p2 .... xor p3 * E where E is a new expression and again reagruping :

    E = (1 mod 1 xor 2 mod2 ... n mod1 ) xor (1 mod 2 xor 2 mod 2 ... n mod2 ) ....

    Then we can get F = 1 mod i xor 2 mod i xor .... n mod i efficiently

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

      Exactly, but what after that? I understood that part, but I could not form a relation afterwards.

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

        We can get

        F = 1 mod i xor 2 mod i xor .... n mod i

        if we take every package of size i then we have

        F = [ 1 mod i xor 2 mod i xor .... i mod i ]

        xor [ (i + 1) mod i xor (i+2) mod i .. (2*i) mod i ] ...

        then

        F = [ 1 mod i xor 2 mod i xor .... i mod i ] xor [ 1 mod i xor 2 mod i xor .... i mod i ]......

        Finally [ ] repeats q = n/i and if q is even there [ ] = 0 else [] = [ 1 mod i xor 2 mod i xor .... i mod i ] and we can consider r = n%i too.

        for solve G = [ 1 mod i xor 2 mod i xor .... i mod i ] we can see that is equal to

        G = [ 1 xor 2 xor .... i ]

        And everthing depends only of G we can precalcalculate with a array.

        My Solution

        Sorry for my bad english.

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

    I have formed an matrix on a paper of n x n rows represent n and cols mod i

    - 0 1 1 1 1 ... 1
- 0 0 2 2 2 ... 2
- 0 1 0 3 3 ... 3
- 0 0 1 0 4 ... 4

    as you can see, every column is a cycle of length i, and you can cancel (n/i)/2 cycles, because x ^ x = 0, obviously you will not always have cycles that pairs, so you need the xor of the parts that can't be paired, lets call it rest[i] finally with a for i do ans ^= p[i] ^ rest[i]

    my submission 6467752

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

A contest with no successful hacking attempt!

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

Am I the only person who are confused with problem E's sample case?

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

Can anyone tell me why my solution gave WA ? I did precomputation of XORs and my complexity is also good. 6468572

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

    can you at least explain a bit your idea? and ull was not necessary

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

    You had the right idea of precalculating xors, but what you're doing on each iteration is not right. Try this simple test:

    4
0 0 0 0

    The answer should be 2.

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

      Yeah . Silly mistake on my part , I took mod as simply the difference and it failed on indices like 4%2 and 4%4. .

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

what was the idea of D?

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

    Bruteforce and TernarySearch , my friend.

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

      Integer ternary search Oo

      You crazy person...

      P.S. I thought, we can't avoid using set in this problem. Such a surprise.

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

      This solution is wrong. Ternary search doesn't work here.

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

        6469423

        Well, but his solution is AC.

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

          And how do you think what does it mean? :)

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

            Weak tests, round should be unrated :Ъ

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

              Not really, I believe his solution is correct.

              His ternary search function is a function of the absolute difference between both times, which is clearly a bitonic function in this problem.

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

        Hey man i think that you are wrong , Ternary search works because my function f is crecient then g = abs( f — t ) is like a parabola then i need to calculate the minimum.

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

          You fix left, right and top borders of the track and then find the bottom border by binary search. Let's see what bottom borders we can create.
          What happens if all odd rows are decreasing (a[i][j] > a[i][j+1]) and all even rows are increasing (a[i][j] < a[i][j+1])?

          If we consider the times needed to go through the parts of track built at these rows, they will be like {d*tUp, d*tDown, d*tUp, d*tDown, ...} where d is the width of the track and tUp and tDown are numbers from the input. It's not a crescent sequence, is it? Of course we also have increasing left and right parts, but they cannot affect so much as the bottom part affects the function (e.g. if the width is very large).

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

            Oh nice counterExample , maybe in random cases my solution works well:)

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

            I thought this during the contest, so I went for the O(N^4) solution :(

            Still, in the editorial (http://codeforces.net/blog/entry/11944) the author says his solution is O(N^3 * logN).

            As far as I've seen, people have used n-ary search to do this, but there are a lot of cases where that would fail, cause you can't guarantee that it's increasing or decreasing at any point.

            Take dalex' example with odd decreasing/even increasing rows, you can actually have any random configuration of rows that are all increasing or decreasing and this would make any n-ary search solution fail, as far as I can understand.

            So, any ideas of how to achieve the O(N^3 * log N) solution with any other method? (Or is there something that I'm missing and a n-ary search actually works?)

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

          champero detected !! :P, Nice problem.

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

Any editorial?

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

Could anyone help figure out what the wrong is in my two solution of Problem C? 6466959 and 6468449

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

In Problem C, upper limit of 'p' was 2 x 10**9. However, solutions that took 'p' as int passed.

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

    the upper limit of int is 2147483647, which is more than 2e9. so ofcourse it will pass!

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

I am wondering if this algorithm is correct or not. http://codeforces.net/contest/424/submission/6470517 He enums all the point on the top-left , and use trinary-search twice to find the point on the bottom-right. In my view , this solution is incorrect. Just can not find a data challenge this code ? Thanks

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

Could anyone share your idea of problem D? I was confused with the problem for more than one hour, sticking to the O(n^4) algorithm and cannot find a way to optimize it....

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

Hello.

Can anyone tell me why submission 6465131 gets Compilation Error on Codeforces, as it compiled perfectly on my local machine ( Linux GCC 4.8.2, though I doubt there are any great differences between this and 4.7) ? Link: http://codeforces.net/contest/424/submission/6465131

Thanks.

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

    Compiler thinks that distance is STL function to count distance between two iterators, but not yours. You haven't Compilation Error on your local machine because your local machine uses C++11 mode. If you want to use C++11 on Codeforces, you should choose "GNU C++0x 4" as language.

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

why is 3 1 4 6 not a solution to sample of D?

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

Problem D was very misleading... During the contest, some people got Accepted with a O(n^4) algorithm, while most people thought that the required complexity was O(n^3) :P

→ Reply