Vovuh's blog

By Vovuh, history, 3 months ago, translation, In English,

Hello!

Codeforces Round #486 (Div. 3) will start on June 1 (Friday) at 14:35 (UTC). It will be the third Div.3 round in the history of Codeforces. You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. 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.

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 Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for testing the round.

UPD: I also would like to thank step_by_step and eddy1021 for testing the round and help with it preparation!

UPD2: You will be given 6 problems and 2 hours to solve them.

UPD3: Editorial is published. Thanks to Mikhail PikMike Piklyaev for the help with translation.

UPD4:

Congratulations to the winners (official results):

Rank Competitor Problems Solved Penalty
1 volamtruyenkyii 6 196
2 IOI2018 6 238
3 Student_of_Husayn 6 303
4 Omoshiroi_ 6 311
5 Deadpool 6 313
6 AHDPIYKO 6 341

Congratulations to the best hackers:

Rank Competitor Hack Count
1 jhonber 70:-1
2 djm03178 61:-4
3 applese 53:-1
4 WAI95 41:-3
5 step_by_step 38:-5
6 greencis 57:-45

530 successful hacks and 401 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A AhmedMohamd-BeatMeIFUCAN 0:02
B S1mplest_gu1 0:06
C S1mplest_gu1 0:12
D volamtruyenkyii 0:23
E Ycrpro 0:19
F MuieEcaterina 0:49

I hope that you will like the problems. If the problems in this round are too easy or too hard, then we will adjust the difficulties in the next Div. 3 rounds.

Good luck!

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

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

It will be the second Div.3 round in the history of Codeforces.

Actually, this is third Div.3 after rounds #479 and #481.

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

Finally, Div.3 round :D

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


Can someone to hack CF rating?? +100 for successful hack. -50 for unsuccessful hack. Just reduce my rating by 1 point. 1600 -> 1599. Because my rating >=1600. So it is unrated for me. But I still want to participate.

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

If suddenly something does poorly with difficulties of the problems,

The grammar here is poor. I'm not quite sure what this is trying to convey, but perhaps

If the difficulties of the problems in this round are poor,

or even

If the problems in this round are too easy or too hard,

would be better.

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

    Thank you for correction, it's fixed now

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

    In fact, I think the difficulties were just about right, nice to have a bit more of a difficulty gradient than what we've seen before

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

Div.3 ! Round for Newbies like me :)

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

"if your rating is less than 1600, then the round will be rated for you."

+respect

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

can anyone explain the difference betwwen div2 and div3.Thank you.

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

    div 2 is rated for > 1600 and the problem is pretty hard and not too easy and for div 3 is rated for under 1600 and the problem pretty easy not too hard (you can check the past contest and learn from it)

    for full explanation -> http://codeforces.com/blog/entry/59228 Meow !

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

      Div 2 is rated for all participants less than 2100. There is no lower bound ( as u said >1600).

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

    Div 2 Rated for -infinity < Rating < 2100.

    Div 3 Rated for -inifity < Rating <1600

    Div 2 got some problems easy, some medium and some hard.

    But to help improve the newbies and others learn, CF invented Div3.

    Div 3 will contains majorly problems of easy and few medium difficulty.

    High Ratings to EveryOne !!

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

so excited <3 to be Expert, it is just 144 :/

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

Hope to be green lol.

it's just 6 points

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

If i never join the contest (unrated account), will this contest rated for me?

**I'm sorry for my poor english & question

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

    Yes

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

    May be not.

    As it's rated for only Div-3 ** trusted participants**. 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.

    N.B.: Read the blog properly.

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

      It is rated for all participants with rating below 1600, dude

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

      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.

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

      lol xD you need to read the blog properly.

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

Scoring?

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

    It's an ICPC style contest. All problems have equal weightage.

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

Suited for me....

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

?detaR tI sI

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

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

Hope that I will become expert after this round. :)

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

    you won't i bet

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

      Let me talk to you after the contest.

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

      Bro you was saying something :)

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

        It might look like I was rude and unprofessional but I did this just to make you really serious for this contest so it goes very nice for you. I commented the same on some other person also, so to give them huge confidence boost. Looks like it worked for you. Good luck for future contest also.

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

          Try to increase your contribution lol.

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

