vovuh's blog

By vovuh, history, 5 years ago, translation, In English

Hello everyone! This round will be a little bit special because it is composed from the problemset of Saratov school elimination stage to the all-russian olympiad of school students. The problems were invented and prepared by Alexander fcspartakm Frolov, Ivan BledDest Androsov and me, Vladimir vovuh Petrov. Good luck to everyone!

UPD: Thanks to Daria nooinenoojno Stepanova and Danila sad101010 Smirnov for testing!

UPD2: We will open solutions to view and start the hacking phase a little bit later because the school elimination stage is not over yet. We will open all in about two hours. Please don't discuss any solutions during next two hours.

UPD3: Now you can discuss problems.

UPD4: Editorial is published!

<almost-copy-pasted-part>

Hello! Codeforces Round 587 (Div. 3) will start at Sep/21/2019 10:05 (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
  • +112
  • Vote: I do not like it

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

Is it rated for all problem XD

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

    Enough with that already. Instead of being sarcastic, why not prepare a round yourself? :)

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

      Because cf only allows to prepare contests for experts and higher

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

        Numb DESTROYS kocko with FACTS and LOGIC.

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

    Please read upstairs first

»
5 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

funny

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

    Rip. My problem D in ECR 73 got hacked only because I didn't use fast printer. Sad the test cases didn't catch that.

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

Excited for my first contest :)

»
5 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Too early

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

    But this is suitable for Chinese people XDDDD

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

I hope the problems are sorted by difficulty:)

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

How and when can I hack others solutions? Morning I was searching for that option in educational codeforces. Didn't get it. So someone give detailed description of how to see and hack others code please.

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

I missread it as "Thanks to Smirnoff for tasting!".

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

So if you rating is more than 1600 then you will be unofficial.
Otherwise, you must be a trusted participant to be in the official table. However, even if you are not a trusted participant and have ratting less than 1600 then the round will be rated for you.
I did not get it. Can a participant not be in the official table but his/her rating changes?
Or there is an official table separated from CF?

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

    Basically when you switch from unofficial to official standings, in addition to removing non-div3 participants, it will remove all non-trusted participants. However non-trusted participants will still be used for rating calculations. So to simply answer your question — Yes, it will be rated for them but they will only be visible under unofficial standings

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

I hope I will start with Expert on CodeForces.

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

    Another Candidate master , making an alt account , waiting for people to reply "Wow you did it" after the contest.

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

hoping to gain rating!

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

Finally Div-3... Want more contest of Div-3.. In fact one in every week....

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

wonderful

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

Another contest as i have lessons (not computer) in the school... That's terrible...

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

Damn I just woke up

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

A similar problem. Similar to problem E.But I am still unable to solve E2

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

