vovuh's blog

Codeforces Round #595 (Div. 3)
By vovuh, history, 7 years ago, translation, In English

UPD: Thanks to Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev and Artem Rox Plotkin for help with round preparation!

UPD2: Editorial is published!

<almost-copy-pasted-part>

Hello! Codeforces Round 595 (Div. 3) will start at Oct/22/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

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

Comments Comments (162)
| Write comment?
»
7 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

vovuh

→ Reply
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it -15 Vote: I do not like it

I wish you all good luck

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

hope this contest becomes my last official participation in DIV3.

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

I hope become pupil

→ Reply
»
7 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

Good luck to everyone. I hope this round will be an exciting contest without dots attacks and lots of hacks. Finally I hope the problems will be solvable and understandable.

→ Reply
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it -13 Vote: I do not like it

Div-3 is Love... True Love... Pure Love...

→ Reply
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it -12 Vote: I do not like it

Love Vovuh's Contest

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +34 Vote: I do not like it

Fitness challenge: I'll do one pull up for every rating point lost and I'll do 3 pushups for every point won. Feel free to join the challenge under your conditions.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

I think you should take part in some contests to become master. It's more beautiful ^^

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Why Div3 get so little upvotes :(

Are we just used to them?

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Which problem has two subtasks? @vovuh

→ Reply
»
7 years ago, hide # |
 
Vote: I like it -45 Vote: I do not like it

Why do Vovuh conducts only Div.3? I don't like him.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

Hi! I decided to simplify one of the problems and divided it into easy and hard versions. That's why I increased the round duration to 2:15. Don't afraid of formally too many problems in the round. You shouldn't think about easy/hard versions as about two independent problems. And good luck!

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it -11 Vote: I do not like it

    Very good idea to divide problems into parts. Sometimes, even after solving the problem, it requires additional data structures or optimizations. This way even partially correct solutions that are slower than intended get partial points.

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

      Another idea is creating one problem with different types of tests. Solutions can first get tested on small tests, and then on bigger numbers. And if it passes small tests, contestant can get partial verdict. This has been done in several rounds, to it is possible. It is just easier to navigate this way, instead of solving 2 same problems

      → Reply
»
7 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

I will AK this contest !

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

Vovuh, the half-quarter!

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

Good luck!

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

I want to improve myself~

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

There's an expert participant in the trusted participants rankings, by the way.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Contest is over. It was a good contest.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I solved 7 problems for the first time. Feel amazing >__< !!

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

    I solved 6 but still. Which 6 did you solve?

    I didn't solve D1, D2 and F. Is D1 just straight bruteforce? I didn't try because it seems like it'll be something like O(n^4) :(

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

      I believe you can see his submissions

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

        Oh ye. Problem E is awesome, I tried a dp-greedy method and it worked. I can't even convince myself that it is true, but complexity-wise it passed.

        dp[i][elevator?(bool)] = Minimum total time to reach ith floor, with last move taking the elevator (or not, depending on the bool)

        dp[1][false] = 0, dp[1][true] = c

        dp[i][false] = min(dp[i — 1][false], dp[i — 1][true]) + a_(i — 1)

        dp[i][true] = min(dp[i — 1][false] + c, dp[i — 1][true]) + b_(i — 1)

        output *(min(dp[i]) for i in range(1, n + 1))

        Can someone prove this .-.

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

      Ummm I used Segment Tree with Lazy Propagation for D1 & D2. (Segment Tree is really useful >__<!!

      But I think there will be more easy way (maybe)

      I thought adding Persistent Segment Tree for D2 at first, but I'm so scared to coding it, fortunately it was solved by priority_queue.

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

    I solved 7 problems too. I wish this contest is rated.

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

Can somebody explain test case 2 in F?

Thanks

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

How to solve C2 ?

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

    It's just ternary numeral system.

    My solution:

    precalculate all values 3^n (0..38 powers), it's 100..000 preseentation of number

    next I check first X that 3^0 + 3^1 + ... + 3^X (presentation of 111..11) >= n, if yes subtract from n 3^X, and add to result same number

    do while n > 0

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

      What about n = 10^18? In the first test the answer is 1350851717672992089, but 3^38 > 10^18 and less than test's answer

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

        You are correct (10^18 — 3^38) < 0 and loop stopped.

        But first I compare with (3^39-1) and subtract (3^(39-1))

        upd: sorry, not 3^X-1, but 3^0+3^1+..+3^X and if this value greater or equals than n I subtract 3^X from n and add to result

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

How to solve D2?

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

    I solved it using line sweep algorithm. Iterate through the points [1,2e5]. Keep a set that includes current line segments. Whenever you find a condition where the number of line segments exceeds k in the current set, remove the line segments which have higher ending point.

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

What was test case 14 of D1?

Also, how where you supposed to solve D2? I thought using a BinaryIndexedTree, but I wasn't sure how to implement.

→ Reply
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

What is Test 11 for Problem E?

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

Isn't Meet in the Middle expected solution for C2. My solution got TLE on test 7

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

I solved only 2 problems. Will my rating will increase or decrease? The problems were easy but I couldn't cope up with the constraints leading TLE

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

How to solve F?

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

    dp on tree

    dp[i][j] is the max sum can be obtained from the subtree of vertex i

    with the nearest picked vertex from this subtree is at distance j from vertex i

    → Reply
»
7 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

I think this round is easier usual Div 3 round.

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

Any Penalties on Unsuccessful Hacking Attempts?

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

The moment I realized that the comparator used by me is wrong in D1/D2 after printing all the values for an hour...........

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

Anyone tell me why this code gives TLE? 63189145

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

What's wrong with this solution for F — dp[node][level] = answer for subtree rooted at 'node' such that among all selected nodes the smallest depth is at 'level'? This recieved WA-3

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

After seeing constraint I thought greedy won't work for C2 so wasted one hour to implement Bit Mask+ Meet in the middle.Lesson learned. -_-

→ Reply
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it +16 Vote: I do not like it

My solution for $$$F$$$:

Root the tree at node $$$1$$$. Let $$$dp[i][j]$$$ be the maximum subset weight for the sub-tree rooted at node $$$i$$$ if the nearest node in the subset to $$$i$$$ is at distance $$$j$$$ from it. Let $$$mxdp[i][j]$$$ be $$$max(dp[i][k])$$$ for $$$k$$$ from $$$j$$$ to $$$n$$$.

How to fill $$$dp$$$?

$$$dp[i][0]=a[i]+\sum_{c}mxdp[c][k]$$$ where $$$c$$$ is every child of $$$i$$$.

$$$dp[i][j]$$$ (for $$$j$$$ from $$$1$$$ to $$$n$$$) $$$=max(dp[c_1][j-1]+\sum_{c_2!=c_1}mxdp[c_2][max(k-j,j-1)])$$$ where $$$c_1$$$ is every child of $$$i$$$, and $$$c_2$$$ is every other child of $$$i$$$.

The answer is $$$mxdp[1][0]$$$.

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

In D why remove segments from longest to shortest length is wrong?

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

    Imagine three segments [1, 1000] [1001, 2000] and [1000, 1001] and k = 1. There are two points that have k = 2 : 1000 and 1001. If you remove longest segments, then you will need to remove both of the big ones. In another case, you can just remove the third one and m = 1

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

how to solve B2?

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

    use dfs, to travel continuously until u get end point of cycle.then update all the travelled value to max distance you have travelled until now.see my code.submission

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

    You could use disjoint sets too... Just put i and arr[i] in same set (union) and like size find size of each set, the answer is same for all the elements in the same set, ie, size of the set.

    → Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
 ll n;cin>>n;ll temp=n;
        int idx=0;ll mn_diff=LONG_MAX;
        while(psm[idx]<n)idx++;
        // dbg(pt[idx]);
        for(int cnt=idx;cnt>=0;cnt--,idx--){
            mn_diff=min(mn_diff,pt[idx+1]-n);
            if(n>psm[idx])break;
            if(n>=pt[idx])n-=pt[idx];
            if(n==0)mn_diff=0;
        }
        cout<<temp+mn_diff;nl;

i was getting wrong answer using mn_diff=LONG_MAX, is it wrong to use LONG_MAX for std::min function in c++, but also it gave correct answer on my compiler.

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

For problem E, could anybody tell me why PyPy 2 TLEs but PyPy 3 ACs?

→ Reply
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

My approach for problem D1 is keep removing the segments intersecting with maximum number of bad points .Is this approach correct ? My submission is giving wrong answer though My Submission

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

    I got WA on 9. Switched to iterate from left to right on bad points and keep removing segment with largest end point, and that passed.

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

      Your approach is also nice.Still wondering what is wrong with our first approach .

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

        I found out whats wrong.

        Take the following case

        5 1
        1 2
        2 5
        3 10
        7 14
        14 15

        Here if we try deleting segments with most bad points, we will first delete 3 10, then 2 5, then 7 14. But the correct approach is to delete 2 5, and 7 14.

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

Hack case for B?

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

The problem-set contained better stories than all of my films combined.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
How to prove this solution ?
→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In problem C2

	// Wrong Answer 
	/*
	for(int i = 0 ; i < 40 ; i++){
		my[i] = (int)pow(3LL,i) ;
	}
	*/
	// Accepted Solution 
	my[0] = 1 ;
	for(int i = 1 ; i < 40 ; i++){
		my[i] = my[i-1] * 3LL ;
	}
	//

This is my AC Code 63196491

what is wrong with this line my[i] = (int)pow(3LL,i) ;

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

thanks for this amazing contest :)

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

Sorry for my bad english, but the user named AHR9N has cheated, he asked me for the code of the problem B2, but I did not send. I think he needs to be severely punished

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

Oh,I can't get problem c2,problem c2 and problem e by using m2.codeforces in this contest. It told me that the statement is available.

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

Can anyone give me the solution of Problem B2 using DSU?

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

In question https://codeforces.me/contest/1249/problem/A A. Yet Another Dividing into Teams from equation it means that difference should not be 1. Statement says difference should be strictly greater than 1. And test cases are aiming just for difference not equal to 1. There is a bit ambiguity . As for input 1 1 1 1 1 1 Answer should be 5. In test cases answer is either 1 or 2.

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

    All students have distinct programming skills!

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

    The second line of the query contains n integers $$$a_1,a_2,…,a_n$$$ ($$$1≤a_i≤100$$$, all $$$a_i$$$ are distinct), where $$$a_i$$$ is the programming skill of the i-th student.

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

Is the round unrated? Why the ratings are not updated ?

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

    Cause you are not rated in this round. You have to participate at least 3 contest in div2.

    and your solution was skipped-- probably you have break any Terms of agreement of codeforces.

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

Problem F is basically the same as BOI 2017 day 2 "Cat in a tree"

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

Edit: I was mistaken, please ignore.

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

If I modify problem A to..like find minimum number of teams you can form if no two students i and j such that |Ai-Aj|<=k may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than k).
So if N be the no of students then I can solve it in O(NlogN + Nk^2). is there ant faster approach if any one can suggest???

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

    Maintain a sorted array. Pick the first element(lets say a), then find the upper bound of a+k. Keep on doing the same thing for this new element until you reach end of array and also maintain the elements which have been allocated a team. Pick the next element in the sorted array which has not been allocated a team yet and repeat the above steps and increment the number of teams. This approach should be O(NlogN).

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

      No worst case complexity of your idea is O(N^2) Consider the case of N consecutive numbers with k=N;

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

        How?

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

          just apply your idea and see... pick your a(first element of sorted array) in search of a+k (i.e. a+N here) you will traverse the whole array(end of array) but you will not find it.. Note1 you have picked just 1 element in 1 traversal do same for 2nd, 3rd and so on... so N(N+1)/2... O(N^2)complexity……. also Note2 you can't say here for this very case to use binary search(however here may work) bcz in general solution binary search will not work.

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

            I won't traverse the whole array. I would just binary search and why would it not work in general?

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

              not work means complexity will become even worst bcz at every such a+k you need to do binary search prev=a; curr=a+k; next a+k+k;..... so on and every time cost is logarithmic time. Also there might be case that a+k doesnot exist but a+k+2 or a+k+5 exist here these will be included in the same partition but then how you will handle those cases using binary search.... Just think once what is your complete idea and check the complexity... once done I will be thankful and love to know that.

              → Reply
»
7 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Why have the rating changes been temporarily rolled back ?

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Stop naming test cases as "queries", ffs.

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

    This is not the first time you are saying this. But I don't think it makes any difference. It is okay until and unless it is not creating any confusion in the problem statement. Isn't it?

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

So when on earth can our rating be back?

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

I got plagiarism mail for the following solution coincided https://codeforces.me/contest/1249/submission/63187125 with another guy solution. However my first accepted solution for this problem was https://codeforces.me/contest/1249/submission/63184980. So the thing of plagiarism, I guess is completely irrelevant.

→ Reply
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it +20 Vote: I do not like it

Is it ok, what a few participants 1600+ rating got it updated after contest?

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

i try to solve D1 by using activity selection problem but it gives me WA on test case 14.

so i would do activity selection for K times and of course for each activity selection it will gives you as many as segments which not intersect with each other.

if you do it for K times then you will get points which covered at most K times, i couldn't think the corner case for my solution.

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

Can someone please check my F code. Its failing on the 38th case. https://codeforces.me/contest/1249/submission/73195435

→ Reply