MikeMirzayanov's blog

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

Welcome to 2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2 - 2004-2005 Open Cup, Volga Grand Prix. 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 availible 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, 14, 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
  • +141
  • Vote: I do not like it

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

if editorials of season 1 were published or atleast the codes of other people are made visible then it would be quite helpful.. :) thank you.. :)

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

    editorials are available here

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

      where I can find editorials for I-J-K-L?

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

      can you share how can we find the editorials ?

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

        The questions for the last episode were from BAPC 2010. Just google BAPC 2010 and you'll find a link saying Outlines of the solution

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

          you mean all i need to do is to find out the source of the gym contest ?

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

            Yes. Also, in the last contest, if you see the questions PDF, it says BAPC 2010 on the top left corner.

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

      Are they the same problems?

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

how to a beginner can participate this season ?
thank you :)

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

    go to gym and click in register after the registration be enabled

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

Why does the title say "S03 E01", but the episode is Episode 02?

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

Wrong Ans on TestCase 104 20243522 isn't it more pathetic ? :p

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

Please reopen registration :(

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

Unrelated, but can I use the image in the post as my avatar?

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

Could you give more explanation about the question Fence. What does "if there are two red boards in the fence with the number of boards between them multiple to K" mean?

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

    You should find such i, j (i != j) that:

    1) a[i] is red

    2) a[j] is red

    3) distance between i and j is the number that can be divided by K

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

      So the distance between i = 2 and j = 3 is supposed to be 1 ?

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

        In this problem distance is the number of elements that are situated between i and j

        So distance between i = 2 and j = 3 is 0

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

Testcase 22 in H? :D

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

    any K

    11

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

      I don't understand, please clarify.

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

        if you have two Consecutive ones, then the distance between them is 0, and number 0 is a multiple of any k.

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

How to solve H?

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

    For all keep indices xmod that are 1's.

    Segment [l, r] is good, if l mod k = (r + 1) mod k.
    So we just need to check that there are exists modulo mod, such that xmod and xmod + 1 are both non-empty.

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

    Hint:

    Simplified the problem as : Find a subarray of an array whose sum is divided by given number K . If the sum of the numbers in the range [a, b] is divisible by K, then: (∑i=1 to a-1 arr[i]) % K = (∑i=1 to b arr[i]) % K

    Construct a hash-map which will store the cumulative sum of all the numbers thus far mod K.

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

How do you solve E?

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

Can someone tell how to solve I please?

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

    Solution for I.

    Claim: For i subsets, we can partition .

    Proof: Induct. i = 1 is trivial.

    Start with .

    Then, perform

    Then, set .

    It is not difficult to prove that and each T is sum free.

    This solves the problem, since

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

      can u please explain your solution in detail.

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

        http://pastebin.com/Ykmg7iWn

        Let me explain this solution in a better detail.

        First, let us reword the problem.

        Problem: Can we partition the set {1, 2, ... n} into 10 sum-free sets?

        (Note: Sum-Free Set is a set A such that if , .)

        Let us make the trivial observation — if {1, 2, ... n} can be partitioned, so can {1, 2, ... n - 1}.

        Now, we use the Claim above. Since , every n ≤ 25000 is okay.

        Therefore, construct the sets T_1 ~ T_10 inductively as described above and print which set a number is included in from 1 to n.

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

Well, it seems the fact that the graph isn't guaranteed to be connected makes C so much harder (adding edges carelessly to make it connected doesn't work). What was the expected solution?

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

    LOL. You need to connect components by leaves. So much harder.

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

    Each connected component can be compressed as a trees where nodes are biconnected components

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

Can problem B be solved in C++???

all the Accepted solutions were either in Python or Java, I know that it could be solved using the BigDecimal Class in Java, but is there anyway to solve it with C++???

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

Is there any editorial available for this round?

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

Can someone give me idea about G and H just getting TLE there

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

    For G Get locations for each value first. Then iterate over 1 ≤ i ≤ n, and j such that i|j and check if both numbers appear in the sequence. Since , this solution is .

    For L (OOPS) Control two arrays, for color blue and red. Let the number of blue fence be bs and red fence be rs. Clearly, we use min(bs, rs) fences of each color. Sort the two arrays and choose the largest ones. The solution runs in .

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

      Would you please explain the iteration for problem G ...... what do you mean by i|j????

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

        I think it means increment j += i.

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

          Nope it means j is divisible by i :)

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

      You mixed problem L and H :! Your soln for H is the soln for L

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

How to solve B & I ?

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

    B: Just iterate several times . This thing goes to really fast.

    I: Suppose, you know how to color N cells using just K colors. Then using K + 1 colors you can easily color 3 * N + 1 cells, like this:

    { old thing with K colors }{ N + 1 cells with new color }{ old thing with K colors }

    This will give 0110222220110 for 3 colors. Overall it allows you to color up to 29k cells with 10 colors.

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

      Could you explain your solution for problem B in detail ?

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

      Nice and simple explanation for problem I.

      I was far from this solution trying with binary operations and congruences, and I solved up to 3125 :(

      I wonder if there is a different approach.

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

      Can that B solution pass with C++ too?

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

        Apparently you need some king of long arithmetics here. Usually the best way in this case is to either use Java or Python.

        If you are brave enough and can write long arithmetics in c++ quick and bugless (and reasonably fast algos), then you are free to go and AC this problem in c++ =)

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

Why can't I see test cases?!

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

test 12 in A?

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

Can anybody share there approach to the problem I ??

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

problem k : wa on test 5 ? i dont know what did i miss ? can anyone help ?

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

i think its better to add the time limit to the statement for each problem.

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

When can we see the test cases ?

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

    Depends on how hard you train :D (you need to participate in 30 contests and have 1900+ rating)

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

test 3 in E?

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

Can anyone tell me how this solution for G is wrong ? Code

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

    You are only looking at pairs (i, 2 * i).

    I'm guessing that you looked at and thought that there exists a pair with (i, 2 * i) by Pigeonhole or something.

    However, just look at n = 5, k = 3 and 1, 4, 5.

    To solve the problem, you have to look for every (i, x * i) which takes

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

Can anyone give me ideas for solution of A or C?

In A, can you modify convex hull and do it?

In C, the graph should have a Hamiltonian cycle, that's all I could think of. How to add minimum edges to make it happen, I have no idea

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

In the light of the upcoming ACM contest I looked into the last year Moscow quarterfinal problems: http://codeforces.com/gym/100792

I wanted to peek at solutions of some problems, but I didn't find any editorials or sourcecodes. Here on cf sourcecodes and tests are also not shown. So I have two questions:

  1. Does anybody know where to find editorial/outlines for solution/sourecodes of someone's solutions?

  2. If no, am I allowed to write and publish the editorial myself (at least partially), or is it forbidden for some reasons?

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

    I think it's okay to create a blog where everyone contributes to make an editorial. They will not link it to the contest, but as a discussion, I think it's alright

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

Regarding problem H (The Fence), there is a missing test case that makes some solutions fail due to exceeding the time limit. I think you should add it and rejudge all solutions.

The test case can be generated by this C++ code:

#include <iostream>
using namespace std;
int main() {
  cout << 2 << endl;
  for (int i = 0; i < 50000; ++i)
    cout << "10";
  cout << endl;
}
→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there any official outlines for this contest? can't find them anywhere

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

Problem F was one of the least solved problems in the contest. I wonder why nobody has asked for a solution/hint yet. So let me do the honors. The statement is amazingly simple, but I haven't been able to make any headway on this. Any ideas in the right direction would be appreciated. :-)

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

How to solve K?

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

Someone please post their approach to problem K- Parquet ?

→ Reply