vovuh's blog

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

Hello!

Codeforces Round 494 (Div. 3) will start on July 3 (Tuesday) at 14:35 (UTC). 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.

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

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 Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

UPD: Editorial

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 peanutpedo20 6 194
2 Sakurak 6 363
3 Mr.HP 6 404
4 CrownJJ 6 417
5 Skypiea 5 153

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Osama_Alkhodairy 32:-3
2 Al-Merreikh 26
3 SovietPower 23:-1
4 neelbhallabos 22:-2
5 Milkdrop 20:-3

419 successful hacks and 670 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Skypiea 0:00
B Rinne 0:08
C quality 0:10
D adamgibiadam 0:11
E peanutpedo20 0:39
F peanutpedo20 0:55

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

Comments Comments (207)
| Write comment?
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for another div 3 contest!

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

I am new here,please somebody give me some info/links on these rounds so that I can explore the site. thanks

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

    Hi, you can go to the contest section.

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

      Thanks i looked into it. Please clear what are systests.

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

        System tests are the exhaustive test cases which are fed to your solution. They cover much more corner cases which are not usually shown in the sample test cases. One must design his/her solution keeping every possible corner cases in mind to pass the System testing phase.

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

    there rounds to solve problems and to your Score will be your rate

    ex : If you didn't solve any problem your rate on website will be lower and vice versa

    After rounds There's Systests So Probably Solve Problem and Got Wrong Answer in Systest and There's in this Contest Hacking phase that You Can See Other Codes and if you found something wrong you can Hack him.

    You Can find previous Contests in contests Section

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

      yes thanks. i found the virtual contest mode very interesting. it's just live as you really attempting the original contest. loving codeforces.

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

Every time you prepare a CodeForces Div3 round, I feel that you always copy paste this blog :| Anyway thanks for the round.

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

Hope this time we get all questions of expected difficulty.Best of luck to all participants :)

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

How many of you agree that the phase of open hack must be reduced to 6 hours as most of the hacking happens in this time and also the penalties on wrong submission to +10 mins instead of +20 mins which I think for a 2 hr round is too much.

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

    it should be just during the contest as i see div 2 rules

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

      in regular Contests Hack is during Contest

      But This contest with Eduacational round rule So There's hacking phase

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

I love div 3

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

    what is so special in it,it should be taken as a challenge to move up.

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

hope this contest has strong pretests... :)

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

    Aren't you a guy who wrote about "a lot of hacking stuff" on previous contest and got a lot of downvotes? ;)

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

      yes...i realized that people don't want that....and so my hope changed..xd plus i wish my contribution is positive as it had become negative due to previous comment..

      also i don't like this type of hacking phase where the questions trip down after the contest..hacking phase should be through the running contest with points being awarded for corresponding hacks, so that people may come to know that there solution is incorrect and at least resubmit correct solution after hack.

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

To practice acm questions click here

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

    It is a matter of taste, yes, it is a large ACM archive, but there are a lot of other)

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

      I just wanted to be resourceful for the community and there are many for whom the link might be useful for practicing for the future codeforces contests.Here the testcases are quite well!

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

        Depends on a problem: some problems were rejudjed because of bad initial testcases, but yes, it looks more like an exception, not a rule

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

bbbbbbbbbboooooooooooooorrrrrrrrrrrrrriiiiiiiiiiiiiiiinnnnnnnnnnnnnngggggggggggggg

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

    Why you comments so Stupid!

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

      people should respect a person competing regularly and is so active from war trodden syria

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

My rating of 1596 is quite embarrassing... Maybe I can be Expert after this round!

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

Div. 3 contests are really awesome! But I think, if the difficulty level between 'C' and 'D' is made more balanced then the participants( specially the beginners ) would get more motivated :). Best of luck to all.

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

isit unrated?

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

I request Mike to increase Number of div3 contests coz number of div2+div3 guys are more than div1

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

