Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Vovuh's blog

By Vovuh, history, 5 weeks 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 ZeroAmbition 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 PikMike Piklyaev, Maksim Ne0n25 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

»
5 weeks ago, # |
  Vote: I like it -48 Vote: I do not like it

Is it rated for all problem XD

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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

funny

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

It is almost midday when the contest starts and sort of every student is supposed to have classes at that time.

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

Excited for my first contest :)

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

Too early

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

    But this is suitable for Chinese people XDDDD

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

I hope the problems are sorted by difficulty:)

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can hack others after the contest and it lasts 12 hours

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

      Yeah, I should go for hacks and then what?

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

        if you can hack someone you will be given 100 points

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

          In Div. 3 and Educational Rounds you don't get any points for hacking.

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

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

»
5 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

I hope I will start with Expert on CodeForces.

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to gain rating!

»
5 weeks 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 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

wonderful

»
5 weeks 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 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Damn I just woke up

»
5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

  • »
    »
    5 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Dat feel when you start from C...

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

No hacking phase ?

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

How to solve F?

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hacking phase will start soon, you have to wait till it's over.

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

How to approach E guys?

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

How to solve E?

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

    You can try to solve 1177B - Digits Sequence (Hard Edition), as they are quite similar.

    Hint: Try to calculate number of digits for 123456789101112.... by breaking them down into 1-9,10-99,100-999,1000-9999,...

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

      My thoughts were on the same track but couldn't come up. I'll try this one.

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

    For E1.
    k is small. We can process the number of digits of i as d[i], and process the perfix sum of d[i] as sum[i]. Then for each k, we can use binary search to find i which contains k-th digits.

    For E2.
    Link my solution, another comment, here.

    Hope it can help you.

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

problem E1 wrong test 1??? :(

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

Is F was lazy propagation

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too

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

    It just meant that you have n types of sword. Each type has exactly x swords . That means suppose you have 3 types of swords . And each type contains 4 swords so you have total 12 swords.

    Then there will be total y people and each will take z swords of same type. That means if anyone take from type one, he has to take all his z swords from type 1.

    Lastly, in the input you will be given the information of remaining swords of each type. That means y people may not take all the swords.

    you have to find minimum how many people if each one take z swords the input is valid. That means you have to find y and z.

    That's the question .

»
5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hopoe unrate TT

»
5 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried using co-ordinate compression. Click here to read about it. Here is a link to my submission.

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

    Deleted

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When hacks will be available?

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    69!=1+5+9+13+21+26

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

      I assume that you are wrong, if I've understood the problem correctly, for this output:

      1 4 2 5 6 3
      
      69=1+6+11+13+17+21
      
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Second term is not 6. If you take a[4](equal to 4), it will be 4*1+1=5. Right answer is 6 1 3 5 2 4

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

          a[4] is 4 with numeration starting from zero. But according to problem statement we have numeration starting from 1. I still can't undestand why this output is wrong

          UPD. Actually if I took second barrel wrong, anyway I have 69 as answer , seems like it is still correct sequence.

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

            a[4] is 4 with numeration from one too

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

              Uhh... seems like I understood. Thank you

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

      (5*0+1)+(4*3+1)+(5*1+1)+(4*4+1)+(4*5+1)+(5*2+1)=1+13+6+17+21+11=69

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

        True, but we need (5*0+1)+(5*1+1)+(5*2+1)+(4*3+1)+(4*4+1)+(4*5+1)

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

          this representation is permutation of my representation

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      5 weeks 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks,maybe i miss understanding the problem

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

How to solve E2 ?

  • »
    »
    5 weeks 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 weeks 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 - Numerical Sequence (hard version) was translated to 1177B - Digits Sequence (Hard Edition).

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

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

when can i solve it again

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

Great round!

»
5 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the explanation.

    • »
      »
      »
      5 weeks 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 weeks 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 weeks 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 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

That was good :)

Did you get + or -? comment it ...

»
5 weeks 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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to approach E1?

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E2 Digit DP?

  • »
    »
    5 weeks 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 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

RIP my problem E :<

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

What's the hack for C?

  • »
    »
    5 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can solved it with complexity n*logn time

    • »
      »
      »
      5 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just sort and you are done

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

i remember when i meet the problem c in france ioi and i skipped it !

»
5 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good to know! Thank you so much!

»
5 weeks 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 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Even though I gained rating,but I have to blame this round. For Problem C,my friend write a wrong solution and submit his code. But he passed all the pretests!!! Do you know why he was wrong? We know that we need to consider all the edges of the white rectangle. But he only considered the rows of the white rectangle,and he passed all the pretests!!!! Why?This is amazing,man.What a shame of the pretests.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

always waiting for a div3 but my rank always drop after participating in them :( after all thanks for a good round !

»
4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

do you know is there any key to problem E1,which is also called the explanation to that problem?

»
4 weeks 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.

»
4 weeks 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.

»
4 weeks 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.

»
4 weeks 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.