MikeMirzayanov's blog

By MikeMirzayanov, history, 8 years ago, translation, In English

You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

  • 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
  • 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
  • 3 place: Saratov State University #1 (Edvard Edvard Davtyan, Vitaliy kuviman Kudasov, Danil danilka.pro Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

  • Vote: I like it
  • +235
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

An hour after this contest ends, COCI contest starts. Tomorrow's gonna be intense! :D

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

    I do not attend any of these. And i was not if there was a t-shirt prize. I will not code anymore. We have been a very good family so far, but i need to leave now. Good bye! ps : im so sorry mahmoudhassan :(

»
8 years ago, # |
  Vote: I like it -37 Vote: I do not like it

No T-shirts ?

»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

For how many Hours Contest will Run ??

»
8 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Please provide editorial and codes if you plan on moving it to gym.

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

    For what reason?

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

      I don't know a lot about Gym contests, but I know this much that they don't allow you to look at test cases, as well as others' solutions. Thus, I was asking them to open others' solutions and test cases , and also provide editorials. That's all :)

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

    Did I get so many downvotes because I forgot to mention "after the contest" , as Gym problems don't let you look at others' codes, or test cases?

    Please tell me if the reason is something else, because I would like to know. I haven't practiced a lot of Gym problems you see. :)

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Will there be youtube editorial after the contest like last year ?

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

how will be the difficulty level of the problems?? Can we (newbie's) can solve these..

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

How to solve Problem F ??

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

    Just make binary search by time near each food and then apply a greedy strategy : eat the most needed food, that will be ended soon. (how many this food we need — number of second it will be available). http://pastebin.com/0crsX2yH

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

      How can you prove it? I can't understand.. I used maxflow algorithm and accepted!

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

will test cases be public later? thanks

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

is it possible to solve G with square-root decomposition ?

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

How to solve C?

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

    First trick: we need only first 60 concatenates.

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

      What's the next trick? We have TLE #11, our solution works about 30s on max test. It's quite straightforward, with complexity something like O(queries * log(r) * maxShift).

      How to solve it faster?

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

        My complexity the same is O(queries * log(r)). Next trick is recursion, if we want to know answer for k-th string on L,R we can use answer for k-1-th string for some new par L' and R'. k-th string can be split into four groups:

        [---p---][--s--][--s--][---p---]
        

        length of [s] it is t[k] (shift length)

        And now, clearly, we have 10 cases of calls in recursion, depending on location L and R.

        Next trick — |s| is small (<=100). In my solution i precalculate answers for all suffixes for all strings.

        For example, if L in 0th group and R in 2th we can use these values and just change R to R'. I think all 10 cases are easy except case L in 0 and R in 3. But if we built projection D of R

        [---p---][--s--][--s--][---p---]
        ..D...L__________________R......
        

        then we can call value for segment [D+1, L-1] and subtract it from all count of symbols. If D>=L we need add it, ofc.

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

can anyone share his algorithm about prob B? I only think of one with complexity O(n^2logn)

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

    n^2 solution: Save all pairs (w, h) such thatw > h (swap them if needed). Sort in ascending order of w. Save all unique h values.

    For every unique h and i (i <= n) remember how many elements with height greater or equal than h there is on suffix from i to n.

    Then just iterate over w (in ascending order), inside this iterate over all unique h values, answer how many elements we have with height > h and having width not less than w in constant time.

    Solution: [submission:13688964]

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

How to solve problem K?

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

    Problem K

    The key observation here is that every time we need to choose a task, we shouldn't look through all of them.

    Imagine we have a list of deques q, where q[t] is the deque containing all tasks with t[i] == t, ordered by l[i], then by i. Let's denote the minimal t such that q[t] is not empty, as minT.

    We can consider only deques q[minT], ..., q[minT + sqrt(10^5)]. Proof: If t[i] + sqrt(10^5) < t[j], then the function l[i] — (T — t[i])^2 is definitely less than l[j] — (T — t[j])^2, no matter what their l and t values are. So the tasks with t[i] > minT + sqrt(10^5) cannot be minimal.

    As all deques contain tasks ordered by l[i], then by i, just as in the statement, iterate over all t in the interval [minT, minT + sqrt(10^5)], and choose the best task from the first elements in deques.

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

How to solve D?

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

    O(n^2) . For Each , check others to catch up,This can be done in O(1) or using binary Search in Time.(O(log(n))

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

what's the 10th test case in problem D ? -_-

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

    Integer overflow probably. For me it failed on checking (f[i] - s[i]) * (f[j] - s[j]) > 0

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

Could someone post their code for A?

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

How to solve problem J ? if i can't move forward should I stop the robot ?

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

my solution for problem J(cleaner robot) is failing on test 15. Can anyone guess what would be wrong?

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

    mine too ! couldn't pass the test 15. 15 attempts, all failed ! :(

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

      After WA15 I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile.

      And test I tried was like

      6 6
      ......
      ......
      R.....
      .....*
      ......
      ......

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

        can you please tell me the answer for this test?

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

          14

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

            I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile? can you elaborate it?

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

              In my solution I just make n2 * m2 steps. It's enough to get AC.

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

                If one step is either moving or rotating, it's enough to make 4*n*m steps. Cleaner has only 4*n*m different states — each direction on each cell. We did it bfs-like, though — with vis[row][column][direction].

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

                  I agree
                  It's not like I was trying hard to get this number, chose the one that will be under the limits.

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

what is the 15th test case of problem j??

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

Can anyone share his code for problem J ?

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

    Maybe 1 10 .........U

    OR 10 10 .........* .......... .......... .......... .......... .......... .......... .......... .......... .........U

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

    Although my code is very big...i have written it in a very simple manner putting all the different conditions...so you can easily understand the code

    http://ideone.com/EuC5xL

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

      thanks. by the way, test cases are public now. so i found my bug. anyway thanks again for sharing your code. :)

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

can anyone guess what is test 15? question to those who passed the tests. I am curious in knowing where my solution is wrong

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

Did anyone solve Problem — G using segment tree?

  • »
    »
    8 years ago, # ^ |
    Rev. 19   Vote: I like it +17 Vote: I do not like it

    Yep. Sort both the days and applicants (by di) in reverse order, process them in parallel. More specifically: when considering candidate i, it suffices to only consider the days j with tj > di (all other days are useless anyway). So we process the candidates by descending di, and for each candidate we would like to find the earliest time they could be done. Clearly if we only consider days j with tj > di, then the optimal solution will be some prefix of this sequence of days.

    You can use a segment tree where leaf j starts as (0, 0), and when you 'process' (more on this later) the day you set it to (tj, 1). Here the first value represents the total available time (we haven't considered setup time yet, but since we are going to maintain that for all days in the segment tree we have tj > di this day will still result in a net gain) and the second value represents the number of days over which this is spread. Combine two leaves with pairwise addition. The idea is now to insert each day j as soon as we process a candidate i with tj > di, because after that, all candidates will have a lower di value, and thus they can also use this day (recall that we process all candidates by di in descending order). You can achieve this quickly by also sorting the days in descending order and maintaining a pointer to the next day that should be inserted.

    After this, you can use the segment tree to compute whether a certain prefix of the days is sufficient. Query the interval [0, d) for some d, this will result in a tuple (time, days), the total amount of time and the number of days in this interval, respectively (amongst all days with tj > di). The candidate can then finish if and only if time ≥ ri + di × days. You can use binary search to find the smallest prefix, since, again, all days in the segment tree will result in a net gain (tj - di to be precise), so the amount of available time for a prefix [0, d) is increasing in d.

    After preprocessing my solution was because I was being lazy, but you can drop the binary search and find the optimal prefix in a single traversal in . Details are left as an exercise to the reader :)

    Code

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

      TimonKnigge My idea was same as you but did it ascending order of . Couldn't figure out what's wrong :( Code

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

        Are you sure you are processing the candidates/days in the right order? You seem to process them in ascending order, not descending.

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

          You wouldn't believe how stupid I'm. The problem was I take n as m and m as n. :( here is the AC Code

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

          You can do it by ascending order too. For each , remove all and then find the result using segment tree.

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

    I solved using BIT in nLogn complexity. Code

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

forget it. Everything is alright. :)

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

i could take it just for about half because of school classes! but i enjoy it !

thanks XD!

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

No way to see other's code?

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve problem H?

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

Ideas for H?

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

full of implementation

»
8 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

The algorithm for the robot to move and clean the floor in the room is as follows:

1.clean the current cell which a cleaner robot is in; 2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1; 3.otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2.

Input #15:
10 10
.*********
.*.......*
.*.*****.*
D*.*...*.*
.*.*.*.*.*
.*.***.*.*
.*.....*.*
.*******.*
.*******.*
.........*

How the ans is 10? Why not like this?

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

    You have an infinite robot movements on the first column: upwards-downwards.

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

    look here "The algorithm for the robot to move and clean the floor in the room is as follows:

    1. clean the current cell which a cleaner robot is in;
    2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1;
    3. otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2. "
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the idea to solve Problem M?

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

How to solve F using flows? Problem Link

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

what happened with the contest 589? We can't submit now!

you can visit vjudge https://vjudge.net/problem#OJId=CodeForces&probNum=589&title=&source=&category=all to view the statements, but can't submit.