Guys can anyone tell me how to automatically generate tests ?, I read something about that long time ago but I can't find it right now.

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

    If you want to generate random test cases of your own, use this website to do so

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

    Polygon has its own test generation system. Check (EDIT: for some reason, the link isn't working, so instead go to https://mirror.codeforces.com/testlib and on the right you'll see one of the blogs has a russion title; that's the one you're looking for.) to see how the generators work. Note: it's in russian, so you'll probably need to use google translate to understand it.

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

Hopefully, problem set will be an interesting and short description. Good luck with the high rating.

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

Cant submit anything

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

Bad Gateway 502 again and again :( Such was not expected

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

Hello, I have been getting 502 error and codeforces unavailable for 8 minutes now, and not sure when this is going to end. Can you please make this round unrated for me, i feel this time penalty is unfair to me.

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

500 / 502

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

WTH??? Contest page hasn't been working for past 3 minutes..Lost my ratings too :(

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

Sorry for 502 on the first 10 minutes of the round. I think I investigated the reason. It is fixed now. I think it is because of filter for trusted participants. I've temporarily disabled it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    Site is not opening on my computer. I am unable to make submission for the last 45 minutes. The round should be made unrated. I wrote this from mobile phone site.

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

There is no score distribution?? :o

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

    Div 3 is based on ACM ICPC RULES (Extended). So there is no score distribution. Each problem is of equal weightage with a time penalty according to submission time and no of wrong answers.

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

the predictor isn't working in Div3 contest again !

[UPD] it is working now .

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

So, I lowered the rating, but the tasks were very good, especially D, thank u, vovuh, for this contest!

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

    In my opinion it was the best div3 contest)

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

Can we submit multiple times?

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

how to solve E ?

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

Very interesting problems this time!

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

Div 2 Round .. Solves A,B,C. Div 3 Round Solves only A and D.. What madness lol.

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

Nice problems, thank you!

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

I suggest having an announcement right after updating some mistakes . In problem F , it shows(j1 > i1) at first , and I thought the number of words must be exactly bigger than 1 . However it changes and I haven't update my webpage , which leads lots of WA on test4 , and I don't have enough time finding the rest bugs .

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

    Another sad thing , my bug is using "srand" , can anyone explain why it may gets wrong by using srand and rand ? PS:I used time(NULL) as the seed

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

      Same with j1>i1 :D Strange that they haven't made clarification.

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

        I'm really sorry about it. I personally can not publish global announcements, they can be published by Mike or Ivan (BledDest), but they were very busy, and I just fixed this mistake and forgot to ask Ivan to publish this fix in the global announcement. I'm very sorry for my terrible mistake and I apologize to RDDCCD, Tutis and the others who were affected by this bug.

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

Could any one help me by pointing out my mistake?code link-http://mirror.codeforces.com/contest/1003/submission/39925516

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it 
    j<(i+3)

    Really?

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

      yeah that was my bad please help now-http://mirror.codeforces.com/contest/1003/submission/39928710

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

        k can be between k <= i <= n, you only considering segments of size 'k' and 'n'

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

Div3: a wolf in sheep's clothing.

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

When will editorial get uploaded??

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