Thanks for this contest

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

Wow!! Already 8k. Gonna be challenging.

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

Is it Div.3 contest if only 3 contestants with rank below 1600 (out of thousands) have solved E and F in first hour??

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

    "If the problems in this round are too easy or too hard, then we will adjust the difficulties in the next Div. 3 rounds."

    Also I think that's good. It differentiates contestants more, than everyone solving ABCDEF and rating only by solve times.

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

Who thinks that 20 points of penalty are too much?

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

    That's standard ACM rules. I think it's fine because it encourages people to write correct code rather than fast code :)

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

Is it just me or somebody else noticed the mistake in question D!!??

in the output format they have said

"In the second line print m integers — the coordinates of points in the subset you have chosen."

but actually you have to print the numbers itself!! XD

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

    Well the numbers you print represent the coordinates

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

      many times they ask us to print the index so it kind of became confusing!

      and again i just asked does anyone else feel the same, just wanted to know how others think! Though no offense to the setters the problem was good!!

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

        Yes, they do mostly ask for the index, I agree. I didn't mean to offend you or something ;)

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

How to solve " Divisibility by 25 " ?

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

    find lastest 0, 2, 5, 7 in given integer. then we know how many swaps we need to make 00, 25, 50, 75 at the end of integer.

    but, you have to consider 0 being at the frontmost number of integer, which is a point i made a mistake.

    For example, if we are considering how many swaps we need to make 25 at the end of integer, and if 2 is the frontmost number of integer (before swapping), and if k 0s continue behind 2, (i mean, 200000235234 has five 0s behind 2, k=5), you need to swap k times more. So you can just add k at the answer.

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

      As you said that we only have to deal with the last set of 00,25,50,75 so for the given example we dont have to go for swapping the 0's.We can use the 2 in the 3rd last position and 5 in the 4th last position to get ans=5.I dont understand when will we ever face the problem of getting 0 as the leading digit?

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

        In testcase 8, in which I kept getting WA — 50267

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

          Did you take care of leading zeroes? The result cannot have any. Need to make extra moves to get a nonzero number to the front.

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

        500044444444442

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

    Solution for E: for each case of 00, 25, 50, 75: find the last digit of the case (_0 or _5) in the given string at the rightmost position and swap it to the end (ans += swap distance), then find the second last digit of the case (0_, 2_, 5_ or 7_) in the string at the rightmost position and swap it to the second-last position (ans += swap dist). Then try to swap starting zeroes (if any) with a non-zero digit (which must be at least third-last) (again: ans += swap distance). If the final string is a correct number then consider the 'ans' as a candidate for the shortest answer. Solution with regexes, Perl: 38862670.

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

great balance imo

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

How to solve D? m is less or equal 3, isn't it?

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

    Yup, but I kept getting WA

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

    Yup, the maximum size of subset is either 1, 2 or 3 :)

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

      why cant the max size be more than 3

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

        Because if you have 4 (or more) numbers, the distance between the 1st and 4th will be 3 times a power of two = 3*2^n, which isn't a power of two.

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

        Because 2a + 2b = 2c has a = b and c = a + 1 as the only integral solutions. Now, If u have 4 numbers then the distance between 1st and 4th will be 3 * 2a which is not a perfect power of 2.

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

    Feels bad when you figure it out right after the contest (:

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

    There are only 3 possible options:

    1) Just choose any one to get a set of size 1.

    2) Just choose any pair such that S = {x, x + 2d} for some x in the array, and some d such that x + 2d belongs to the array. It works trivially.

    3) Choose, if possible, for any element x in the array, the set S = {x, x + 2d, x + 2d + 1} since it's the only choice to maximize the size (It's not possible to add another one with difference 2^{d+2} since 2^{d+2}-2^{d} is a multiple of 3 and also consider that it also shows that is not optimal to choose different d's as pairwise difference), remember that all those elements need to be in the array.

    One can get all the information needed by mapping values to indices and just checking for a not null index in each try. Woof!

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

