MikeMirzayanov's blog

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

Welcome to 2014-2015 CT S02E05: Codeforces Trainings Season 2 Episode 5 - 2009-2010 ACM-ICPC, NEERC, Southern Subregional Contest. 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
  • +78
  • Vote: I do not like it

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

Love that graphic. :)

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

contest is for Practice not for cheating !

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

It sounds great. Thanks for this.

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

I feel like a confused zombie during contests, hopefully this training session brings me back to life.

Do you guys feel its wise to migrate from Java to C++ ? anything to be aware of before shooting myself in the foot?

That pic above there describes me too well xD

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

    I don't think that it's that big of a deal for contests. On the other hand, STL may be really useful sometimes.

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

    Well, from my expirience you can write less code using C++ as opposite to Java, and C++ is much faster than Java. I myself migrated from Java to C++. And I find C++ very pretty after using Java!

    But you don't have to migrate from Java to C++ to get successful in contests like ACM ICPC. Moreover, Java is really good because of having built-in long arithmetics. Btw it's much easier to handle bugs with Java, because it simply doesn't allow your program to compile if you have commited some minor mistakes. You can spend a lot of time trying to find annoying typo in your code, since it most probably will compile.

    It doesn't really matter wether you use Java or C++, because it's just an instrument. What matters is your skills and knowledge, so you better use a language, which seems to fit you better.

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

When is it?

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

We call it a 'cold' joke in Chinese.

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

    We call it cold joke too in Turkish. Actually, it's also called cold joke in English.

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

I can't download the problem statements. Can anyone give a link?

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

Can't find mistake in Perl "G. Plural Form of Nouns" solution: submission — 8159457, ideone — http://ideone.com/v1Occf

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

    When I run this on the sample, I get:

    contests
heroes
ladies
s

    And the last line is missing the newline character. It seems that Perl interprets newline as line separator instead of final character for each line ("lady\n" vs. "lady", "").

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

      Thanks, you shown me a mistake, I forgot newline. I "disabled" line separator, and my mistake — I asked last regex to find and insert "s" in between "not s" and ("\n" OR end_of_string), so regex inserted "s" between "\n" (!="s") and end_of_string.

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

How do you solve problem E(Meetings)?

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

    hello

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

    IMHO, most interesting thing is to find out what test case #3 checks for. First, I thought it was because of problem misunderstanding, But so much time have already been lost for rereading((

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

How to solve problem F?

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

    I wrote DP optimized by segment tree. I think there is a better solution.

    Code

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

      Indeed, I think I found an O(n) solution. It's based on the on the same DP aproach, but it optimizes finding the maximas. Namely, unlike in the LIS problem, where it has been proven to be a bound of Omega(nlogn), here we can do better because the maximas we want are quite particular. In fact, we have maximas of the kind Max(All elements of a vector except for 2 of them, the ones which have the absolute difference 1 from v[i]). Because of this, we may mantain a data structure witch supports adding a new element and deleting the smallest one (in order to mantain the 3 largest elements of the vector => One of them will always be the maximum in our vector). This is O(n) with a pretty big constant, so it's comparable with the segment tree solutions, but still O(n).

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

        Thank you. It's the solution I've been looking for.

        It works 31 milliseconds, so I don't think that constant is such big.

        Here is the code

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

    Let's denote by dp[i] = the length of the longest subsequence that fits the properties in the problem statement, ending by element i. You may easily calculate this in O(n^2), but this won't fit into the time limit. In order to optimize this aproach, you will need to use 2 Fenwick trees and a usual array (or just one single segment tree). Let's denote by x[i] = the largest dp[j] already calculated with it's v[j] = i (i.e. the largest dp with a fixed value), then the first Fenwick tree will mantain maxima on segments of the form [1,i] from x, the second one on segments of the form [i,n] and the usual array will be the vector x. Hope this helps.

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

    thanks!

    this is a really nice idea.

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

    My idea is as follows.

    Since all numbers are between 0 and 10^6, we can store the length of the longest valid sub-sequence ending with each number. We can store those values linked with their numbers in a max-heap. We begin to traverse the given array. For every number x that we encounter, we erase the values for x-1 and x+1 from the max-heap. Then we update the length of the longest sub-sequence ending with x. After that we put values for x+1 and x-1 back in the max-heap. Note that since the length of the original string is at most 10^5, max-heap's size won't be greater than 10^5.

    Here is the code: http://pastebin.com/yRqtUSxV I have used STL set for the heap.

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