I'm unable to understand whats wrong in my submission on problem D .can anyone help me ? http://mirror.codeforces.com/contest/1003/submission/39928159

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

    Try lli (aka long long int) rather than li (aka long int, it is actually the same as int).

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

      thanks! but can u tell what is causing this mistake ? as if I'm running in my pc system it gives correct answer but on codeforces system, it is giving dump value.

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

        it is cause of long long( just change (li ans=0) to (lli ans=0)

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

Can we use greedy approach in D??

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

    Yes Greedy will work.

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

    Yes. Greedy approach always works when the numbers in the sorted order are the multiples of numbers before them in the array.

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

I think there was a problem on the problem C ! I tried an O(n²) in python but i got a time limit error while the same code in cpp passed the pretest... Could you make little changes please for that all the .py code passed the pretest such as the ccp code please ?

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

    The same code is judged as correct in PyPy and judged as wrong in python 3.6 !

    I hope that my submission and the others like mines are going to be corrected...

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

      I'm more curious as to why the latter submission took almost 13 times more time to execute

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

      first of all there is a difference between wrong and TLE. And pypy is an optimised intime python interpreter. so you should always submmit your sol. in pypy because it is fast. although there is a disadvantage to it, that it consumes a lot of memory, so only if you get MLE submit it in python. It is very rare to see python working faster than pypy

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

        Now i won't continue to use python 3.6 as interpeter but i'm very dissapointed. I will loose rating (probably such many other persons) juste because i used python 3.6 s interpreter. I think that's not normal and I really hope that Codeforces Admin will make something to change that.

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

          Dude python is not a recommended language for competitive. But yeah it is quite useful in some questions. By the way in this question python also passes, you should try optimizing your code

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

            but where is the egality if the O(n²) passed in other language ?

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

              Then use the other language. Language equality is an illusion. Join the cult of C++

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

              Some languages are faster than others. Also, some compilers/interpreters are faster than others. It's not the fault Codeforces and it's up to participants to know these things and to be able to judge which language/compiler/interpreter is approproate for which task.

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

    You may done this in O(n) time.

    code

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

      Can you tell a little more about the O(n) approach?

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

        Let us denote .

        And

        Let yi = S[i - 1], xi = i - 1 then what we want is to maximize the slope of lines that cross two points (i, S[i]), (Xj, Yj)

        This is an ordinary model, which we can simply maintain a convex hull, and a deque to solve the problem.

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

          Doesn't maintaining a convex hull take O(n*log(n)) complexity? And hence the total complexity of the above would be O(n*log(n)). Please correct me if I am wrong CelesteLight.

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

            The decision is monotonous.(my English is poor)

            Because we know that Xi, Yi are both increasing. And we can prove that if

            then

            So we can pop the last point of convex hull if the next one is better. And it is $O(n)$

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

          Ohk, that was good.
          Can you give pseudo code or the AC submission of this algorithm and similar to this

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

          CelesteLight I am trying to understand your solution without looking at your code implementation. Sorry I am not very good at Math, especially the Math term in English, can you help me understand the following:

          1) what do mean by "ordinary model"? Do you mean degree 1 polynomial?

          2) I understand your explanation up to the point of finding the slope of (i, S[i]), (Xj, Yj). So, the naive solution is to find the slope of every pair (i, j) , which will take O(n2) . How does convex hull algorithm helps reducing it to 0(n)?

          a) To clarify my confusion, when we build the convex, we will go from point to point: (i, Si), (i + 1, Si + 1). How will that reflect on (i, Si), (i + k, Si + k) which is the range that we are interested in?

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

            My English is far too poor to explain it further. If you want to know more, searching in the Internet for "slope optimize DP" might help.

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

Website issue cost me rating

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

    After submitting A, I had to wait around 8-10 minutes to read the problem statement of B.

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

    This happened to everyone, and I think now noting can be done.
    And further questions B,C,D were also good. 10 minutes does not matter in that if you solved B,C,D also.

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

      Yes but there will be a gap between people who submitted A right before the server issues and right after, while in a normal contest its a few second/1 minute off but in this contest is can be over 10 minutes apart.

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

I'am solve first problem in 1 minute, But the site did not work so I was very late in sending it, It is unfair that unofficially registrars can act on the site's lack of responsiveness while official registrants lose points because of it.

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

    All Had The Same Problem....And There's Ranking for official registrants only

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

Can someone tell me when CF-Predictor will update the rating for this contest.I am so excited so Its hard for me to wait 12 hours to see my new rating. :p CF-Predictor: https://cf-predictor-frontend.herokuapp.com/contestSelector.jsp

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

Are current #2 and #3 cheating?

http://mirror.codeforces.com/contest/1003/submission/39911751

http://mirror.codeforces.com/contest/1003/submission/39926904

Their solutions for F, other than the template and variable names, look identical.

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

For Problem C , the answer shouldn't vary by more than 1e-6.
I see that some solutions are printing solution till 6th place precision, something like %.6f. This could lead to rounding off at 6th digit after decimal at times, depending upon test cases.