Enters Div2 rounds.. Solves A, B & C...

Enters Div3 round.. Solves only A, B...

What ??

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

Was it really a div3 round? Cuz it looked like a div2.

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

How is this possible that i have TLE when my algorithm calculates in O(n * 30) ?

38858406

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

    Every time you check in map you create a new entry, instead use .find(), it doesn't affect the map size.

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

      thank you

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

        Also use unordered_map so the find complexity is O(1) instead of O(logn)

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

          There are cases when unordered_map gives TLE while map passes. See this.

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

    Idk. I have passed with in 2.5s.

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

    I got WA in same test case than sorted it and got AC till now

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

The sums were hard sir. Please make it easier next time for rating 1600 and below.

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

Yes, we know about fast solution to the problem F (with Li-Chao tree). But in hard version this problem is too complicated even for the last problem of the div3 contest. This why we prepared this problem with such constraints.

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

    I thought it was simple dp?

    I mean just dp without using any others data structures

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

      Yeah, dp solution have O(n^2) time complexity and this is accepted. But there are exists some other solution with dp and convex hull trick (also known as Li-Chao tree) which have time complexity O(n * log^2 n).

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

        Yes. My bad. I didnt read carefully and though you was complaining about the difficulty of it

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

        Solved it using Li-Chao tree. Learned a new thing. thanks!

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

Can anyone say why did I get runtime in this code Problem B (Test 7)? Code
I had made 10 submission to get it accepted, which resulted in huge penalty...

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

