MikeMirzayanov's blog

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

Welcome to 2016-2017 CT S03E09: Codeforces Trainings Season 3 Episode 9. The training duration is 5 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!

Visit Codeforces::Gym to find the contest and register.

We are planning to start on November 9, 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!

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

Comments Comments (25)
| Write comment?
»
8 years ago, # |
  Vote: I like it +77 Vote: I do not like it

In problem M in test 8 we have following strings in input

b+b=156820
f+f=-189258

Why don't we know answer for query

b+f

?

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

    Maybe, judge's solution misses a case. I just exclude cases when two variables are independent to get AC.

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

Sorry, haven't seen vintage_Vlad_Makeev's comment

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

How to solve G? (The Queens one)

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

    Probably, the right decision was to bruteforce answers for small n and to find the formula on oeis.org.

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

      In fact the first 5 cases are enough, and n =4,5 are given while n<=3 is trivial (answer is 0)

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

        How to solve it without using external resources?

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

How to solve B, I and j?

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

    I — O(n^3logn) passes. Iterate the points of the first triangle and calculate the count of each triple of distances. Std::map got TL verdict, so I used std::sort to do that.

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

    Problem J you can you gaussian elimination, you can solve http://www.spoj.com/problems/XMAX/ to understand it

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

      How can I find the number of subsequence of maximum sum and the sequence using Gaussian Elimination?

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

        You can store the numbers whose xor equal to the answer by vector and find the set that xor equal to the answer. To find the number of subsequence, you just count the number of 0 after using Gaussian Elimination, Suppose it is M. If you xor the answer with any subset whose xor sum is 0, it doesn't affect the maximum xor sum, so the answer is 2^M

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

    Ignore the comment about Gaussian Elimination above. Here's a link to the right algorithm to solve this: Link

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

      It seem like the link is missing solution for this problem. Can you re-update this ?

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

I just cant get it? Why neither solution nor code available for Training contest ??? :(((

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

what is the solution procedure of Problem N(Cut Tiles).

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

How to solve problem B?

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

Could anyone tell me how to solve problem E? Thanks in advance

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

Do you have editorial this contest?

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

How to solve C?

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

How to solve D?

→ Reply