Does anyone have a test case to break this? I tried generating tests, but have no success uptil now :(

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

    U tried generating test cases by taking help of any tool? OR on your own. If u used tool can u plz share

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

      No, I just wrote a program to generate tests for the problem.

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

    I think printing %.6f would be fine and can not be hacked.

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

      See this, for example. If your answer was 1.3333337, it would print 1.333334 as answer, which has difference of 1e-6.

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

        No it actually has difference 1.3333337 — 1.333334 = 0.0000003(3e-7) which is smaller than 1e-6

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

          The difference would be between actual answer (1.333333) and our rounded off answer (1.333334), ie 0.000001

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

            by statement of problem C,

            ... is the answer given by the jury's solution.

            and the jury's solution is printing more than 6 decimal points.

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

              Damn, didn't realize this. Thanks for correcting :)

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

                My pleasure. Actually I thought just like you at first :)

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

    if u .6%,The answer will be rounded.So it is wrong

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

can anyone plz explain problem B to me its not clear

Thanks

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

    It is really clear.A string S consists of 0 and 1.Number of 0 is a,number of.1 is b.U need to find a S content the situations

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

    add sth. there are x index that s[i]！=s[i+1]

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

Will the points deduct in case of unsuccessful hacking attempt in this round?

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

Fix a bug in the last 30 seconds, so close :p

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

What is the main idea of the problem E? I solved A, B, C, D, F and thought for a long time about E

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

    Create a chain with d+1 nodes that has length d. Just repeatedly add new nodes, making sure that each node still has degree <= k and the diameter doesn't increase.

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

    I solved E using BFS. Here my approach:

    • First let our base tree is the chain tree which length is equal to d (If d >= n -> answer is No)

    • Second let try to put more vertices into that base tree, we can observe that we can actually put some 'forest' into these vertices and the maximum height of each vertices is calculatable Let H[u] is the maximum height if we add 1 forest into vertex u, then H[u] should look like this 0,1,2,3,.. d/2,d/2-1,... 0 .

    • Thirdly we know that each vertices has its maximum degree k, then we just greedily add forests into these nodes until >= k

    Code : http://mirror.codeforces.com/contest/1003/submission/39923949

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

nice contest .. problem E is similar to this problem

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

    E had an extra constraint of maximum degree for any vertex. I believe this constraint is (more than) enough to differentiate between the two questions.

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

      that's right .. I was pointing to the general idea which is building a tree with some given diameter

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

For D, Can someone sketch a proof for why greedy works. First, how can we be sure that greedily removing values would not make it possible to get the sum. How does a local optimum of removing the next maximum power of 2 as much as possible result in a global optimum.

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

    This might be a useful hint. Think about the binary representation of numbers

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

      Yeah that was my first idea. Since the numbers are powers of 2 , they would have only a single bit set in their binary representation. But that didn't get me anywhere substantial.

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

        I meant the binary representation in the queried numbers, this should help you with the first part of your question. For the second part does the fact that 2^i= 2^(i-1)+2^(i-1) help you get further?

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

        Converting decimal to binary is greedy (take the biggest you can until number becomes 0)

        Which means that if you use powers of two (numbers you consider taking when forming a binary number) you can use the same greedy process.

        Also, you can think of it as coin problem where each number is the divisor of the next, if you have 2i and i coins you would always take a 2i-coin instead of 2 i-coins. Apply that logic recursively until you hit 1. Only issue with this is that there is a limitation on amount of coins you can use, not sure if this affects it

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

          Exactly, without the limitation on the number of coins we can show that it's optimal. But what about this case.

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

            Let's assume our greedy works given no limitations, which it does. Also note that the greedy solution is the only optimal solution, any other arrangement is worse.

            Now we can think of a case with limitations.

            During our greedy process, we hit a scenario where we need the coin with value 2^a but we don't have the coin.

            Now assuming the greedy method is optimal, it is also optimal to use the greedy algorithm to find the solution to 2^a given coin values 2^(a-1) and below (to replace the coin).

            This is what our general greedy algorithm does, except we process the whole thing in one go instead of running a separate greedy every time we don't have a coin 2^a. When we are lacking 2^a we greedily replace it with lower value coins, which we already know is optimal.

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

    Let there be two coins, X and Y, such that Y = (2^k) * x. (k >= 1)

    If you want to get an amount Z of money given in those coins, it is always optimal to take as many Y coins as you can, before you take any of value X. That is the best you can do, because let's suppose you used only X coins instead of using X and Y. Then, it is clear that you needed at least (2^k) times more coins to make up for the value you could have made using Y, but chose to use only X. So, if you want to have as minimum coins as possible, you need to start from the higher-valued coins, no matter how many of them you have in comparison to the lower-valued ones.

    And if you can't form the sum using a X coin, you wouldn't be able to do it with Y either, because using Y means using (2^k) * X. The opposite is also true, only difference is the amount of coins you would need to use to make the sum.

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