If the problems in this round are too easy or too hard, then we will adjust the difficulties in the next Div. 3 rounds. Again, in the next round :(

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

Will greedy strategy work for 988E - Делимость на 25?

I mean a number is divisible by 25 if only it ends with 00, 25, 50, 75. So from the end we search for last digit (i.e. 5 of 7**5**) and then for second last digit. If at last there are leading zeros then we make the first non-leading zero number as first.

I got WA on test 23, but I feel I missed corner case!

UPD: Yes, it was a corner case :'(

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

    23 was the first one with a 2 digit input (I was using python and got a runtime error when checking for the leading 0 afterwards).

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

How to prove that in the problem D: 1 <= m <= 3 ???

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

    Assume x < y < z satisfy that y - x = 2a, z - y = 2b and z - x = 2c. Then 2a + 2b = 2c. Notice that c > max(a, b), so 2max(a, b) divides 2c, and therefore it divides 2a + 2b, so it must also divide 2min(a, b), implying that a = b.

    Then any three number subset satisfying the condition is an arithmetic progression. Therefore if w < x < y < z have all differences powers of two they must all be in arithmetic progression. This is impossible because then z - w = 3(x - w) and z - w isn't a power of two as it's divisible by 3.

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

    assume there are four integers a<b<c<d satisfying the condition. let b-a=2^k, c-b=2^l.

    c-a=2^k + 2^l must be a power of two, thus k=l.

    c-b=2^k.

    similary, d-c=2^k

    then, d-a=3*2^k, must be a power of two, but is not.

    So, 1<=m<=3

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

    try proving with contradiction, what if n==4? (show that it cannot happen by using subtraction of bit pattern of numbers).

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

    Suppose we already have the sequence a[1],a[2],...,a[k]. It is clear that it must be (a[k]-a[k-1]) = (a[k-2] — a[k-3]) = ... = (a[2] — a[1]) = 2^d, d > 0. Try it on 3 numbers, suppose we have a sequence a1,a2,a3 and a2 — a1 = 2^a, a3 — a2 = 2^b, with a <= b. Then a3 — a1 = 2^a + 2^b = 2^(b-a) * (2^a + 1), which is a power of two only in case when a = b. So the sequence should be like k,k+2^d,k+2^d+2^d and so on. Consider an example now with four numbers in sequence, a1,a2,a3 and a4. (a2 — a1) = (a3 — a2) = (a4 — a3) = 2 ^ d Then a4 — a1 = 3*2^d which is not power of 2. The same goes for m > 4.

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

Missed problem E by just a minute. Contest was over just when I was about to submit problem E :(

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

In Problem C, my this — code 1 solution got TLE on test 5. I used set_intersection function to find common sum in any two sequences.

Later I wrote this — code 2 in which I have just done linear comparison between two sequences. I couldn't submit it in time.

Can anybody tell if code 2 time complexity will be less than code 1 or not? Also is there any even faster method to do the problem. Thanks!

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

Why test case 8 in problem E (50267) the answer is 5?

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

    50267 -> 52067 -> 25067 -> 20567 -> 20657 -> 20675

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

    Damnn I too kept getting WA there. I couldn't come up with a test cases like this. The point is in 50267, you want to get the 5 to the right .In doing so your intermediate number is 05267 which has a leading 0 and thus isn't accepted. You need to do another swap — (0,1) which will make all the intermediate numbers not have the leading 0.

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

Hmmm...

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

In B I think if any code print "YES" for {2,p,pp} then it should receive wrong ans. cause statement says if "reorder" impossible it should print "NO".

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

Contest of maps and sets

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

I could only do A, B, C and D. (Before system testing) And I think the difficulty of the questions are absolutely fine !

You end up learning more if there are two questions out of your reach, rather than just 1 or doing all of them. I definitely appreciate the difficulty of these problems. Please don't water it down for the next contest.

My only complaint here is that your previous contest had one question from every topic — DP, graphs, binary search, STL, number theory, etc ... Whereas the other two Div 2 contest didn't cover as many topics.

We got STL and I guess you could call D some kind of number theory where you observe the answer is never more than 3, but still we didn't get a pure number theory one like your previous D — Multiply by 3, Divide by 2 did ! There were no graph problems either.

In short, my feedback is this — The difficulties are great, pre-tests are great, Just add more topics :)

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

Why are there some guys hacking themselves? lol

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

    because they know they will soon be hacked by reds or etc..

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

    Or they would anyway fail the main tests

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

A div3 contest with 3 div2 problems for me :(

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

In D, my mistake was printing a long long int instead of an int. Naturally, long long int wasn't needed. But is this a legitimate reason to give a WA?

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

    That's really strange..

    I used printf("%lld", ~) and get AC

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

    Well you not print any solution, look carefully~ Just try it to run locally

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

    That wasn't your mistake — it's just a slightly confusing error message. Your code outputs 0 for that test (as 42 isn't a power of 2) without a second line which causes the error message seen.

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

      You're right. Why was the correct output 1 42, when 42 isn't a power of 2? I can't have that in my subset right? Or can I?

      UPD: When the max size was 1, I printed any element. Just got AC. Why is this correct though?

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

        It's given in the problem statement, a subset of size 1 satisfies the given condition.

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

          Didn't read the problem statement carefully. Thanks

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

please explain solution of C??

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

    While you reading the input get the sum of the numbers from the current array. Every time check if the current sum has been encountered before. Now traverse the array once more and map this value (sum — a[i]) with arrays index, and its position in the array. Check out the code: http://codeforces.com/contest/988/submission/38843860

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

    For each set if elements, first calculate sum of entire set. Then calculate difference matrix by subtracting each element from sum. Use a global map(common for all the sets) for hashing and storing indexes, and check whether each difference element was obtained earlier or not. If yes, you have found common sum producing elements in the 2 sets!

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

      I thought about this approach, but wouldn't creating a difference matrix take O(ni) time for each sequence. and we have k such sequences, so its O(k*ni). Wouldn't it time out?

      Also what does global map store exactly? Would be helpful of you to elaborate. Thanks

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

        No it wouldn't time out as k*n<= 2*10^5

        Global map stores the difference (between sum and actual element in all the sequences) as key. Lets say I have difference D obtained on sequence i for a element j, I map the difference D for i and j. The map is of the form map<int,vector>. vector stores for i and j. Later if I find the same difference for seq i1 and element j1 in it, I have stored earlier occurrences of the same difference in map. See my submission for implementation! Hope it helps.

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

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

D --The size only can be 1,2,3 (but why?) Maybe the "conclusion promble" in div3 is a little bit weird?

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

    Let A = C + 2a, B = C + 2b, A ≥ B.

    According to the problem, A - B = 2a - 2b = 2x should hold.

    Divide each side by 2b. The equation would be 2a - b - 1 = 2x - b.

    1) If x - b = 0, then 2a - b - 1 = 1 -> 2a - b = 2 -> a - b = 1 -> a = b + 1

    2) If x - b ≠ 0, contradiction since left side is odd and right side is even.

    So there are at most 3 which is C, C + 2a, C + 2a + 1

    IMHO, this kind of problem is little challenging for div3 but worthy at the same time.

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

The round was cool! I'll wait a new round.

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

Couldn't debug the runtime error in my solution of B !. Someone help : 38838754 Problem B : RUNTIME ERROR ON TEST 7

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

    Try submitting it using the C++17 Diagnostic compiler, it might help in debugging.

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

    I had the exact same issue. The error is in the comparator.

    One of the requirements for a comparator is that

    If comp(a,b)==true then comp(b,a)==false

    One way to fix it is to return false if a == b before you check if a is in b.

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

      One way to fix it is to return false if a == b before you check if a is in b.

      I didnt get this, what's the need for that?

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

    http://codeforces.com/blog/entry/59770?#comment-434966

    For your case,

    bool comp(string l, string r){
    	return l.length() < r.length();
    }
    
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    return l.length() <= r.length(); — is not right. return l.length() < r.length(); — is right.

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

      When both strings are of equal length, they must be exactly same, for this ques. So, it shouldn't matter whichever comes first. Can you explain why "=" should be removed.?

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

        Because If comp(a,b)==true then comp(b,a)==false is a requirement for the comparator.

        If two strings are of the same length, then comp(a, b) and comp(b, a) will both be true, which breaks the requirement.

        On the contrary if you remove "=", then comp(a, b) and comp(b, a) will both be false, which doesn't break the requirement.

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

    bool comp(string l, string r){ return l.length() <= r.length(); } Don't use = int your comparator function.

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

Can someone tell me what's wrong with my code? 38862572 It is getting a runtime error in testcase 7 But when one of my friends submitted the same code from their account after the contest, they got it ACed I made it a point to compare both codes on an online text comparator and it gave both codes are same.

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

What is the complexity of ACd solution for problem D?

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

There are unrated peoplr in the official standing

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

Hi all, I am new to CF contests. I am not able to locate the hacking option on my dashboard. The 'hacks' tab also has no such option for me (it only shows hacking results involving other hackers and defenders). Can someone help me out with this? Thanks.

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

    Click on any solution (from the standings, the status tab, etc), you should see a hacking option

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

      Thanks, how do I locate my room though? Or I can hack ANY solution?

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

    You can navigate to a submission from the standings page, and you should see a button that says "hack it" above their solution.

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

      Thanks, how do I locate my room though? Or I can hack ANY solution?

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

        In a typical CF round, you would only be able to hack people in your room, but you may hack anyone in this round.

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

Unexpected verdicts again, hacks #456187 and #456189.

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

in problem E for sample case 1 :5071 i think answer should be 1:-
5071 to 1075

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

Test 27 of problem D is made to fail if unordered_set is used, why is that a thing?

EDIT: It fails with C++14 and passes with C++17, fuck me I guess.

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

    I think it's anti-hashmap test(I guess someone intentionally generated such test).

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

      How could I have known, so basically I can't use unordered_set in a contest? Or I should write my hash function I guess lol.

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

        My solution with the STL map passes.

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

        Welcome to Educational Rounds!

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

        Xor with a random constant before inserting the number into unordered_set also work.

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

    idiot

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

      What?

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

        unordered_set is O(n) // why you use it instad of set log(n)

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

          actually unordered_set is faster than set (some times)

          in some problems your solution won't pass unless you use unordered_set

          so ,, no one is an idiot

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

        my team's name in ACM is 2 idiots

        it is good thing for you :)

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

