I_love_natalia's blog

By I_love_natalia, history, 9 years ago, translation, In English

On April 4th, V (XVI) Volga Region Open Team Student Programming Contest was held in Samara State University. And now, we invite everyone who haven't already participated in the championship to join the Codeforces training contest version on June 21st (11:00 — 16:00 MSK, UTC+3). We believe that participants of any level will find problems that will be interesting for them. The contest will probably be mostly interesting to participants with violet and orange levels (difficulty is 4 stars).

This contest uses ACM ICPC rules.

Please, do not use the Internet, prewritten code and other sources: participants of the championship could not use any of these.

Contest was prepared by Dmitry Matov (Nerevar), Constantine Drozdov (I_love_natalia), Andrew Antipov (Sinner), Andrey Gaidel (Shlakoblock), Elena Rogacheva (elena), Sergei Shteiner (steiner), Alexander Efimov; Igor Baryshnikov (master_j) was of great help in English translation.

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

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

Isn't it a gym contest?

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

Where can we find the link to the contest?

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

Great!!!! and thank's! :D

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

The registration is open now at gym :)

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

How to solve problem A? I saw a lot of AC on this, but I completely have no good idea on this one.

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

    Minimum spanning tree, answer is maximum edge weight

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

    Let's build graph, where string are verticles abd between each pair of verticles there is an edge of weight equal to difference between strings. Now question is: what is the smallest K such a graph with edges with weights <=K is connected. It can be done using binary search. If we fix K we just do dfs which is going by edges <= K and check if graph is connected

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

    my solution : build graph with recipes. g[i][j] is equal to distance between recipe i and recipe j. then use binsearh for answer: for the fixed answer there shuold be a path with all recipes and without edges with weight greater then anwer

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

How to solve K? I could not find any approach for this question but it has a lot of AC's so I am guessing it cannot be extremely hard.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it
    ans = 0
    while (true) {
      posA = (position of the rightmost not processed 'A')
      posF = (position of the leftmost not processed 'F')
      if (posA < posF) break
      ans += posA - posF
    }
    
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      After adding posA — posF which of the 2 things is considered processed?

      Or do we consider both possibilities by dp somehow?

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

        Letters 'A' and 'F', on positions posA and posF are considered processed at each step

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

          I am sorry to keep on bothering you but could you please explain how your method works?

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

            Just take a pen, write some examples and see that it really works. I don't have any other proofs.

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

    Here's my idea: all we want to do is all As should come before F. Now considering A and F are some values such that A<F now we want to calculate no of inversions ( problem becomes similar to sorting an array with only operation of swapping two adjacent elements. I dont know proof but its equal to no of inversions in the array). Now main problem is every N can be taken as A or F. Which we can solve using a recursive function with two arguments 1.position we are referring to 2.no of Ns considered as F before this position. For every F just count no of As after that position. For every A dont do anything. Now for every N if we consider it as F do same thing as normal F and if its A then add to the answer total no of Fs before this position (original no of F + considered ones). I hope this helps.

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

      Ah yes. This helps a lot.

      I was already aware of the minimum swaps = inversion idea and during the contest was trying to reduce this problem into that one but was unsuccessful in doing so (because of the N's). Your solution takes care of that in a very nice manner.

      Thank you.

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

      Proof —

      If we swap any two adjacent numbers, the number of inversions decrease by at most 1. So, we need at least inversions-count adjacent swaps to sort the array.
      And as long as the array is not sorted, we can find two adjacent indices whose swapping will decrease the inversions. So, minimum number of swaps needed is indeed the number of inversions.

      On a related note , what if the adjacent condition is lifted i.e. we can swap any two numbers, what is the minimum number of swaps needed ? If all the elements are distinct, we can solve by counting permutation cycles or by a greedy method. If there are equal numbers as well, i am not aware of solution. Does anyone know ?

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

      I used brute force and greedy for this problem I fixed a position 'pos' and solve the minimun number of swaps when all 'A's are on the left of pos, even they can take pos, and every 'F' has to be on the right side.

      That's when the greedy steps come....

      Closest F to 'pos' on the left side will swap until it stays at 'pos', similar with closest 'A' to 'pos + 1' on the right side will swap until it stays at 'pos + 1', then swap what you have in pos and pos + 1. Do the same until you can't get one 'A' on the right side and one 'F' on the left side.

      When there is no 'F' on the left side of pos or there is no 'A' on the right side of pos you'll have to swap 'A' or 'F' with 'N's to achieve the goal.

      code : link My solution is O(n^3). I've simulated every step :/, it could be better maybe, without simulation...

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    consider dp[i][j][k] which means how many swaps do we need to move all A's in first k positions of substring(i,j) and moves F's out of first positions.
    then you can update dp so easily.
    
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      nice and greediless :D

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

Can anyone explain how to solve G or provide a test case for which my submission 11697424 will fail?

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

    Something similar to:
    7 5
    1 1 1 1 1 5 1
    Correct answer is
    7
    +++++-+
    but your answer is 5.
    Correct approach is dynamic programming dp[i][j] — are we able to get number j after i moves.

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

    Try this:

    4 100
    50 10 10 60
    
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas for question I please??

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

    Build pairs of  < skill, field >  for each course, sort all of them in increasing order by skill and find an interval [i, j] of courses which has the following properties:

    1. There exist at least one course for each field in that interval
    2. Skill[j] - Skill[i] is minimum
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you!

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

      I would add that you can find such interval in O(n) time using two pointers technique. Of course complexity of whole solution is still O(n log n) because of sorting.

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

very good problems with nice ideas , but is it necessary that statements be very inexpressive ??

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

How to solve F?

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

    dp[i][a][b] — the best result for i processed indices, a of them are chosen for the first player, b of them — for the second player.

    There is also a flow solution but DP is much easier.

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

      how is the flow solution modelled ? The DP was pretty easy!

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

      a can be at most 400 and b can be at most 400 and i can be a most 400, a MLE will be given isn't it?

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

Thanks! I really enjoyed solving your problems! Specially "problem I" which was really interesting in my opinion!

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

Is it possible to discuss short write ups on the problems? Atleast on the ones with less than 50 AC.

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

    Sorry for my bad English.

    C) Main idea: go from up halls to downs and for each hall keep set of disjoint intervals. Interval is a structure with following parameters:

    • hall — hall number
    • from — first moment such that we can come in interval
    • to — last moment such that we can leave interval
    • start — start of the flight such that we can come in interval in moment from
    • prev — prev interval on hall with number hall - 1 or null if we start from hall with number hall

    For each hall we can construct its intervals using intevals of previous hall (it is case when we come from up hall) and open segments of current hall (case when we start from that hall). After building intervals for current hall we have to merge them greedily. All that can be done in O(numberOfIntervals) operations if we keep intervals sorted by from and use two pointers. Maximum available value of numberOfIntervals is less or equal than , so we can process all halls with total asymptotic . Further we can find best interval. It is interval with minimal start such that to - start ≥ t. After we just need to restore the answer.

    Source: pastebin.

    D) I’ll just leave this here: part 5 in article.

    E) Just find cutpoints and biconnected components and construct tree of biconnected components. After that we can use dfs on that tree to calculate for each cutpoint sizes of children components and size of parents components. English, Russian. It can be done in O(m) operations.

    Source: pastebin.

    H) It will be written later by me or elena.

    J) In first calculate maxGame  –  prefix maximum of queries(lengths of games) and sort gamers by t. After that come from the last game to the first and for game number i will be add gamers with t ≥ maxGame[i] in DSU. Answer for game number i: g[i] * size(0), where size(0) — size of set, which contains knight. It also can be solved by BFS and TreeSet. Asymptotic: O(m·α(n)).

    Source: DSU, BFS.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it -7 Vote: I do not like it

    some write ups in rev 1.