why not, round extended for 10 min

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

Any tough/tricky cases for E?

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

What's wrong with this solution for F? 39922956

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

My first ever hacking attempt against srand(time(0));!

The way I did it: 1) printed time(0) at a certain time

2) Seeing as time(0) was 1530644xxx, I decided to make a code which finds a counter-case for every time(0) between 1530644950 and 1530644969 and puts them all into 1 test case. Code: https://ideone.com/SQ2AAb

              3) I went to their submission, selected the hacking window and selected the test case in the form of a text file.

              4) I refreshed Custom Invocation code for time(0) until it became >=1530644950.(took about a minute of waiting)

              5) Once it was >=1530644950(1530644953 at the time of invocation), I pressed the hack button.

              6) Profit!
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u hack again, he submitted in practice mode, by changing some values? xD

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

    Hack me! 39934835

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

    My solution uses random generation of mod > 1e9 and base for hashing, I think it's not hack, it's true?

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

      I probably couldn't hack it because finding a collision among 1027 possible combinations is extremely unlikely. On Akul's code, there were only 109 possible combinations, so I could find a collision pretty quickly.

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

        Thanks for your reply. What can you recommend in problems with polynomial hashes? Will this solution be safe in other problems?

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

    We can use std::chrono::high_resolution_clock::now() which tick faster than std::time()

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

F can be solved in O(map * n^2) using hashes. For every length of iterate through interval of this length in increasing order, then using map + hashes store how many intervals you can match, and there is the rightmost one. 39934835

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

    But you must randomize the hash value otherwise your code will be hacked like mine.

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

What can be causing the RTE in this code

Im losing my mind :D

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    I think it's a stack over flow because of too many recursions try this test case:

    5 1 1 2 4 8 16 10000

    answer is -1 your code is giving RTE

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

    Stack is getting overflowed by repeated calls here long long add=go(pos); Try on this :- 1 1 1 2

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

      Yes the issue is caused when i call the function giving it a parametre number with only 1 set bit which make an infinite recursive calls .

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

Is there any way to implement hash so that I won't be hacked?

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

Hello, I'm new here and I want to know if there is any article describing the whole process of a complete round. Could anyone help me?

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

    Yes editorial will come out probably by tommorow.

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

Can someone give a nice approach for div2 B problem other than spamming if-else statements? Either way do explain the solution you all submitted, it'll surely help me. The way I thought the solution was as follows: for x such characters in the final string we need (x+1) groups of consecutive 1's and 0's with any number of 1's and 0's in them( obviously there should be more than 1 in each group). But I found the solution difficult to implement. Can someone help me with it?

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

    I also found awkward to implement.

    So you need x+1 groups of consecutive 1's and 0's.

    The way to do that using minimal amount of digits is just

    10101010... or 01010101...

    Depending on the constraints one of might fail, but one of them HAS to work.

    Not this solution already fits the x constraint, now you need to match it to a and b.

    Actually there's an easy way. Insert a bunch of one's next to a prexisting one and zeros next to a preexisting zero.

    Like this:

    1010101 ---> 11111010101

    notice how this doesn't affect the amount of switches now we do the same with zeros

    atleast one of our solution will work, we just have to test which one

    39905965

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

      Note:

      f() creates 10101010 g() creates 01010101

      count(v) counts the amount of "01" and "10" in v (should be x)

      fits(v) checks if v used less than a and b zeros and ones

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

    First, we implement a sequence which is always flipping like "01010...". Specifically, we set the initial sequence to be "01" if A >= B, or "10" otherwise.

    Then, we put the rest of the 0s and 1s into any of the position of 0 or 1, which does not change the flipping number. You can see this implementation 39904229 for details.

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

