Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 10 лет назад, По-русски

Добро пожаловать на 2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1 (NEERC 99 + misc). Продолжительность тренировки — 4 часа 30 минут. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.

Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!

Удачи!

  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How many problems are there gonna be?

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats the Idea of problem G — Highway ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Minimum spanning tree. O(N2) passes comfortably.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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))

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    G: see above

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    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? :(

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell the approach for A — Divisibility? Thanks

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

code

Whats wrong with my dp function? Plz help. Thank you,

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

code

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

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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!

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.)

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why can't I see code from others people?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Жалко что разбора нету. А его вообще кто нибудь делать будет?

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

My codes:

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

(upd: B and J added)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hint for L?

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can anybody explain statement of task D?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the meaning of Ghost Participant ?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats the Idea of problem C? "Expression"

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.