Why is sum of area of intersection = area of original rectangle not working in C :((

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

    you will also need to subtract area of the intersection of the intersections as that will be counted twice.

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

Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).

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

In D, I have taken the difference of every element with the maximum element of the array. Then took the gcd of all the values which is the minimum number of swords each person will take. Then the answer will be the number of persons and swords each person will take.

Why I got the WA in test case 5?

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

    I did the same. But remember to filter out the '0' values while finding the gcd.

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

    I got the same firstly.

    Expecting test smth like:

    4

    1 1 5 9

    try it.

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

    using x, y, z — notations from D;

    x = max element of the array;

    z = gcd(z, x — a[i]), i = 1..n;

    y += (x — a[i]) / z, i = 1..n;

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

    This is not true number of swords is right in your case bt the number if people is sum of the difference of each element with maximum divided by the number of sword

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

Dat feel when you start from C...

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

    Totally agree, I skipped C without thinking once I saw these rectangles in the problem and start solving (D) xD

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

No hacking phase ?

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

How to solve F?

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

Odd, is there no system tests? Usually the standings say "System testing" but now it just says "Final standings".

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

How to solve E?

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

problem E1 wrong test 1??? :(

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

Is F was lazy propagation

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

Not able to understand D at all. To much words and entities.

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

Come on, guys, stop discussing problems, please. The elimination stage in Saratov is still not over.

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

It was good contest. Thank you for all. btw, How long do we have to wait to be able to submit code?

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

Wouldn't it be more logical to start Div. 3 two hours before the end of the elimination stage, so that everyone would finish at the same time?

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

    Yes, this is more logical. I didn't knew when the elimination stage starts and ends and thought that all is ok.

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

      Since the comments under the announcement are probably the only place where problem discussion may take place, I think it may be reasonable to hide it until the end of the elimination stage (if it is possible).

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

Late for 1 minute. T_T
Wait to submit my E2's code and hope that I will succeed.

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

How to solve C? I tried so hard and got WA on test 11 :( It's really disappointing. After so much hard work couldn't get the AC.

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

    I also got WA on test 11 for my first submissions. For me it was because I had calculated the area of overlap between the two black papers, but didn't check that this overlap was within the white paper.

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

    Deleted

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

    You need to find areas of intersections. Between first and second, first and third, and between all of them. Then if S(1, 2)+S(1, 3)-S(1, 2, 3) < S(1) -> Yes, else -> No

    img1

    You can find area of intersections using intersections of projections. Notice that rectangles intersect when both x, y projections intersect.

    img2

    Here is my submission 61021591

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

When hacks will be available?

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

why this output is wrong in problem B test 3

69 1 4 2 5 6 3

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

      Okay, if you need an explanation, here it is:

      Your permutation is $$$[1, 4, 2, 5, 6, 3]$$$. So durabilities of cans in order you will knock them down are $$$[5, 4, 4, 4, 5, 5]$$$.

      So the answer by the formula is $$$(5 * 0 + 1) + (4 * 1 + 1) + (4 * 2 + 1) + (4 * 3 + 1) + (5 * 4 + 1)$$$ $$$+ (5 * 5 + 1) = 1 + 5 + 9 + 13 + 21 + 26 = 75$$$. $$$75 > 69$$$ so firstly you're printed wrong answer and secondly it's greater than author's answer.

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

How to solve E2 ?

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

    I did it using binary search. for each i we are writing numbers from 1 to i. So first I did a binary search on i such that when I write from 1 to i+1, the number of digits exceed k. Now we have to find the number j between 1 and i+1 such that writing till jth number makes the number of digits greater than k. again binary search on this. Once we get j we can easily get our answer. you can refer to my code here

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

    Write down each block in a column and consider all the blocks that the last number has the same number of digits as the Big-block.

    // Big-block 1
    1
    12
    ...
    123456789           // the longest block in Big-block 1
    
    // Big-block 2
    1...910
    ...
    1...910...99        // the longest block in Big-block 2
    
    // ...              // ...
    

    The number of Big-blocks is about 9, so we can find k in which Big-block easily.

    Then the right block can be found by using binary search. I preprocessed the longest length of block in each Big-block and the sum of digits of all Big-blocks.

    Now this problem 1216E2 - Числовая последовательность (сложная версия) was translated to 1177B - Последовательность цифр (усложнённая версия).

    Here is my solution 61007196 and wish it can help you more.

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

when can i solve it again

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

For C, can someone explain how the answer is "NO" for TC 11:

50 100 100000 99000

13 4654 999999 1000000

0 0 1000000 45654

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

    Dunno why you ask. White rectangle is almost inside first black rectangle except a little part near point (0;0) and the 2nd rectangle covers this part.

    Possibly you should notice that it's 999999 that is not 99999

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

How to solve problem F?

I think it can be done using dp and segment tree with lazy propagation but am a little bit confused.

what should the dp state be and how to use segment tree efficiently with dp?

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

    Think of the problem like this — there are $$$n$$$ offers for intervals $$$[l_i, r_i]$$$ and the $$$i$$$-th offer has cost $$$c_i$$$ (this problem is only a special case). We want to cover all indices $$$1$$$ to $$$n$$$ and choose the cheapest such set of intervals.

    Now here's the dp state: let $$$dp[i]$$$ denote the minimum cost to cover indices $$$1$$$ to $$$i$$$ with intervals that have their right point $$$\le i$$$. The answer is $$$dp[n]$$$. The base is $$$dp[0] = 0$$$. How do you transition?

    To find $$$dp[i]$$$, you must cover indices $$$1, \cdots, i - 1, i$$$. Since in $$$dp[i]$$$ we're looking only at intervals that end $$$\le i$$$, obviously, we must choose at least one interval that ends at index $$$i$$$ to cover it. Also, we choose exactly one such interval, because if we chose more than one, we can pick the longest and that won't affect the answer. Which interval should we choose? Let's iterate on all possible choices for that — let's pick an interval that ends at $$$i$$$ (call it $$$[l, i]$$$) and say it has cost $$$c$$$. Once we have picked this interval, we just have to ensure that indices $$$1, \cdots, l - 1$$$ are covered because this interval covers the indices after $$$l - 1$$$. What is the minimum cost of this subproblem? It's not $$$dp[l - 1]$$$, because there could be a cheaper configuration with intervals that end after $$$l - 1$$$ but before $$$i$$$. To cover those possibilities, we take the minimum of $$$dp[l - 1], dp[l], \cdots, dp[i - 1]$$$ (call it $$$m$$$). So the optimal cost of doing this is $$$m + c$$$. And $$$dp[i]$$$ is the minimum of this expression over all intervals that end at $$$i$$$.

    We can store at each index a list of intervals that end at that index, and to support finding $$$m$$$ quickly, we can maintain a segment tree that stores $$$dp$$$ values of each index and allows us to find minimum in a range of indices.

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

      Thank you for the explanation.

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

      In addition, since all intervals have identical lengths (except those near the bounds, but this is not really a problem), you can maintain a sliding window minimum to solve the problem in $$$O(n)$$$.

      Edit: a 21-liner getting AC — 61020296

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

Can any one tell why my solution got failed on test1 61010239

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

    your answer is 2 3 1 , but it's wrong , the correct answers are 1 3 2 or 3 1 2 .

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

deleted :)

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

I wrote a segment tree to solve problem F, and I also know that it can be solved with something like the sliding-window. But I found many solved it without using any data structures example. I'm just wondering how that works.

Can someone please help me with that?

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

How to approach E1?

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

    Process the number of digits of i and get the prefix sum, then use a binary search to find i which takes up the k-th posithon. Finaly the answer is the k-sum[i-1]-th digit of i.

    Here is the commit which is my solution for E2. If you are interested in E2, Link it.

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

Is E2 Digit DP?

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

    I solved it with binary search and some mathematical calculations.

    If you are interested in my solution, hope the commit-544591 can bring you some of the inspiration

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

RIP my problem E :<

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

What's the hack for C?

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

    one of them =)) 0 0 3 3 5 5 6 6 0 0 4 4

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

    your solution is WA with follow case 2 6 8 8 1 2 3 3 1 3 10 10 sorry, I will hack your solution :(

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

      Hi. Could you please tell me where the mistake is in my code?

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

Submitted a solution for problem D with complexity n*log(10^14) + sqrt( 10^14 ) This gave a TLE in java in test case 16 during contest Same code I rewrote in c++ after contest. It passed all pretests.

Time limits too strict for Java

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

    you can solved it with complexity n*logn time

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

      O(n) is easy to! you just get the maximum number and find the GCD of all (maximum — a[i]) and output sum(maximum — a[i]) / GCD and GCD

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

It was interesting that my exact the same solution for A was TLE in PyPy3 but accepted in Python 3. Any idea?

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

    Try to avoid using += with strings in Python, when you add chars multiple times. There are some optimizations thrown in here and there, but it sometimes happens that this method's performance degrades to $$$O(n^2)$$$, since each time you append a couple of chars this way, a brand new copy of the whole string may be created.

    Instead, you can put all strings into an array, and then write something like s = ''.join(a), which is definitely faster.

    Update: now your code passes in 140 ms — 61033581

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

      Good to know! Thank you so much!

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

Same solution, just change in indentation and variable names, was expecting same handle too! :(
sol1: 60988370 sol2: 60998975

MikeMirzayanov sir, please look into the matter.

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

Hi MikeMirzayanov, I had used unintentionally public online compiler(ideone.com) in middle of contest for solving Question D. Here is link to my solution on ideone which I had used in middle of round unintentionally. But there is message from system saying that my submission is exactly same with some other guy. Here is his solution which is exactly same as mine. I think he has taken the solution from there only because I don't know that guy. It is my mistake to use online public compiler which I will take in account for further codeforces round.

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

i think my solution 60995513 for the problem 1216F and solution 60994761 of tuan52 just a coincidence, Because each problem can have different ways, the same idea is inevitable. tuan52 and I use queues so we can have the same idea, can't say we copy each other's code

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

    The same idea causes similar solutions but not exactly the same code with only the changes in indentation and variable names. Don't you think your solutions are somehow too similar?

    Sorry if I'm wrong.

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

      i don't know why, but I'm sure he and I don't know each other

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

This is regarding the notification I received having similar code to some other codeforces user. For problem B, the code to keep track of indices is available here https://www.geeksforgeeks.org/keep-track-of-previous-indexes-after-sorting-a-vector-in-c-stl/ and the rest logic is highly vulnerable to probability of being same.

Also I did use ideone on public setting unintentionally http://ideone.com/KvSYMv but thought this is highly unlikely to be copied since almost 100+ submissions are done every minute there.

Anyhow,the system may realize, I have clear early submission & please remove the warning on my profile.

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

I received a talk from System saying that my solution 60971083 for the problem 1216A significantly coincides with solutions Arianfk/60969857. It's just a coincidence. I am surprised that the two solutions are almost the same. I wrote the code myself without reference to any third party code. 1216A is a simple problem that can be solved with only a few lines of code, and I think it is true that the similar solutions may occur.

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

This is regarding the following system message I received.
Attention!
Your solution 60996009 for the problem 1216C significantly coincides with solutions meet29/60996009, gagan_6730/60997664. Such a coincidence is a clear rules violation...

Upon investigating (if it can be called that), I found that it's the exact same solution. The only thing is that my submission was made earlier. I could think of no reason how my code could have been leaked as I never use any online IDE, just editors, and compilers on my machine. But, later, I recalled that I had received a new sign-in mail while the contest was running. I had thought at the time that it was probably a delayed mail for my own sign-in (OS and browser were the same) so I didn't think twice about it. Now, that is the only thing that makes sense to me. I don't know for sure if that is what happened i.e. my account was compromised, but that is the only logical explanation to me. The IP did turn out to be different.
The timeline of events was as follows — I submitted, then I received the mail about a new sign-in, and then the copied solution was submitted.
I don't know if this would constitute as an unintentional leak, but if it would, I take responsibility for any penalties. Regardless, I have taken the necessary steps to secure my account so that such an instance does not repeat (if this is what had happened). Will surely be more careful from now on. Lesson learned, the hard way.

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

Clarification of my flagged plagiarism submission:

Your solution 60992562 for the problem 1216C significantly coincides with solutions anonymous-420/60989907, CandyZack/60992562.

I have used a part of the code from stackoverflow, the link is below. https://stackoverflow.com/questions/27152904/calculate-overlapped-area-between-two-rectangles

Because both the submission uses the same code form external site, I urge you to remove the plagiarism on my submission.