I have tried an approach to problem F involving string hashing mod 1e9+7 and then picking intervals to shorten greedily (interval scheduling) but it fails on test case 54.

Now, I changed the modulus to 1824261409 for the hash and it still fails, I think there might be some case I am missing out on, as answer is off by only two. I'm guessing it might have something to do with whitespace, but codeforce does not let me look at the full case. Can anybody pinpoint what's causing the anomaly?

39940552

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

    just use a map<string, int> and change everything to ints

    Alternatively you can use double hash or even triple hash, but that is probably too much time to code and too error-prone.

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

    That test case is actually one I used to hack, it's 299 'a's and one string with 99000 'a's.(that test case was originally designed to possible TLE something, but i saw a solution give a negative answer on it and hacked it with that). If you want a smaller test case, then try this:

    3

    aa aa a

    Your answer: 4

    Expected answer: 5

    Your solution treats 'a's as 0s, meaning that it recognizes "aa aa", "aa", "a", "aa a" and "aa aa a" as 0. To fix that, you need to treat 'a's as at least one, meaning you need to add one to your base and the letter. 39946086

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

i am a beginner just wanted to ask when will the final results be out for this contest??

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

I don't understand why two same solution one in Python and another in Java give different verdicts.

The one in Java passes while the Python one gives TLE

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

    Simple: because not all programming languages are equally fast.

    P.S. if you're using python, try submitting with PyPy interpreter. It's optimized for speed.

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I think that we shouldn't have been able to hack F, because there is the hash solution for which there always theoretically exists a countertest. I might be a little biased here, because it happened with my solution: 39926278, but it also happened to more than half of the solutions of F.

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

    That's why sometimes srand((long long)new char) is needed. xD

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

Where's editorial ?

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

Can someone explain how to solve F? Or just give some hints?

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

hey for E, my 39924761 hacked, but i show the hacking test, that was 5 4 1, http://mirror.codeforces.com/contest/1003/hacks/465215/test, my answer is "NO", it is correct answer i think, why my solution was hacked? sorry my poor english. vovuh

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

    it depends on exit(1), exit code 1 means runtime error on codeforces, I regret what I dont know about it. I changed my code exit(0) get AC

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

Same codes with just reformatting again from Mo2men and Molo5ya.

39914320 39910896

MikeMirzayanov vovuh

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

is there going to be an editorial for this round?

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

Why so much people used hashing solutions on F when a simple string matching algorithm like KMP works just fine?

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

    It's easy to code . At least for me it's easier .

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

      But it's not very reliable. I have bad luck when choosing the big prime numbers for hashing, and I say "luck" because I don't quite understand how to choose them, I just pick the most famous ones around, and yet most of them have complex counter-cases!

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

        Well I am afraid of being hacked . So I choose the prime randomly . And I got wa . I got ac after I use a certain one . I don't know why srand and rand affect so much . :(

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

    Why so much people used hashing or KMP solutions on F when http://mirror.codeforces.com/contest/1003/submission/39912717 works just fine?

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

In the graph of problem E how do I calculate the maximum number of edges?

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

    What do you mean? Since the output is a tree with n nodes, it's always going to have n - 1 edges — no more, no less. Did you mean something else?

    I guess, to answer your question, the maximum number of edges is always going to be n - 1.

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

self-delete

→ Reply