MikeMirzayanov's blog

By MikeMirzayanov, 10 years ago, translation, In English

Welcome to 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + 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
  • +68
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Why?

»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Isn't it better to move CF Round rather than Training Episode? Rounds are always on different days, while having Training Episodes on certain day would allow teams to include it to their regular trainings schedule.

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

    I also expected the CF round to be moved instead. Maybe it just has lower priority since it's Gym... and can be done in virtual participation anyway.

    And now I'm also curious why this got many downvotes in a short time.

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

    Considering the number of participants (CF Round 267: 4k7, last gym training: less than 400), we can clearly see why the training should be moved.

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

      I was not talking about the amount of the audience, was I?

      Those 4.7k would participate on any day of the week, because it's ok to have cf rounds on different days and it's not difficult to schedule a 2-hours round for a single person comparing with scheduling 5-hours contest for teams of three.

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

How is problem F solved ?

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

Anyone can help me find my mistake on J? Here's my code : http://pastebin.com/T5vuiMHG

I get WA on test 2, but I can't see the test data and I have no idea where could I be wrong (can't think of any test case).

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

Why can't I see other solutions after the end of contest?

»
10 years ago, # |
  Vote: I like it +52 Vote: I do not like it

The author of the problem A probably was angry with life at the moment of creating it...

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

    Hehe, you apparently don't have much experience with CTU Open. Nasty problems are relatively common there (which is normal considering there's a technical university involved).

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

Please someone discuss problem E (Invasion) and problem F (Intergalactic Mortgage). It will be really helpful.

I could not find a way for the problem E and got TLE in problem F using brute force.

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

    Well obviously you got TLE, there are millions of cases in the input file. Not like it'd be so simple.

    E: remember the min. distances to each vertex from the bad ones, update it using Dijkstra with breaks

    F: linear recurrence relation

    And while I'm at it, D is a simple O(NM) DP.

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

      remember the min. distances to each vertex from the bad ones

      How can I do that? Would you please explain in details please?

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

        In one array. Do you know Dijkstra's algorithm? You remember distances there.

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

      My question on problem F: What you mean by linear recurrence relation? I had simple linear recurrence relation too, but tried to find answer in O(n) for every test case, but it gave TLE. Can you please tell more about your solution? Is your solution faster? P.S. I had an idea about matrix exponentiation, but I think it is not necessary here

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

        This talks also about linear recurrences and their solutions. There is a formula that allows you to compute the result in O(1).

        I don't know what you mean by necessary, an O(N) solution obviously can't solve a million test cases in a second. Sure, you can use matrix exponentiation, you can use double exponentiation, whatever works in O(1) or . Not O(N).

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

          Thank you. By necessary I meant that there may be solution that is much easier. Most of contestants solved it too fast.

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

            I don't know what kind of easier solution than googling a formula you have in mind, but I assure you no bruteforce would work.

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

          my soln with complexity O(log N) is giving TLE for Problem F. :(

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

            It's not because of that, it's because you're using cin on doubles.

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

              Care to explain why cin on doubles should be avoided?

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

                Because it's slow, why don't you guess...

                (I don't know why it's slow, I don't have insight into C++. But it doesn't matter.)

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

      The solution of problem E is do dijkstra for each consul and do the dijkstra only when the distance of bad node to good node is < k, the demostration of the time of the algorithm is:

      the time of dijkstra is the number of number of times update one node, in this case the algorthm update each node k times, the time in general is O(k*nodes + k*edges)

      Zorry for my english.

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

        I know, you don't have to tell me :D

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

Any ideas on G?

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

    Maybe, hypothetically speaking, there could be a heuristic — but the input size is large as hell, so I'd say that you need a sweepline algorithm that maintains the set of lines ordered by their intersections points with the sweepline. It has a name, google it — or you can think about it yourself, it should be similar to the convex hull trick in DP.

    It feels like CTU Open problemsetters always tell themselves "so, for a seriously hard problem, let's have reasonably obvious but nasty geometry".

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

Any suggestion on how to solve problem B ?

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

    take one number, use algorithm described in statement while number != 1, and save in std::map<long long, int> number of steps:
    let d[x] be the number of steps to conver first number to number 'x'
    then use algorithm to convert second number to 1 and while converting choose the shortest way to do convertation

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

How to solve I?

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

    Optimized backtrack, probably. The authors suggest doing stuff like "if there's a cell with 1 neighbour, put a tile there first".

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what is test case 2 on problem H ? I wrote a dp solution, but it keeps giving me WA