thank you for very nice problem set. Had a really great time :)

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

Is problem E somehow related to Digit DP ??

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

    i dont know about dp solution but i think E can be solved without dp

    result is min(case25(), case50(), case75(), case00()). Here case25() is a simulation function that return minimum swap to make the last 2 digit is 25, if it cant make it, return infinity. If result is infinity print -1.

    however i'm getting WA because i didn't read the problem statement carefully "your number can't have leading zeroes"...

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

someone give me hack test for problem E. I want to know if my solution is correct .. thanks :)

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

I like the idea of harder D, and E(i really think they are harder than the last Ds and Es of Div. 3) so people who just know how to implement fast are ranked lower then the ones who are skilled at getting fast ideas for problems, but implement kinda slower, so those programmers can get rating a bit faster, but also because you don't finish the round in 1 hour. Super Cool problems nonetheless !

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

i think 2:30-hours Could be better for today

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

Why will this code return 0xC0000005(Index out of bound) instead of 0?

#include<bits/stdc++.h>
using namespace std;

int n;
string ss[110];

bool cmp(string s1, string s2) {
    return s2.find(s1) != -1;
}

int main() {
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 0; i < n; ++i)cin >> ss[i];
    sort(ss, ss + n, cmp);
    return 0;
}

The input data is as follows.

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

    I guess cmp was a bit not properly

    cmp should return whether s1 should be in front of s2 in the result array or not according to your sort rules.

    when a=b="aaa",cmp(a,b) and cmp(b,a) both be true.

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

      I don't think so. For example, in integers comparison, we use the cmp function:

      bool cmp(int a, int b){
          return a < b;
      }
      

      Even if a == b, and cmp(a, b) = cmp(b, a) = false, our program will return right result, isn't it?

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

        My fault.

        But when cmp(a,b)==cmp(b,a)==true, sort will TLE.

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

          Yes, you are right. So, I am confused to why that code will return 0xC0000005.

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

            Indeed,sort use so called quicksort when n>16

            while (true) {
                while (*__first < __pivot) // here always true
                    ++__first;
                --__last;
                while (__pivot < *__last) // here always true
                    --__last;
                if (!(__first < __last))
                    return __first;
                iter_swap(__first, __last);
                ++__first;
            }
            

            Your cmp may cause out of bounds, so when n>16 it will RE.

            UPD:use stable_sort instead?

            Chinese version:sort在n>16的时候用通常意义上的快速排序,对于a<b且b>a这种情况(非偏序集?),指针就跑飞了~

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

      I think that you are also a Chinese, how about we talk in Chinese?[斜眼笑.jpg]

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

