MikeMirzayanov's blog

2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1
By MikeMirzayanov, 10 years ago, translation, In English

Welcome to 2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1 (NEERC 99 + misc). 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!

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
  • +69
  • Vote: I do not like it

Comments Comments (74)
| Write comment?
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Haha, I like this pic! The end of evolution of human is programmer :)

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

    There's a lot of funny ones on the Internet:

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

    This is very true, because purpose of humanity existence is creating AI which can surpass human brain. Just like the purpose of previous evolution was to create human brain. After we create AI which surpasses human brain we will not be needed anymore. We are just a tool in Universe's quest of self-recognition and self-understanding.

    Under this paradigm (not mine, loosely citing David Deutsch, if you've heard about him) the picture is very true — it basically gives the full story of human being — from emerging as smart monkey to finish as creator of new artificial life.

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

    If you extrapolate the picture, it would seem like the next stage of evolution(artificially selected) is physically fusing with the machine. Genetic alteration is another possibility.

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

Whats the Idea of problem G — Highway ?

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

    Minimum spanning tree. O(N2) passes comfortably.

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

      how O(N^2) passes? there are 100000 cities.

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

      How'd you do an O(N2) MST? Shouldn't it be O(n2 * log(n))?

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

        No, you don't need to use a priority queue on edges with dense graphs. It's even simpler than .

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

          I still don't get it. I can't think about anything better than O(N3) or O(N2) with O(N2) memory.

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

            It's Jarník-Prim's algorithm, but you keep the shortest distances from the so far constructed MST (from its vertices) to all other vertices in one array. When adding the next vertex, you're picking the one with the cheapest distance and updating the minimum distances to all vertices.

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

              Yeah, that's what I was trying to implement, but I couldn't come up with an implementation without O(n^2) bool adjacency matrix to store if there was an edge between two nodes in the original graph. Turns out that using a set and checking it in O(log(m)) is enough. Final complexity: O(N2 * log(M))

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

                In this case, you implicitly know all but M edges (Euclidean distance) and you can store these M in an adjacency matrix + remember the vertex from which the cheapest edge went to each vertex. See my code.

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

                  Damn, so simple... PS: Nice template, lol

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

        Don't use a heap to extract-min, extract-min in linear time using a vector.

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

Can someone provide a link to solutions or explain how to solve H and G? Thanks!

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

    G: see above

    H: sort and greedy, the constraints allow an easy solution in instead of pure .

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

      Why O(104N + NlogN) work ....T_T I thought it should be a O(NlogN) solution...

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

        Why wouldn't it work? N ≤ 1000 and it's slightly easier to code.

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

          N <= 1000 ?... N <= 10000!

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

            No, 1 ≤ K, N ≤ 1000 in my problem statement.

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

              N <= 10000 in the gym... I thought the data must be enhanced...

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

                No, always N ≤ 1000 for me. Are you sure you're looking at the right problem? It's H, Billboards.

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

                  Haha, please forgive me ...

                  Anyway ... I thought there must be a O(nlogn) solution base on voronoi-diagram ...

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

    For problem H

    I had an N*(log(20000)^2) solution.

    You can sort the intervals by their end points and then for each interval check how many points inside it are already covered ... If the count of already covered points is sufficient(>=k), then do nothing ... else u need to start covering new points inside the interval from its end ... You can use binary search and segment tree to get this algorithm to work quickly.

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

      Plus size S of output to the complexity, which gives a different bound using a simpler simulation of the greedy: if the coordinates from the input are large, or if they're small (which is the case here).

      In fact, when you need to print the output, there's no point in using segtrees or whatever.

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

On problem K, with this testdata

7
aa
aa
aaaa
aaaa
aaaaaaaa
aaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa

Why is this not valid ? 


1.tab      ("aa")
2.type 'a' ("aaa")
3.type 'a' ("aaaa")
4.tab      ("aaaaaaaa")
5.type 'a' ("aaaaaaaaa")
6.tab      ("aaaaaaaaaaaa")
7.type 'a' ("aaaaaaaaaaaaa")
8.enter
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think after 3rd tab you will get aaaa as completition not aaaaaaaa.

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

      aww thanks! forget about that one :|

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

    "aaaa" is a prefix of "aaaa" so on step 4 you will get "aaaa" again and not "aaaaaaaa".

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

    When you press tab with "aaaa", you won't get "aaaaaaaa". The string will remain exactly the same ("aaaa").

    P.S. Holy shit, why are people typing so fast? :(

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

Can someone tell the approach for A — Divisibility? Thanks

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

    Simple DP on achievable modulos.

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

      thanks,trying again to solve it

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

      not getting the DP, can u tell? thnx!

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

        What modulos can you achieve using all possible expressions with the first k numbers?

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

          how to form all possible combinations of expressions,iterating would be time consuming.

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

            That's why it's dynamic programming. Think about what I wrote — anyone that knows what DP is should be able to solve it with those hints.

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

      is this possible with simple recursion?

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

        If you mean backtrack, then probably not.

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

          I mean binary recursion on sum +,- next element, exiting from recursion if (sum mod K) equals zero.

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

            Then NO. Definitely not.

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

can somebody explain the approach of K ... is it trie+dp ??

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

    While you could use trie, there's no need for it. A simple DP using substr() checks is sufficient.

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

      thnx a lot ...

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

      are the prefixes proper or any prefix ... i mean say have already typed "an" and one of my words contain "an" so will my 1 tab be wasted on this .

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

        Read the comments here and you'll find out.

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

      what's the data of the 18th testcase?I got wrong on it.But I can't find any error.

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

code

whats wrong with my solution getting TLE. please help. Thank you.

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

Where do we find editorials for the Training Season2 episode 1. I am new to cf, can anyone help me out with this :| Thanks a lot!

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

Ask for kind help: for the task F, according to the rules, could we uniquely determine the output of the dictionary? (as the description does not give detailed explanation, while "sample input and output" instead.)

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

tourist is unbeatable. No matter if we start individually or as a team.

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

Why can't I see code from others people?

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

    Because it's training competition. You can't see code of any problem from other participants, if you haven't solved this problem yourself.

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

My codes:

A B C D E F G H I J K L

(upd: B and J added)

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

    То что надо, спасибо огромное тебе добрый человек.

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

Any hint for L?

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

    Sort cows by sum of weight and strength. This is an optimal order.

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

Please publish the editorials.After trying if unable to solve we are left with no solution but to have a look at editorials.

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

Same code but choosing Java 7 instead of Java 8 made it pass (well under time limit). What's going on?!

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

    I had AC instead of TLE by switching Java version for two times in official CF Rounds. As for my experience, Java 8 seems to be faster with Objects and standard data structures, while seventh version is better when you work with primitives/recursion.

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

Can anybody explain statement of task D?

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

What is the meaning of Ghost Participant ?

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

Whats the Idea of problem C? "Expression"

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

    Just stacking the same type of expression (using the carry bit of the i least significant bits and the i + 1-st least significant bit) N times. You can see which expression it is from the sample.

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

      How could I see the test cases?

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

        Solve the problem, then you'll be able to. Sometimes.

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

          I was wrong on test 9 of prob d, can I see the test case then? Thanks!

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

            Solve the problem, then you'll be able to. Sometimes.

            (Also, I can't see the tests now. That's why I'm saying "sometimes".)

            → Reply