»
9 years ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

Enjoyed problem H "A lot of work" a lot. Seems that most of the solutions are some kind of heavy-light decomposition which solves differently long and short colour chains. My solution is a bit different, at least in terms of the written code, there is no distinction between long and short chains, I solve both of them with the same code. The main idea is that the result function for a given colour chain is monotonous with regards to its forgetting parameter k, so if we know that f[k1] = f[k2], then we don't need to calculate the answer in between of k1 and k2. So for a given colour my solution goes as follows:

  1. Sort all queries by their parameter
  2. Calculate result for the first and the last queries using straightforward approach (O(M) solution, where M — length of current colour chain).
  3. Recursively calculate result for all queries between first and last, given the results for its borders. If both answers are equal then set this result for the entire range. Otherwise take the query in the middle, calculate its result using straightforward approach and repeat recursively for its left and right halves.

Submission: 11838173

Code

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

    Your submission is not available for all.

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

      Thanks, always forgetting that submissions in gym are not that easy to see. Plus this time they were submitted with coach mode enabled which makes them even more difficult to see.

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

    And why will we use straightforward approach small amount of times?

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

      Thanks for asking, I forgot to clarify that part. I claim that function f(k) will have no more than distinct values for all given values of k. The reason for that is that we can consider two cases:

      • — in this case obviously you have no more than distinct values.
      • — in this case we need more than segments to cover the entire timeline. That simply means that the length of the segments can be no more than itself, otherwise it will cover more than N elements in total. But that length of the segment is our parameter k, so we have . So we have no more than distinct parameter values, for those values we can't get more than distinct function values.

      So we have distinct values in the result array. The entire point of the algorithm I described above is that it skips intervals where function doesn't change its value. So effectively it looks for all distinct values and then does binary search between adjacent different values to find the exact parameter value where the function changes its value. So in total it should be invocations of straightforward algorithm.

      I think the idea behind heavy-light decomposition in this problem is similar to my intuition above but this solution uses this intuition only to prove its correctness while the code is simply does binary search + brute force approach which is very easy to code, that's why I wanted to share it.

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

How to solve problem H by heavy light decomposition ?

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

Can someone give some tricky test case for problem E ? Thanks I'm not sure if I understand problem E correctly.