is hacking phase will affect the standing result ?

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

    Yes,for only those who have their solutions hacked,going by the rules of educational rounds.But those who had successful hacks won't be affected.

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

Why does the contestants who are blue or higher have * marked before their name in status?

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

    They are out of competition participants and the round is not rated for them.

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

my rating has not been updated after div 3 why please help

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

I'm new to CF contests. Kindly help. Do the final standings that are currently displayed include hack scores too? (+100 for a successful hack and -50 for unsuccessful hack) How do I know if my solution has been hacked? Also, tentatively, by when will the ratings be updated?

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

    If your solution is hacked,you will be able to see it in your submissions.It is informed on the moment whenever your code goes hacked.

    The ratings update takes some time..But it is quite sure to be updated within an hour or two.

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

      Do the final standings that are currently displayed include hack scores too? (+100 for a successful hack and -50 for unsuccessful hack)

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

      You may want to use CF predictor extension in Google Chrome.It shows you an assumption of what your ratings increase or decrease will be.It has always given me perfect rating change.

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

    just In the Div2 and Div1 contests you can hack during the contest and get points ,and they show you a window that tells you if u have been hackd . In the educational competitions and div3, you can only hack after the contest is over and the hack results didnt affect your points. For the rating it may take from half an hour to 4 hours Or more to be update.

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

      But if someone's solution is hacked, his solution won't be counted as correct and he won't get full points for it right?

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

        right

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

          though if someone hacks successfully he won't get points for it? what is he hacks incorrectly? will he get negative points?

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

            It is supposed to be that way.Still, there is no update in the standings yet for the one who has attempted a hack.I think the score for the hacking attempts will be rejudged during final system tests.

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

        Actually he will not get any points for it..

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

        he didn't get any point even if he didn't be hacked becuase after the contest his solution will get wrong ansower, the hack help u to debug and update your solution befor the contest is over , and if u lock your problem (you lock a problem if u want to hack someone ) then u cant update your solution .

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

