MikeMirzayanov's blog

2016-2017 CT S03E03: Codeforces Trainings Season 3 Episode 3
By MikeMirzayanov, history, 8 years ago, In English

Welcome to 2016-2017 CT S03E03: Codeforces Trainings Season 3 Episode 3 - 2007-2008 ACM-ICPC, Central European Regional Contest 2007 (CERC 07). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

We are planning to start on September, 21, 2016 13:10 (UTC).

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

Tags gym
  • Vote: I like it
  • +104
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

Typo in title: S03E02 (should be S03E03)

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

available*

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

how to register for it?

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

What's wrong with the problems?

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

Please, help me to find a max sum of test cases in problem — A?

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

How to solve Problem Weird Numbers ?

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

    I'll explain my solution, which I'm pretty sure is not optimal.

    • It's clear that with a negative base, odd positions will be negative and even positions will be positive. So all numbers in base  - b can be expressed as e + o where e is some number in base b with all zeroes in odd positions and o is some number in base b with all zeroes in even positions.
    • So what I did was generate all said numbers up to 109 and store them in E[b] and O[b], where b is the base. Then for every query [b, x] (that is express number x in base  - b), I iterate over all e in E[b] and check if e - x is in O[b]. If it is, I just have to print e + o in base b.
    • The other type of queries is trivial, is just processing a number in base  - b.
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I'll explain my solution, which I think is optimal.

    Its almost the same as converting in positive bases. Lets convert N from base 10 to base b (b < 0):

    N = a0·b0 + a1·b1 + ... + an·bn

    note that , so (N - a0) / b = a1·b0 + ... + an·bn - 1 and we can repeat recursively.

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

Anybody knows where can I find the editorial ( :

Thanks

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

Why did answer "4 2 3 4" fail on the second sample? (Problem S. Robotic Sort)

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

    It is said in statement: their mutual order must be preserved: the one that was given first in the initial order must be placed before the others in the final order too. So you should also consider the INITIAL indexes of elements.

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

What is solution for problem C(Phone Cell)? We thought that problen can be solved by geometric invertion, but we don't know, how we can use it.

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

How to solve B? :(

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

    Consider all the tiles of row 1. There are m tiles and 2^m ways to select a subset of them to be flipped. Notice that this uniquely determines all the other tiles which needs to be flipped to clear the billboard afterwards.

    Consider cell(2,1). If cell(1,1) is on, then cell(2,1) must be flipped. And if (1,1) is off, (2,1) should not be flipped. Because after flipping (2,1), (1,1) is on and now there is no way to turn off (1,1) since the columns to be flipped in row 1 is fixed.

    Complexity: O(2^m * n * m)

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

      I used bitmask but it keeps giving me TLE on test 2, I submitted the same code on SPOJ(where time limit is 3.6sec) it got AC, How to get AC when time limit is 1sec using bitmask?

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

        You can optimize your solution with the bitwise operation! Complexity: O(2^m * n) Here is my solution

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

    Try all possibilities for the first row, after that it's easy to see which ones you should switch in the second row (the ones that are still black in the first row), then the same applies for the third row, etc..

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

    We actually solved it using systems of linear equations.

    Suppose aij is the number of times a tile at row i and column j gets swapped. First of all, aij ≤ 1. Then, for each position (i, j) we can get it's final color as (initial_colorij + aij + ai - 1, j + ai + 1, j + ai, j - 1 + ai, j + 1) mod 2.

    That gives as a system of equations with n·m equations and unknowns. Sure it's not as easy to code, but it gives better time asymptotic.

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

      The system of equations can have many solutions, how do you choose the one that minimizes the number of taps?

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

        Great question!

        It turns out, that number of free variables (meaning we can choose any value for them) is not that big (7 for 16x16 matrix). We can search over all possible values for this (at max 7) free values and find other unknowns, then choose one that minimises number of taps.

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

Can anyone explain the solution for Problem C?

→ Reply