Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

hugopm's blog

By hugopm, 3 months ago, In English,

Hello, Codeforces!

I'm glad to invite you to Codeforces Round #600 (Div. 2), which will be held on 16.11.2019 17:35 (Московское время). It will be rated for all participants with rating below 2100. You will be given six problems and two hours to solve them. As usual, the score distribution will be announced shortly before the round.

The problems were invented and prepared by me. Huge thanks to:

This is the first french round on Codeforces, I hope that everybody will enjoy it :) GL&HF to all!

UPD1: Scoring distrubtion is 500-1000-1500-1750-2250-2750

UPD2: Editorial is out

UPD3: Thanks for participating! Congratulations to the winners:

Div.1 (unofficial) participants

  1. Um_nik (solved all problems in 38 minutes!)
  2. dreamoon_love_AA
  3. mango_lassi
  4. imeimi
  5. cerberus97

Div.2 participants

  1. whyzker
  2. root_power_6
  3. SeranOZ
  4. AlineSH
  5. niro14

First solve

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

»
3 months ago, # |
  Vote: I like it -34 Vote: I do not like it

Hope problem statements are short & strong pretests.And also best of luck for your first round.

»
3 months ago, # |
Rev. 2   Vote: I like it -105 Vote: I do not like it

This is the first french round on CF, I hope that there won't be any DDOS attacks.

»
3 months ago, # |
Rev. 2   Vote: I like it +153 Vote: I do not like it

I wish this will not happened

y3mqxi9bulm11.jpg

»
3 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Unfortunately, right in the middle of the two contest days of CSP-S 2019

»
3 months ago, # |
  Vote: I like it +84 Vote: I do not like it

How to learn the culture of other countries?

Google (×) Codeforeces (√)

"Bonne chance et bonne note!"

It is correct?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I think we would just say "Bonne chance !" in french. We don't add anything comparable to "wish you high ratings", it would be redudant :)

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

    Ta tête est si mignonne. qwq

»
3 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

Good luck to everyone in this round! Hope it will be unique and interesting (because it is anniversary).

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

martin&frederick instead of Alice&Bob :think:

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

I hope your first contest will be my best ;) Good Luck to everyone

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

Round clashes with COCI #2. Please do smth. I really don't want to skip either COCI or Round, where McDic is tester

»
3 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Bonjour à tous — Bonne chance

»
3 months ago, # |
  Vote: I like it +36 Vote: I do not like it

baguette round :O

»
3 months ago, # |
  Vote: I like it +167 Vote: I do not like it

Me: I haven't done a CF round in ages. I should do this one!

Also me: wait I tested this?

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

You will not be lucky enough to see someone in No.1 spot in top rated list except tourist for long. Congratulations ! Benq.

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Everyone knows I only test the best rounds

»
3 months ago, # |
  Vote: I like it +39 Vote: I do not like it

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Does it mean french statements? Or, does it mean problems made in France? :o

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +89 Vote: I do not like it

    Problems made in France. Statements will be only available in english and russian, as usual.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Alright, thanks. I was afraid of french statements :o

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Upvote to become green

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

    You're OneSubmitMan you should be legendary grandmaster all problems are accepted in one submit

»
3 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

This will be my first contest by hugopm.Please, pray for me.

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

As soon as I saw that the round would be french, I immediately thought of baguettes, berets, and french accordian music. Good luck on the round everyone!

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

I hope the problem statements are short and clear.

»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Score distribution?

»
3 months ago, # |
  Vote: I like it -14 Vote: I do not like it

what is the penalty for wrong submission in this contest ? 50 or 10 points ?

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

A well balanced contest! Thanks hugopm

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

I'm not the only one who did Silly Mistakes :/ I forgot the most obvious case in B when the employee doesn't leave and as always forgot to handle long long in C

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

    I did Silly Mistakes on both A and B =)

    declare 1005 elements of array when it actually has 100000 elements

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

    My silly mistake in finding representative for sets — par[i] = par[par[i]] instead of par[i] = root(par[i])

»
3 months ago, # |
  Vote: I like it +78 Vote: I do not like it

Segmentforces lol :D

Good round btw

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Become Master =)) congratulate!

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

      Now I'm sure in this so thank you!

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Quite strange to see Vovuh in orange colour (instead of purple colour)