Hi All, can anyone tell me why the subset size is at most 3 in problem D?

I got it from above comments. Thanks!

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

    Assume points a, b, c are in increasing order, and let d(x, y) be the distance between points x and y. if d(a,b) != d(b,c), they cannot be in the same subset because d(a,c) wouldn't be a power of two. So if a, b, c are in the same subset, d(a, b) must be equal to d(b, c).

    Now assume that you want to add another point x (x>c) in the subset. According to what I mentioned above, d(b,c)=d(c,x). But this means d(a,x)=3*d(c,x), which means it's not a power of two. So the subset size cannot be larger than 3.

    Edit: Good that you got it already!

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

I don't know this is educational round or div3 round :(

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

Summary of hack for C (test 29): There were a lot of solutions that iterated over an O(K^2) loop. It passed original tests because when K is large enough, there tends to be a lot of YES answers and the solutions would just print it out right away when found.

The largest possible K with the answer NO we can easily think of is when K=20000 and ni=10 for each sequences, where every elements of each sequence are the same. But still some solutions passed through.

I managed to find a test case with K=40000 while keeping the answer as NO, and I think this is actually the worst case. Here's the code of the generator.

#include <cstdio>
using namespace std;

int main()
{
	int n = 40000, i, j;
	printf("%d\n", n);

	int cur = -10000;
	for (i = 0; i < n / 2; i++)
	{
		printf("5\n");
		printf("%d %d %d %d %d\n", cur, cur, cur, cur + 1, cur + 1);
		printf("5\n");
		printf("%d %d %d %d %d\n", cur, cur + 1, cur + 1, cur + 1, cur + 1);
		cur++;
	}
}
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

not able to submit code and also not able to participate virtually in this.

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

    You can't practice or virtually participate during system testing.BTW system testing is over, you can try now.

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

can somebody explain why O(31·N) gets TLE in D? 38851723

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

    Worst case of .find() in unordered set is linear i.e O(n) in worst case making your code O(31*n^2).

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

      that is because of collisions but using int reduces the chances of collisions (good hash function of STL), unless the test case was crafted for making TLE.

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

        It's totally possible for someone to add a hack data to make such solutions fail. That's why you shouldn't leave any luck-based things in your code in educational / Div. 3 rounds :)

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

    thanks _l-.-l_ & djm03178 but the problem was pretty stupid, I computed v[i]+(1<<bits) and v[i]+(1<<(bits+1)) again and again, this increased runtime, caching these values passes TL.

    Never thought this addition can be so evil. 38877122

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

      Haha that's sad, but you still passed TL by a little margin. 38877547 is your code using set instead of unordered set and it's almost 3 times faster.

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

        unordered_set (C++17): 3790ms

        unordered_Set (C++14): 2729ms

        unordered_Set (C++11): 2995ms

        set (C++17): 1263ms

        set (C++14): 1341ms

        set (C++11): 1263ms

        Lesson learnt:

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

          That's not the lesson you should learn :)

          You need to understand that unordered_set works based on hashes and therefore, if somebody knows the hashing algorithm used, they can handcraft a test case for which the hashes will have many collisions.

          One popular technique to avoid this is to add a random seed to your hash function. That way, the hash function is different every time and it is very difficult to generate a bad test.

          Have a look at this submission 38889378. It is your code, but with a random element added. It passes in 1153 ms.

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

            thank you for this valuable information, but I think you forgot to take xor again when searching in set. This trick helped me reduce runtime to 998ms. 38890354

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