How to solve C and D?

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

    D: I didn't succeed with Trie, it gives ML

    C: I'm afraid map+dsu+dfs will not work in 0.5 s (compress the destinations with map, find all connectivity components, mark some of them as "cycled" and find the wire that should burn in every "cycled" component)

    That's all I can say.

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

    D was a typical cycle-finding problem. One can use the hare and the tortoise algorithm to solve it. You can find it on Wikipedia. It is a simple algorithm with tons of applications.

    For C, Ralor's idea is pretty close to the solution. One needs to find the maximum spanning tree for the given graph.

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

    C explanation -> Find mst using kruskal

    But edges go in descending order of reliability[since we dont want minimal reliability edges to be included in ans]

    And if same reliability, in descending order by cost[since we want higher cost]

    Now insertion order is just the reverse of this

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

Can't find my mistake written in Perl in problem "A. Walking around Berhattan" (WA #6): submission — 8159769, ideone — http://ideone.com/wN8bcY . Tried some corner cases, but seemed fine.

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

    test_
    1 1
    4
    MRMRMRM
    right answer is 10, and your answer is 7

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

      Why 10, not 7? 4 + (4 div 2) + (2 div 2) = 7

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

        You should only one time do div 2 rounded down for each block, and 10 = 4 + (4 div 2) + (4 div 2) + (4 div 2)

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

          Ok, thank you. I dislike read statements :(

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

        4 + 2 + 2 + 2, each field is divided by 2 at most once.

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

how do solve the problem B??? :) !

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

    B can be solved by backtracking, Precompute if you can achieve a sum S using L elements if the elements {a1, a2, .. } (can be represented using a mask) are available.

    Then use backtracking to fill each of the empty cells, and keep checking after each assignment whether the assignment is possible or not.

    code

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

what's the trick about K?

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

    No tricks. Just a recursion, column by column.

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

      can you give me some test case?

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

      Could someone help me find what's wrong with my code? http://pastebin.com/C0eJuX1k

      I get RTE on test case 19. Seems like I'm having pos>size of the word at some point (cause checking for that turns the RTE in WA :P). But it only calls parse if all the words have the same sequence of '*'s and '#'s (only) up to that point. So, since the strings are guaranteed to have at least one non '*' or '#' character, this shouldn't be a problem :(

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

        Your program throws runtime error on a test with single line. Because it tries to get substring from negative index. Line #27.

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

          yeah, AC now. spent hours trying to figure out this :'( lol

          thanks!

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

Can anybody find a mistake in haskell code for task G: ideone, submission ?

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

    You should read from "input.txt" not from stdin.

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

      Thank you. I still cannot find where files are mentioned. Is it because of the haskell language?

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

How to solve "D. Sequence analysis". I just use bin search for finding "second occurence of the first repeatable member". And check this in O(2e7) time. So, it work in O(2e7*log(2e7)) time. And i get TLE on 8 test.

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

    Look at Floyd's cycle finding algorithm or Hare and the tortoise algorithm. It will work in O(n)

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

      how did you solved it with Floyd? I did it but got TLE, here is my code: http://pastebin.com/XhZa3r77

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

        code

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

          thanks! I thought of exiting the first loop when iterations were bigger, but I still don't get it why it works. Isn't it possible for the algorithm to jump some comparisons and go beyond the 2e7 limit, even if it exists a solution < 2e7?

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

how to solve E?

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

How to solve H? Are there some mathematical formulas?

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

    as x0 = x1 = ... = xi, and you know x0 = a0 + b0 and a0 is fixed in s * p / 100, you only need to find the right b0. you can do that using binary search for values between 0 and s and checking if it needs more or less months than m for this b0. this checking can be done in O(m): at the end of m months, check if there's still some debt left. here is my code: http://pastebin.com/Va8yCuGH

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

      I did the same thing, but with float I got TLE. Switched to double and now it works like a charm... Thank you

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

Why my solution to problem H always WA on test 10?8237424

→ Reply