»
3 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Does d&c optimization not work for E? f[i][j] — minimum cost to cover prefix j considering first i elements. Here is the submission that works in n*m^2. The commented part and the recursion function is the d&c optimization.

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

    Can you explain your idea a bit?

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

    I don't think the dp was of the form where you can do divconq.

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

      Well it looks like a recurrence that can be optimized by d&c but i don't think that the function is monotonous so you might be right.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    1. Find distances between every two of centrals using Dijksta-like algo.

    2. After that sort all central-to-central distances.

    3. Construct DSU where for each component you maintain set of queries not yet answered.

    4. Then just merge distances from (2) in increasing order. Use small to large technique: and if query from small is present in large set that means that this merge is first moment when queries vertices is reachable one from another

    I was 2 minutes to slow to finish this in contest, so I'm waiting up-solving to submit. 65211806

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

      lol, i first construct MST after dejkstra and then solve smth like max edge on tree path query problem. Didn't understood that i could have answers on constructing mst already

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

    This might be super complex, but I think it works:

    1) Find minimum distance to every vertex from a vertex that has a station (Dijkstra), denote as d[v]

    2) Transform the graph, so that each edge has now cost c[u, v] = c0[u, v] + d[u] + d[v], where c0[u, v] is cost at the beginning

    3) Now each query is equivalent to — what is the heaviest edge on path in this graph between a and b.

    4) Find minimum spanning tree of this graph, and on that MST perform LCA to find heaviest edge from a to LCA(a, b) and b to LCA(a, b).

    I got RTE13, but I think it should do okay.

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

      I got lost on step 2. Why do we want the heaviest edge between a and b after the transformation? Also, what was the intuition behind the transformation?

      EDIT: I misread your step 1. Thought you chose an arbitrary central. Nice solution!

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

If I pass pretests, then brilliant round!

Or else, still brilliant round!

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

Is E a straight-forward dp? I thought it was easy, but I keep WAing on pretest 5.

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

    If $$$x_i < x_j$$$, you only extend $$$x_i$$$ enough to cover the uncovered left part because it's always better to cover the right part with $$$x_j$$$.

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