In problem D,My submission gets Ac , but I think it is wrong because I thought same numbers can be chosen the same time . However , x — x = 0 , and 0 is not 2^s . it can be simply hacked .just like 3 3 3 3

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

    The coordinates should be distinct.

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

      Oh , I haven't notcied that. Thanks

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

    "There are n distinct points on a coordinate line"

    So that's not a valid input.

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

    Bro, the problem D's statement has said that the input contains n distinct numbers. :)

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

      Yeah. Thanks for telling me that. :)

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

I am new to this platform.... Just wanted to know.... after how much time rating changes are updated?

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

    I'm still waiting for the ratings to get updated. I don't know why I takes so much time. Hmmmm...

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

      Because it's div3 with ACM ICPC rules and extended hackings (12 hours if I am not mistaken).

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

For D, solution1 using set passed, but solution2 using unordered_map got TLE. How does solution2 which use unordered_map tend to be slower than solution1 which uses set?

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

    Press Ctrl+F and type "unordered" and you'll find out similar questions and their answers.

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

Your crafting.oj.uz ratings are updated!

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

Can anyone explain the approach/solution to problem F?

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

Editorial??

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

What is the required complexity for problem C)Equal sums?

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

In D, why did I have to sort the coordinates array to not get TLE?

TLE submission: 38882910,

AC submission: 38883316.

Thanks in advance.

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

    The problem in your code is not the sorting, but that you use the [] operator for map look-ups, which creates a new element every time (check the documentation), therefore needlessly increasing your map's size.

    Use find or count when you want to do lookups without creating new entries. This submission 38889506 is your TLE code but with this bug fixed and it passes in 1107 ms.

    As for "why does it work when sorted", it just so happened that, by coincidence, if you sorted your data, you found a solution early on and exited your program before hitting the time limit :)

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

Is O(n^2) not enough for Problem D? n<2*10^5 and time limit is 4 sec.

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

    O(n^2) would be 4*10^10 operations. 1 sec is aproximately 10^8 operations,so order 10^10 is too much.

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

Can someone please explain intuition / approach behind solving Problem F?

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

    It's optimal to bring at most one umbrella at any time. To get minimum fatigue given the configuration of rains and umbrellas (position, weight) you can use DP 0-1 technique to consider whether to pick current umbrella (to survive the next rain) or not.

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

maybe I need a div4 contest,because I think div3 is still too difficult for me.

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

What's the difference between if (v.find(x) != v.end()) and if (find(v.begin(), v.end(), x) != v.end()). (v is a set/vector)

The former one got AC but the latter one got TLE? Please help.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    set.find(x) - O(log(n))
    find(set.begin(), set.end(), x) - O(n)
    // set
    

    in the vector always find O(n)

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

      My vector v is sorted, that's to say, after sort(v.begin(), v.end());, does that mean it is also O(n) all the time?

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

        Yes. How с++ should understand that your vector is sorted. If you want to find the element in the sorted vector, you can use this:

        vector <int> a;
        //read
        sort(a.begin(), a.end());
        int i = lower_bound(a.begin(), a.end(), x) - a.begin();
        if (i < a.size() && a[i] == x) // yes
        else // no
        // O(log(n))
        
»
3 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

volamtruyenkyii this guy has given his first ever contest and got 1st rank, great. But he has registered just 2 days ago, Well I think he is a high rated coder who has made a new handle just to get rank 1 in Div 3

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

    Not that it really matters, but regardless of his intentions I understand he should not be in the official results because it is stated that "only the trusted participants of the third division will be included in the official standings table" and he does not meet the requirements to be such (actually, he is not an official contestant in the "common standings" page, the thing is that he got included in the "official results" table of winners in this post)

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

It was my first time to get tagged in official codeforces round .. Awesome ^_^

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

I'm glad to be an expect through this round. ~ this is a lovely round. Thanks

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

hahaha i ac 5 rating from 1500 to 1691!!!!!!!

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

can someone give me the complete 17th test case of problem F?

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

can someone tell me why my submission 39007350 is WA at the 17th testcase to problem F?