What was test case 6 in D? :(

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

How to solve D?

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

    Use dsu Find min and max in every component, save these as segments, sort them If seg[i] crosses seg[i -1] then combine them and ans++

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

      How much crosses if one (or more) segment completly inside another? And why?

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

        I also checked whether these two segments are connected now or not using dsu

»
3 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

In problem D, I tried this approach: instead of finding the union-set of each element, store each disconnected component's max and min in a vector using dfs, sort the vector by min elements, then no. of segments (found using the above sorted vector by normal traversal) which are intersecting is the answer.

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

    how do we find intersecting segments.?

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

      considering you have above vector<pair<int, int>> x, and:

      • x.first = min_ element of each disconnected component.
      • x.second = max_ elemtent of that component.
          sort(x.begin(), x.end());
          max_ = x[0].second;
          for(int i=1; i<x.size(); i++){
              if(x[i].first < max_){
                  cnt++;
              }
              max_ = max(max_, x[i].second);
          }
          return count;
      
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I made the same idea, I hope this idea pass the system test

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

How to solve D? is it union find?

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

    i got TLE using union find

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

    It is somehow about counting the components and count the missing connections between them. Still not fully sure about which ones to connect to each other.

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

      I guess each connected component must have all consecutive vertices. If not, you must connect it to another component that has that vertice. I tried this using DSU and got TLE, and then WA.

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

    me too. but i thought it is because of python

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

    It is, you can check my solution.

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

    Do DFS from 1 to N for every currently unvisited node and store the maximum visited node so far. Before doing DFS if the maximum visited node is greater than this unvisited node that means u need to connect these components, and hence increase answer by 1.

    Spoiler
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thats by far the most nice solution to this problem I have seen, thanks.

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

      Thanks, this is a cool idea! I missed it completely :(

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

    OK. I knew what i did wrong. i had to check duplicated visits :(

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

    Yea union find worked for me.

    Edit. But now that I think about it — simple dfs or bfs would be enough for me.

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

    Process the connected components (either bfs, dfs or union find) and identify the max element for each component. Then check for each element 1 through n what component it belongs to and the max of this component. If you see an element of a different component and you haven't reached the max, update the max and add 1 to the answer. $$$O(m+n)$$$ overall.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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

graphforces

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

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

Couldn't solve anything... feel so dumb atm... :'D

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

    Eh, you're not the only one. I tried solving C as DP problem, tho i think the actual solution is easy :D

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

So far, there isn't any comments on B.Ummmm......Don't you want to say something about it?

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

    I don't know what is the corner case in test 13

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

    I couldn't solve A and B. I think these problems with a specific implementation, where you have to be careful, but I, as it turned out, is not like that)

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

    I shouldn't make such a comment. My B FST now......

»
3 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Worst Contest i ever had. trash A,B problems

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    You have done only 2 contests so far. It is too early for you to get frustrated.

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

    You even didn't submit neither A nor B. How could you have contest if you haven't participated?

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

in Div2-B I did the same as tutorial but instead if the office is empty start a new day I didn't start a new day and continued the solution until I found someone who is already entered, I begin new day at this time.

what makes this solution fails on test 13 ?

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

    I'm guessing something like

    6
    1 -1 2 1 -1 -2
    

    would make it fail, as you end a day when 2 is still in the office.

    Trying to minimize the number of days like you're doing is actually something none of the testers thought about, hence the lack of pretest designed to make this solution fail. There will most likely be a lot of systests on that problem, and we sincerely apologize for that.

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

      agh!!!. what a (Silly Mistake)

      Problem name is really describe my mistake!!

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

      What is the answer to the test case? Is it -1 (or) 2 [2 4] ?

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

        The latter is the correct answer.

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

          Hmm, my code is printing the same but still FST.

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

            Shit!. I did not check the condition that one can't leave without entering. Nice and strong pretest.

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

      Can you please see what is wrong with my approach, the test 13 is big and i cannot make sense of it?

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

      what if we check if the ones who entered already left when somone reenters above soltions should work..But it still fails on test 13. can someone help 65220901

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

    Lol, I did same thing((( I think smth like this: 1 -1 2 1 -1 -2

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

Thx 4 rlly fast testing and great pretests))

»
3 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I'm sorry for the unexceptedly high number of FSTs on B. It was the last problem added in the contest (between Single Push and Sweets Eating, in order to make the round more balanced) and we didn't come up with the incorrect greedy that tries to minimize the number of days :(

»
3 months ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

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

I miss this contest,but now I'm trying to solve the problems but it says you can't, you should register to submit your solution.

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

Got FST in B WA 33 :/ Can anyone go through and tell what silly mistake did i do?

https://codeforces.com/contest/1253/submission/65188326

thanks

got it simple silly mistake

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Fastest editorial I've ever seen

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

please what's wrong with my solution to B?

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

Thanks hugopm !

»
3 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

D was the easiest. This should not be like this

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

Can someone tell me a cleaner approach for D using DSU . I did something like storing the minimum vertex in each component and if that component does not form a contiguous segment I start merging.

»
3 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I can relate with B's name .

Worst Mistakes I have done in a while (just missed both B and D).

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

Can someone explain their idea for problem E using Segment tree?

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

    The inner min query of DP transitions can be converted to segment tree, though it's unnecessary.

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

    Create segtree of size m+1. You start index 0 with cost 0, and indices 1...m with cost inf. Then we iterate through each antenna i in increasing order of position. Now we iterate through all possible sizes j for antenna i, such that it reaches interval [i-j,i+j]. The cost, denoted by cst, for this interval is max(0,j-s_i). Now we add this interval in the following way: we find the min cost x on interval [i-j-1,i+j] and then set index i+j to cst+x. In this way, we are "extending" the configuration from [0,i-j-1] to [0,i+j]. Now answer is index m in segtree.

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks hugopm for the round and congrats for reaching GM!

»
3 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

My rating before the round: 2032 Expectation: +68 (Master) Reality: -68. Expectation + Reality = 0.

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

I've did some Silly Mistakes in the problem B during the contest, but resolved after that. In C I can't think of a solution with complexity less than O(n^2), any tips or topics to study?

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

    The solution to C involves dynamic programming. However, we must make some observations first.

    If you want to eat exactly $$$k$$$ sweets, it is optimal to always eat the ones that will result in the least sugar penalty. So, we will sort the sweets from lowest to highest sugar penalty, and for each possible $$$k$$$, we will eat the first $$$k$$$ candies in our sorted array.

    Next, we realize that the optimal way in which we eat these $$$k$$$ candies is to take as many as we can each day, starting from the largest ones. For example, if we had $$$k=5$$$ sweets from $$$(1, 2, 3, 4, 5, 6, 7)$$$ and can eat $$$m=2$$$ each day, we would eat $$$(5,4)$$$ on Day 1, $$$(3,2)$$$ on Day 2, and $$$(1)$$$ on Day 3.

    So there is our $$$O(n^2)$$$ approach! For each $$$k\leq n$$$, we greedily take sweets in this manner. To improve this to $$$O(n)$$$, we make some more observations about the patterns in these calculations. Let's consider the same example as above. For $$$k=5$$$, we have a minimum sugar penalty of $$$1(5+4)+2(3+2)+3(1)=22$$$. How about for $$$k=7$$$? Then we would have $$$1(7+6)+2(5+4)+3(3+2)+4(1)=50$$$, which looks suspiciously familiar...

    The expression for $$$k=7$$$ can be broken down into the result of $$$k=5$$$, plus the sum of first $$$7$$$ sweets. As a matter of fact, the result of any $$$k=i$$$ will be equal to the result of $$$k=i-m$$$ plus the sum of the first $$$k$$$ sweets in our array, as long as $$$i>m$$$. We can calculate the sum of the first $$$k$$$ sweets in constant time by using a prefix sum array. Let's store our results in an array called $$$dp$$$.

    Our transition is as follows:
    - for $$$i\leq m$$$, $$$dp[i]$$$ is simply the prefix sum of all elements up to and including $$$i$$$.
    - otherwise, $$$dp[i]=dp[i-m]$$$ plus the prefix sum of all elements up to an including $$$i$$$.

    I hope this helped! If not, the official editorial should help you get somewhere. Cheers!

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

      Wow, it really helped me and was very didatic. Much obliged!

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

For D, I thought of two questions:

(a) how many components are there at the beginning?

(b) how many components must be there after the operations?

then the answer is the difference (a)-(b).

(a) is a simple union-find. (b) is a Problem B when an edge (u, v) means an employee comes at time u and goes home at time v.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Congratulation!!! root_power_6

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

i am so weak , how to become strong? QAQ

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

Can anyone please fix the tags for problem A? It seems that somebody had been spamming every single tag available on that problem.

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

.

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

some people copy from ideone and pretend that they are smart.

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

why they didn't give ratings till now?