Arpa's blog

Codeforces Round #432 (based on IndiaHacks Final Round 2017)
By Arpa, history, 7 years ago, In English

Hi!

I'm honored to invite you to Codeforces Round #432, it will be held on 4th September 14:35 UTC. There will be 5 problems for each division, as usual, you have 2:30 to solve the problems. The contest was prepared by Lewin Lewin Gan, Artsem Arterm Zhuk and me.

The IndiaHacks Final Round will be held on 3rd September 12:30. Finalist must not discuss the problems after their contest.

The stories of my problems will be about Arpa, although in one problem you'll see Mojtaba moji FayazBakhsh, my great teacher.

I'd like to thank Lewin, Artsem and myself (:P) at first, then Konstantin zemen Semenov and WHITE2302 for testing the problems, Nikolay KAN Kalinin for helping us in moving the contest to codeforces and Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

The scoring distribution will be announced later.

Obviously, if you are interested in if the round is rated or not, ask in comments and get a lot of down votes.

UPD. There will be 5 problems for div.2 and 6 problems for div.1.

UPD2. Scoring Distribution: div.1: 500-1000-1250-1750-2000-2500, div.2: 500-1000-1500-2000-2500.

UPD3. Editorial is partially ready. I'll complete it soon.

Congratulations to winners:

Div.1:

1 . BaconLi

2 . dreamoon_love_AA

3 . sd0061

4 . W4yneb0t

5 . Um_nik

Div.2:

1 . miaom

2 . fzzzq2002

3 . lzy960601

4 . Lucas97 and Szymanski_w (WoW !!)

Official results

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

Comments Comments (326)
| Write comment?
»
7 years ago, # |
  Vote: I like it -445 Vote: I do not like it

Obviously, if you are interested in if the round is rated or not, ask in comments and get a lot of down votes.

is it rated ? :))))))

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

4nd September 14:35 3nd September 12:30 Didn't know September had an extra "thirnd" and "fournd" days :)

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

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

WTF? Just say that the contest is rated. It's not a place for your stupid jokes. There are new users don't know if it is F**king rated or not!!! Hope statements are not s**t like your announcement.

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

So unusual time for contest

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

If its rated than Cool and if not also Cool . But you should have said if its rated or not in ur blog post.

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

    Yes I though it was unrated because it was based on a contest that happened before which could cause a leak of problems.

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

I missed the round (HE India Hacks Finals) :( It seems that the time in codeforces calendar is wrong.

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

    Oh no, I'm very sorry about that, I forgot to update it :(

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

      Darn, forgot to check it was 12.30 UTC time. Should have got a notification at the beginning of the round :(

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

      I also missed the round on Hackerearth and didn't registered for it too. So can i participate in cf round?

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

        Yes, this is fine. We have a list of people who opened the contest, so you should be able to compete as long as you didn't open the problems.

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

Thanks for the contest. Indiahacks final sounds pretty tough. Will the difficulty be of a normal round?

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

    A bit harder than a normal round.

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

    Of course, the high rated orange gets upvotes for sarcastic comment while everyone else gets downvoted to hell.

    Amazing community we have here.

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

Is it rated?

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

I hope to be specialist in the 50th contest for me :) Good Luck for everyone :)

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

    dude, you don't know whether or not, it's gonna be rated!

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

Great contest with a great rank for me, I hope. It's true that I never solve more than 3 problems in a contest. Bring good luck to me and all of you, too!

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

I think, Arpa means "Artem", not "Artsem".

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

Still no one answered if the contest is rated officialy? What kind of joke is this? How can CF admins allow this

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

    If you really didn't get, Yes, it's rated.

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

      I asked same but I got many down votes :| why ?

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

        you asked,but in bad place. and also in that place you should mention that it wasn't mentioned in the blog.-some people have algerie to "Is it rated?"-

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

        Because you have done it for a joke.

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

      Please include that in the post. I take CF round very seriously and you are making fun out of it

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

        how could you say that ! this is your second contest

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

        but if you are really active , why you still don't know that the round is unrated only when they say it in the announcement

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

Spoiler Alert!

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

In fact,it is rated as usual.

So,don't ask the same questions unless you want to get a lot of down votes. :)

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

    like you, and like me (because i know this comment will get lots of down votes) :)

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

I've advanced to the finals, but I'm in other country on bubblecup, so I had no time or posibility to take part in the finals, also I've not visited hackerearth website last days, in one word: I have no idea about competition, I only know who won it (from friend). Can I write this round?

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

    Yes, this is fine. We have a list of people who opened the contest, so you should be able to compete as long as you didn't open the problems.

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

      you are pasting your line again and again :D

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

Thanks to CF calendar, I don't need to ask whether the round is rated or not. For those who don't know about this:

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

    I don't even need the calendar to know this fact, this contest's name is "Codeforces Round #432" so since it booked a number (432) it means it's rated, also if it wasn't rated then there wouldn't be two divisions

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

      I didn't know that. Thanks for telling us.

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

What a late time for Chinese players. I'm glad to take part in it ,but out of the curriculum...you know

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

    An additional hour later for Korea, Japan and parts of Indonesia...

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

    I'm a Japanese, and the contest starts at 23:35 and ends at 01:35. Also, system test will ends after 2 o'clock am. It is so late time for 9-th grader student.

    But this is earlier one I think. Some of past codeforces contests start at 00:05, 00:35, 01:35, ... In the worst case contest starts at 02:35 and ends at 04:35. What time do you think the ending of systemtest and rating update?????????

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

      I am so sorry to hear that,it is an earlier one indeed. But what makes me embarrassed is that I made a mistake.I regarded this contest will start at 23:35,I am so sorry. Wish us would have an interesting contest and have a high rating!

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

There will be 5 problems for each division, as usual, you have 2:30 to solve the problems.

Is 2:30 a usual time duration for Codeforces contests?

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

is the contest rated ? :P

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

It was 2.5 hours or more surprising when I first saw the game. As a Chinese player, I needed to go to bed after one o'clock in the morning, and I hope that tomorrow morning classes will not fall asleep. In addition, I wish codeforces would be getting better and better, and this competition can be rated normally. I wish you all good results in the competition.

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

WoW,I think it's an excellent contest. Although the contest will start at 22:35 in China. I will take part in it! :P

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

So is it like there are 4 shared problems in both divisions?

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

    No. 3.

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

      so right now there is two condition: 1.Div 1 is simpler 2.Div 2 is harder so which one is correct??

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

        In fact, Div 2 is simpler than Div 1.

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

          I know that,but from the place that 3 question are shared,question c,d,e div 2 is shared,so if C or D are harder than usual ,div 2 is harder,and if not both div are as usual as they were.(actully i'm not sure about what i'm saying:) )

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

        Neither :)

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

can anyone say's what is the difference of CUP,and contest that based on CUP?

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

Maybe this article should just tell us if it's rated rather than warn us that question about rated or not will be down-voted.

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

Hope to be rated.

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

    yes, it is as you wish

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

    After the contest you will hope it was unrated.

    (Off topic question: is the previous sentence grammatically correct? If not, how should I say it correctly?)

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

      FIX: After the contest you would wish the contest was unrated

      But anyway, we are programmers, we code, we encrypt and decrypt. Grammatical mistakes are nothing.

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

        "Grammatical mistakes are nothing."

        My compiler doesn't think so.

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

Hope clear problem description this time.

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

Love you Arpa

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

I usually don't understand Indian accents. Will it affect my performance?

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

    Dude i understand that you want downvotes, but being racist is just blatantly wrong and i think that your account should be temporarily suspended.

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

Nice joke with rate/unrate...

Good luck everyone! :3

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

Does Minimum Spanning Tree appears in any codeforces Div-2 contest? As of now, I haven't seen any :/

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

Arpa you and your teacher have almost the same rating. That's cool :)

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

Is it rated OR not? Yes!

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

in today's round ,will div1A==div2C or div1A==div2D ?

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

Less than 2 minutes until contest, and still no score distribution. Later means, after contest?

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

3rd contest with geom, I think I will lost my rating(

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

too weak pretests for problem D div2

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

    Is it a thing that you can say during the contest? If your saying is true, many people that knows your comment use the different strategy.

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

is this mathforces??

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

wtf how much geometry ? 2 problems out of 5 ?? that cruel

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

Unable to see other's code for hacking :|

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

Why unrated is higher than rated?

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

    I think Arpa and his teacher wanna to make more down rating users like them!
    I think sum of all users rating changes in contest equal to 0.

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

      Congratulations! I got many down votes because of baby who is you ;) Heyyy don't jump at me ;\

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

      You were wrong and I won! First fact you got -50 Ha ha ha ha ha ha!

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

In Div2B, i have try to hack three different solution on same test case ,two of them giving "Yes" and one is giving "NO" as output still all goes unsuccessful. and try to hack a code in which he is dividing by 0 but still i got unsuccessful.

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

    there is something problem in hacking ...please check

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

      You didn't have three equal hacks by the time of posting, and all outputs were "No".

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

We need more geometry problems, why two only?

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

WTF was this contest? I'll give you all diplomas.

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

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

    upvote if you go to the CF to read the memes

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

Someone probably shared problems.

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

Probably my rating will go up, but I didn't like problems...

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

    well the goal of the contest was to make it painful for div2 first : 2 geometry problems second : only 5 problems while div1 has 6 maybe an extra non geomtric problem would make it less frustrating

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

Hardest B-Div2 in the History!

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

I don't understand why some people submit obvious wrong bruteforce for d(it's painful to hack them).

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

    I had solution where I generated primes up to 10^6 and done something with them + optimization. Is that bruteforce you are talking about or?

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

ideas on div2 C ?

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

    I think this works.

    First of all, dismiss the cases n = 1, n = 2 as trivial (I failed to do this correctly on many instances).

    Now, note that if n > 11,  there cannot be any good points. (verify this with the 2 dimensional case, where a similar conclusion holds when n > 5, and extrapolate). Now n ≤ 11 and it suffices to simply brute force every triplet of points, which works in time.

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

      how did you up come with that observation ?

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

        Intuitively, it gets increasingly difficult for a point to form an obtuse angle with every pair of points as the number of points get very big. My first observation was that there can only be one good point when n ≥ 3,  since if P is a good point, and so

        Then I realized it's difficult for even one good point to exist, which led me to the bound I found in the previous post (I think I have a proof, but it is quite messy).

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

      could you explain in details about n > 11, please?

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

        It's nothing close to a formal proof, but the proof I have in mind is quite tedious, so I'll just give a heuristic argument.

        Consider the 2 dimensional case of this problem. The maximum number of points there can be in order for there to be a good point is 5. (consider the zero vector and the unit vectors in each direction (+x,-x,+y,-y)). In the 3 dimensional case, it's also pretty clear that the best we can do is 7,  with the same construction (except we add +z and -z). Extrapolating this way, I got my bound of 11 (although in retrospect I should have been more lenient, just in case).

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

      Yup, i failed that n=1 n=2 this time...tried for an hour but that didnt cross my mind...well atleast this wont be happening again!

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

      Wow,how did you think of this,I mean,as an amateur I thought that it's hard for a collection of a lot of points to exist such that some points are good among them,but to make SUCH A BOLD statement that, ans = 0 for n > 11..

      I want to learn how did you think of this,and also how you convinced yourself.. I mean not intuitively but what solid reasoning made you confident on your statement?!

      Thanks!!

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

        I'm an amateur myself, but I think the intuition for this came from doing math contests (which I'm not that much of an amateur in), where I encountered similar problems. Starting with the 2D case was a natural step (I can actually draw the points!), where I noticed that 5 points was maximal. I didn't arbitrarily choose the number 11 and try to prove that it was maximal, but I think the extrapolation method is enough motivation.

        I did come up with somewhat of a proof before I submitted, but I was fairly certain in my intuition. I generally wouldn't submit without at least a sketch of a proof.

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

          pretty impressive,my background in math isn't that solid,for most of it I have studied only calculus and almost no geometry, Your statement was no less than MAGIC to me,seriously, I will try to keep this in mind,also if you can link some article or some proof,please do,I can't find one..

          By the way,In the end when I was not able to think of a solution for Div2 C, I submitted a brute force solution which was O(n^3),someone told me 10^9 operations run fine on codeforces server,lets test that today :P

          EDIT: I was unaware of the situation that for n > 11 the solution would be zero,so in order to make my N^3 solution run,I made a little pruning effort by breaking the loop in case acute angle occured,so my algo reduced to O(11^3) for n > 11,pretty lucky haha :D

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

            That's good to hear. I think v_Enhance's post here serves as a nice proof (I forgot about this until now, oops.)

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

    My code outputted "0" if N >= 100 and was a brute force otherwise. Does this work?

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

    3 points form a triangle. At most, only one of those points can be good by definition of a triangle. Make a queue, pop 3 elements, append at most one. Brute force the points remaining (at most 2).

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

      i would agree if we talk about 2D/3D. but in 5D i can't even imagine plane, so taking about properties of triangle in 5D sounds a little bit unreasonable

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

        It is reasonable because when 3 5D points are chosen, they form a plane.

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

      I think the same, but I implemented a thing like a sieve.

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

how to solve div2 B ?

fu**ing geometry

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

    Assume a point of rotation exists, call it X. Then clearly XA = XB = XC and so It follows that it is necessary to have AB = BC,  and moreover to have that A, B, C are not collinear. It is easy to see that these conditions are also sufficient, and we're done.

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

    You can construct a circle from 3 points (sorry for my horrible English)

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

    The requirements are that the distance between A & B and B & C is the same and the points makes a right angle. Play with rotating triangles on Desmos.

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

How did you pass the pretests after getting WA #8 on C, those who did?

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

    I had a silly mistake not taking into account values with only one prime factor(a typo), and that turned my wa8 into pretests passed.

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

Give me counter example for (ax-bx)*(by-cy)-(cx-bx)*(by-ay) != 0 (preset 6(

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

What's up with tc 8 div2E?

This is what I did, let's calculate the grundy number G for each prime separately.

For a prime, if the powers of this prime in the array in the sorted order are P1,P2,P3...Pn.

Then, grundy no. for this prime would be P1^(P2-P1)^(P3-P2)..^(Pn-Pn-1).

So Arpa wins only if the xor of G for all primes is 0. Can anyone tell why this is wrong?

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

    p1 = 1, p2 = 3 should be a losing state

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

    your grundy number is wrong, I counted grundy by dp on bitmasks and it passed.

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

      Yeah I get it. Thanks

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

      What with states for 2?

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

        I can't prove it, but there is small number of states even for 2. At least I tried on 229 - 1 and some numbers like that and it worked fine with map.

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

          fml seriously? I spent more than 1 hour thinking about that but I thought there would be too many states :(

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

        I think that number of states is less than number of compositions of log(1e9) because when we divide by p^k than we subtract k from max{k1,...,ks}. Am I right?

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

Can div1 C be solved using grundy numbers, where each prime is equivalent to a nim stack? I couldn't figure out how to compute it though since there are too many states.

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

I like geometry problems. Only if i had read B and C today :(

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

This submission for Div 2. D was TLE on pretest 10, does anyone see why? Should be O(10**8)

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

typedef long long ll;

const int LEN = 1000;
bool isP[LEN];

int n, a[500001];
ll x, y;
vector<int> pri;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fill_n(isP, LEN, true);
    isP[0] = isP[1] = false;
    for (int i = 2; i*i < LEN; ++i)
        if (isP[i])
            for (int j = 2; i*j < LEN; ++j)
                isP[i*j] = false;
    for (int i = 0; i < LEN; ++i)
        if (isP[i])
            pri.push_back(i);
    assert(pri.size() == 168);
    // cout << pri.size() << '\n';
    cin >> n >> x >> y;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll ans = (1LL<<60);
    for (int p : pri) {
        ll z = 0;
        for (int i = 0; i < n; ++i) {
            int d = ceil((double)a[i] / p);
            z += min((p*d - a[i]) * y, x);
        }
        ans = min(ans, z);
    }
    cout << ans << '\n';
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are about 8e4 primes below 1e6. So, total number of operations is about 8e4 * 5e5 = 4e10. TLE thus.

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

      Oh I see, I only tried primes under 1000

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

        Im happy to see someone had this idea haha. I solved it same way except for one optimization but it didnt help (i thought its good optimization but looks like not really that much)

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

    same here!! my solution doesn't pass, where m = 1e6.

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

When in the last five minutes you get hacked on Problem B after spending an hour figuring out that you need to use long numbers and when three points are in a straight line it doesn't work :(

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

In problem B, i thought that only when AB = BC you can achieve thing described in problem. I coded but it failed on test 3. Why does it not wok?

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

    If the three points are collinear it doesn't work

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

      Why it does not work?

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

        If you draw a circle that passes through the three points then you can rotate the page on the center of the circle. You can make that circle for all angles that the points might be in, unless they're collinear

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

    The angles of BAC and BCA should be the same as well (but should not be collinear).

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

    You should check if the 3 points are on a straight line.If that is the case ans will be no even if AB=AC.

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

Problem F in Div. 1 reminded me of this problem from Stanford Math Tournament a few years ago (scroll down to page 7).

Can a similar solution be used here?

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

    Yes, it can be solved this way, but instead of just finding f(1), one needs to add f(ai) for all i.

    I still wonder how people solve this problem in 30 minutes, though :) It took me more than 90 minutes yesterday.

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

      It's well-known in China. WJMZBMR created exactly the same problem back in 2012.

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

        Meh, out of 13 people that have solved it, 11 are Chinese, so it seems you are right. That makes me even more sad that I made an error in my calculations which stopped me from getting AC on this.

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

The first contest in wich i solved D and not C. I didn't study n-D vectors in highschool lol

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

what was pretest 10 of DIV1C I calculated grundy number of each prime separately using DP.

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

Cf rules are stupid, it wasn't "enter the dragon" as I expected. XD

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

Tfw you find D and E easier than B and C. :/

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

:(

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

    I like geometry and math problems much more than data structures ;d

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

      The Best I Could Make Before my rating drops to Newwwwbie

      → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
double ax,ay,bx,by,cx,cy;
    scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy);
    
    double dist1=sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay));
    double dist2=sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by));
    double dist3=sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay));

    //pritnf("%lf %lf %lf\n",dist1,dist2,dist3);

    if(dist1==dist2  && dist1+dist2!=dist3)
    	printf("Yes\n");
    else
    	printf("No\n");

What is wrong in this code ? Please help ...

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

    dist1+dist2!=dist3 What is that? Why?

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

    Might be double inaccuracy (e.g. abs(dist1 — dist2) = 1e-8 or some other very small number when they should equal). I kept it as long long (didn't sqrt) and compared the square of the distance so I could compare integers

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

    dist1+dist2!=dist3 does not guarantee that the 3 points are not collinear

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

      How ? Tell me any example .

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

        for your code: (0, 0) (1000, 1000), (1, 1) in this order. they are collinear, but your code states otherwise

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

          this case is taken care by the condition "dist1==dist2" if they are different then for sure the answer is NO but is they are same then only one condition can make the answer NO i.e when points are collinear and if dist1 is equal to dist 2 then the points are collinear only if dist1+dist2==dist3!!!

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

            Floating point error due to the sqrt() function is the reason it fails

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

      Man, I tried hacking a solution that did it, but I was wrong ;_;

      Thing is...we have already checked if d1==d2 or not, if their sum is equal to d3 then they are co linear. So...you can just check if B is the midpoint of AC or not

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

    Now I know mistake. Order of points may not be A-B-C. Maybe A,B,C are on the line but their order is C-A-B or something so dist1+ dist2 != dist3 but they are collinear.

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

    There's nothing wrong in this code.

    I have done the exact same thing and my solution passed system tests :)

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

    I used long double instead of double for the distances and used sqrtl() instead of sqrt(), it got AC (after the contest).

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

How to solve Div2 B ??? I am Helpless in geometry ???

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

    just check that if point B lies on the perpendicular bisector of line AC. and also these three points must not be collinear. if(B lies on perpendicular bisector of line AC than) print yes else no

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

      Seeing all this I really beleive that becoming purple is really a far dream . :(

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

      same as saying check if the triangle is isosceles!

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

For problem D, I had this approach (time limit on pretest 10). Generate primes up to 10^6. Idea is to find for every prime (not really EVERY, there is optimization) what is minimum that we can achieve to get all numbers divisible by that prime.It is easy to see that we will either delete some number or increase it prime — ( number%prime) times, so there is simple calculation for every number. Now comes optimization: If number of a[i] that are divisible by some prime > 2 is less than or equal to number of a[i] divisible by 2, skip that prime (because it will obviously make worse or same score as with 2). So, after we visit every prime, we will now best answer. I know this is overkill but I thought it would maybe pass because this optimization eliminates a lot of primes (or does it).

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

rating predictor

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

WHY problem C div2 solve with N^3 :(( :((

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

    It cannot be solved by pure N^3, only with the fact that if the pair giving acute angle is already found, break the loop, which significantly reduces runtime.

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

      I know this trick, I use it in D but I dont have reason use it in C... Why n > 100 -> write 0 :(( :((

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

First of all, my bad for having a wrong idea and not looking at test samples carefully but I think these kind of things shouldn't happen during the contest....

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

    but they did not mention about the point C!

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

    I'm really sorry. Excuse me. I remember that I was to press "No"... I don't know what happened, it seems I accidentally pressed "Yes" (in the drop down menu). Anyway, I'm happy that you get the correct answer only after 3 minutes. Sorry again.

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

      If it only happened to me, it's fine. Thank you for an interesting problem set. :)

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

        Yes, only to you. Thanks for your kindness, and sorry again :)

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

So many people have solved div2 D , but I got TLE. What is the algorithm

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

    You can enumerate the final gcd, and devide [1,1e6] to several parts like [1,gcd],[gcd+1,2*gcd],[2*gcd+1,3*gcd],and for every part the last x/y values should perform operation 2 for several times , and the rest should perform operation 1.And you can put the array in some bullets, and calculate the suffix sum of the bucket , and another special type of suffix sum which can be calculate like this: s[i]=s[i-1]+bucket[i]*i. And for every part you can calculate the ans under 'this gcd' in O(1) time,and for emutating gcd in and the parts in O(n/1+n/2+....+n/n)=O(nlogn) to solve the problem.

    Sorry for my poor English.

    P.S.: You can check the code by miaom 30061008

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

      thx. 432 people passed pretest, and now 81 left. miaom code let me realize my algorithm is wrong(TLE) (:з」∠)

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

      Wait — you need to check all possibilities for final gcd or what?

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

        Yes, you should check from 1 to the maximum number of the array.

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

I think the point decrease speed was not adjusted for a 2:30 long contest.

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

How to solve C? Don't tell me that the intended way to calculate the Grundy number is DP on bitmask...

PS: Btw, RIP yellow color T_T

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

    I think the answer is "Yes". The number of states is pretty small.

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

      How I can understand it, if maximum degree is 30 as log2(1e9)?

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

        I also didn't solve the problem because of this, but now I think I understand why it works. Let's look at states by their maximum set bit. For states where this bit  ≤ 20, we obviously have  < 220 states that we can reach.

        Now for bits  > 20, for example 23, the number of states is bounded by the number of ways we can reach 23 from 30 by performing subtractions each step, which is basically  < 27.

        In simpler words the number of states with the maximum bit k is  < min(2k, 230 - k).

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

          I don't really get your idea there. Could you elaborate it more specifically?

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

            Yeah, let me try explain it in a better way. The problem is when p = 2 (p is the prime factor).

            Basically we'll have at most 1 state where the maximum nonzero bit is 30, at most 2 states where it's 29, at most 4 states where it's 28, etc. Thus we need to look at how many states that initial state spawns.

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

              I think I get your idea. So, the maximum number of state is not 230, but 215, right?

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

                Yes.

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

                  So it turned out that the solution actually involve an elegant observation, not just a "brute force and pray that it'll pass" problem.

                  Thanks for your explanation!

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

    I think it is. For numbers bigger then 2 is easy but I can't show that for 2 number of states is small.

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

    If we calculate only DP values that we really need, there could be much less values to calculate. But I can't even make an upper estimate for the count for these values...

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

    If by "DP on bitmask" you mean "backtrack with memoization" then yes, I believe it's intended.

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

Wrong answer on test 3 (Div 2. C). What's test 3 ??? Why wrong ?

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

    did you check the trivial cases n = 1 and n = 2?

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

I see a lot of submission for Div 2 C checking all i,j,k. And there I was thinking of some fancy algorithm to cut down the runtime :((

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

    Not fancy algorithm, but you could use pigeon hole principle to return 0 immediately if n >= 244, and then brute force from there... Think that might be intended solution

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

    That's what I thought as well. After thinking for half an hour I came up with this: Consider three points. Draw lines between the three points and then you see that only one of them can be good. From there we can deduce there is at most 1 good point. You can now compare the first three points to find one that might be the good point. If the triangle created by the first three points is acute, then just choose one of them to be your candidate even though you know it is not actually a good point. Then do the same thing with your current candidate and some other two points you want to test. After less than n tests you will have a single point that may or may not be good. From there, just use an N^2 algorithm to see if it is actually good or not. I'm not sure if this works yet since system testing is not over but I'm just putting my thought out there.

    EDIT: it just passed system tests

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

GeoForces!!!

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

Geometry Geometry everywhere :||||||||||||||

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

For Div2B : the two cases that can produce a "yes" are:

1- the triangle has 3 equal sides.

2- the triangle has a right angle centered in point b and distance(a,b) = distance(b,c).

what am i missing here ?

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

    any isosceles triangle with ab=bc will do the job

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

      No. The triangle must have a positive area and have a right angle at point b

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

        No. Right angle does nothing. Center of rotation will be circumcenter of triangle ABC and only thing you need is AB = BC and A,B,C are not collinear. I dont know why you think right angle is important.

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

anyone know how to solve 1B in a non-hacky way? I am no good at math

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

    You can see my submission, it runs in O(10^6log(10^6)).

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

      Can you please explain what's happening? I'm still confused.

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

        My submission just got wa on 61. :(

        I think it should be some edge case I missed (EDIT: yep, a very stupid one). What I did is fix some final gcd. Every number has to be a multiple of this gcd. We have two options, either delete the number or make it a multiple of this gcd. First find which of the options is suitable. Let's say you increment some number k times to make it a multiple of the gcd, then for it to be optimal, k*y must less than or equal to x i.e k <= floor(y/x) otherwise we could just delete the number instead of increasing it. Now fix two consecutive multiples of this gcd, call them z1 and z2 and z1 < z2. You need to change the numbers between them. So increase the numbers which are in the range [z2-k, z2] and delete the remaining ones i.e [z1, z2-k-1]. To efficiently calculate this, use some prefix sums.

        My AC code: http://mirror.codeforces.com/contest/851/submission/30081999

        Let me know if something is still unclear.

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

I thought I saw RoadToMaster's coding style and templates of problem D and E div.2 are different. Am I wrong ?

P/s. He/She is now at rank 8.

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

Ignore

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

Why the hell would anyone put 100+ test cases on div2A? It's just gonna take a really long time to test, and I doubt it will be more efficient than having like 30

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

I have a feeling that system test is going to destroy many people (including me) :v

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

many O(n3)s passed on div1A. Why not make n ≤ 3000?

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

    Because answer is 0 for n > 64 and one will eventually end up with 64n2 operations?

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

      ?

      if(n>64) { cout<<0<<endl; return 0; }

      so upper limit on n has no meaning, it can be even 1018

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

        But input would TLE on their side with 1e18 =)

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

        Could you elaborate your proof for n > 64?

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

      n > 64 is very high upper bound. Answer will be zero if n > 11. AC solution http://mirror.codeforces.com/contest/850/submission/30076671

      I can give you an intuitive proof. First of all for n >= 3, answer could not be greater than 1, thus we only need to find this point. So lets think about the upper bound in 2D, then we will extend our solution to 5D. Without loss of generality, assume the point which we want to find to be the origin. You could only place 4 points(two on each axis, one on positive side and other on negative side of the axis) such that point at origin is a good point. Now think about 3D. In going from 2D to 3D we can only place 2 more points(on the 3rd axis) such that origin is a good point. Hence in 5D, there can be atmost 10 points excluding the origin. Thus for n > 11 answer will be 0.

      My solution's complexity was O(n + 113), which is a pure brute-force solution after considering the above observation.

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

Div.2 C: is acute (i.e. strictly less than 90°) but it was not said that acute is strictly more than 0 degrees.

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

    Let's continue your thought.
    What if  - 1,  - 2,  - 3, ... are also acute? What would it mean to be obtuse?

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

In div2D, isnt this conditions enough?

If initially gcd > 1, then answer = 0

Else

ans = min(cost(2) , min(cost(x)) for all x, where x is an odd number present in an array, and cost(x) is the cost to make gcd equal to x.

PS — got it, its wrong.

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

    Consider such circumstance that you have an array teemed with odd numbers along with a single 1, where you will proceed cost(x) for N times.

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

    No.

    Let's say you have 9 14 15 21 the best answer would be cost(3).

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

    3 1000000 1 9 9 2

    'odd number present in an array' and 'GCD = x' may not satisfy at the same time

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

    Okay, how about this case: 2 9 21 let modification cost to be A, removal cost to be exorbitant then cost(2) = 2a, cost(9) = 7a+6a, cost(21) = 19a+12a however,cost(3) = a

    In this case the condition you have proposed seems to be insufficient.

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

    The fact is it depend on prime make it :) :)

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

In problem A shouldn't an acute angle be strictly greater than 0°? https://en.wikipedia.org/wiki/Angle

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

When it takes you 5mins to read,solve & submit problem D(got WA but still impressed) :D

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

    A similar problem was once on a Quera contest and here the pretests were too weak so you just had to copy your code from the other problem.

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

F seems cool. I have a pretty unproven guess at the solution. Maybe somebody could verify?

Let E(something) be the expected time taken for something to happen, and | inside meaning conditionality.

Let's ignore mod P, because we can.

ans = sum over colours of P(colour i dominates eventually) * E(1 colour let| colour i dominates).

So all we need is to evaluate E(1 colour let| colour i dominates). Clearly easy. cough

All we need to care about is how many balls of i there are at a given moment. Define F(k) to be E(dominates starting from k balls of colour i | colour i eventually dominates).

We handwave and pretend that we can treat it as if transitions happen every step, but scale the duration of the step accordingly. (You are feeling extreeeemely sleeeepy...)

Then since we know that for an unbiased random walk starting from 0, the probability of hitting -a before b is a/(a+b), the transitions must be (conditionally) weighted in ratio k+1:k-1.

Now we form a linear equation for F(k): F(k) = T + (k-1)/2k * F(k-1) + (k+1)/2k * F(k+1), where T, the expected time is (kC2 + (n-k)C2)/nC2.

Solving this takes O(N^2) time and we are done.

Anyone knows if this is correct and if so, is there any way to justify the handwaving step?

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

    "Then since we know that for an unbiased random walk starting from 0, the probability of hitting -a before b is a/(a+b)" — but here our random walk is not unbiased. I also don't get "the transitions must be (conditionally) weighted in ratio k+1:k-1."

    Moreover I don't think that "handwaving step" is correct, I do not know how to exchange between problems with transition every step and not in every step, because avergae waiting time is different for different number of balls in our color.

    Moreover I don't know where did you get O(n^2).

    However I believe that we can reach conclusion using your logic. We just need to work out a lot of formulas and hope that we will get something that will be possible to evaluate in time.

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

      Thanks for the reply.

      The random walk is unbiased -- the probability of converting colour A to notA is the same as converting colour notA to A. (since the probabilities of exchanging orders of draw is the same).

      For the weightage of the ratios, we have:

      P(transition to k-1 balls | a transition happens and colour i eventually dominates) = P(k-1 balls eventually dominate)/2 / P(k-1 balls eventually dominate)/2 + P(k+1 balls eventually dominate)/2, where /2 is the probability of the transitions happening.

      The linear equations are of form aF(i-1)+bF(i)+cF(i+1) = d. So the matrix looks like:

      XXOOO|? XXXOO|? OXXXO|? OOXXX|? OOOXX|?

      whereby gaussian elimination actually can take O(N) time.

      Handwaving is handwaving. I can't defend that.

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

Screencast

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

LOL. Many O(N^3) solutions passed Div2 C. And all of them using C++. Why not decrease input to pass time limit not only using C++ ?

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

    They are not actually N^3. If N is large, it takes very little time to ensure that points are bad.

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

    Can you share some link to solution O(N^3) please.

    Edit: I found one.

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

Tests of Div1 B are too week. This accepted submission fails with this test.

499999 1000000000 1 1 3 5 7 9 11 13 15 17 19 .... 999991 999993 999995 999997 (all odd numbers except 999999)

The answer is 499999, to make all numbers even. But this program outputs 500000.

30079608

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

I have seen many solutions of DIV2C. Many solutions which have O(n^3) time complexity passed system test. How is it possible with n=1000 and time limit of 2 secs? According to me, 1s has almost 10^7 iterations. Someone explain this to me or Correct me if i am wrong!

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

    Codeforces judge servers are quite fast. It can run a simple loop of 10^9 iterations within 2 seconds.

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

      are you sure?

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

        If you can't believe that, try some custom invocations.

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

          i didn't solve it. Thought O(n^3) will give TLE. How to judge the time limit? There should be any principle.

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

            Don't you know what the custom invocation is?

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

              i know:). I just told u how cheated i m feeling right now

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

    Apparently codeforces uses fast computers, which can process over 1 billion simple operations in 1 second, especially in C++. Not sure if pruning helps squeeze the time limit.

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

    If you have a break in the right place, the complexity is something like n^2*2^5, even though it looks like n^3 at first glance.

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

      i didn't solve it. Thought O(n^3) will give TLE. How to judge the time limit? There should be any principle.

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

        It's very approximate. Custom invocation helps. In this particular problem, O(n^3) probably does actually TLE. If you break when you find an acute angle, the complexity is less than O(n^3), because for large n there are many acute angles (see the editorial for details when it gets posted).

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

      in my implementation: with the break it runs on 15ms, without the break it runs in 608ms, note that without the break the number of loop iterations is nearly 5 milliars (approximately n^3 * 5), how does it pass with only 608ms ?! is it because the loop iterations contain very simple operations ?

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

Last contest I got hacked because of constant seed, so people calculated my queries and made test exactly aganist me. Today in B I had giant, visible, readable debug, when result was 0 I was printing some stupid number, and no hacks. Wtf guys? XD

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

    I had two ridiculously stupid bugs in B/C and also noone bothered to hack. Don't you really see wrong array sizes? =(

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

80% of submissions for B were some random obviously wrong greedy. WTF guys, are you hoping that it just happens to pass system tests? Because if so, you're absolutely right, some of those greedys did pass... Not blaming the authors, it's hard to kill every single heuristic in such a problem.

I should have continued hacking instead of trying D...

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

Can somebody explain div2C/div1A ? Got WA on system test 19, although my code is very similar to many accepted ones.

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

My code in the contest mistakenly treat the second operation as "decrease by 1" (not "increase by 1" as the statement), and it passed pretests. What the hell?!?

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

This contest made me wanna tell a deaf person that a blind person is looking at him :v

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

Why haven't all hacks been added to system testing?

For example, div2B

But i don't see it in the tests.

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

That feeling when you failed D because you forgot this :(

sort(a, a + m);
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

Can anyone help me in div2-C (Five Dimensional Points).

My code fails for n<3. I am confused that, point is bad if there exists an acute angle. But if only a single point is given, what will you do? Similarly 2 points form a line and not an angle. I took both of them 0 and failed :( .

Can someone possible help me out here :)

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

    Read about "vacuous truth".

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

    I was very confused as well, about n=2. If n=2, both points are 'good', because there is no third point that would make them 'bad'.

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

    In case n <= 2, points are good, since doesn't exist 3 points so you can't make the angle.

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

For problem E, would it be correct to do this, for each prime, store the distinct exponents of it among all Ai and reduce the problem to finding the grundy number of (1, 2, ...., k) where k is the number of distinct exponents and the game is played by selecting some element and subtracting it from all elements greater than it. I think I have worded this poorly but I can't think of a better way to write this.

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

    That's correct but you can optimize it using bits (use a bitmask for the exponents).

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

      That was my initial guess but after trying some values, I found a matching sequence in OEIS: http://oeis.org/A025480 but I am getting WA on test 18 so I am wondering if something is wrong with the sequence on OEIS.

      My submission: http://mirror.codeforces.com/contest/851/submission/30064152

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

        That doesn't look like the same problem =/

        "These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap." This looks totally different. Edit: also, the value depends on the exponents too, not just the amount of exponents.

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

          Yeah but the grundy values I calculated turned out to be really similar.

          k = 1, the set is (1), grundy value is 1.

          k = 2, the set is (1, 2), only reachable state is (1), so grundy value is 0.

          k = 3, the set is (1, 2, 3), reachable states: (1, 2), (1). Grundy value: 2

          k = 4, set: (1, 2, 3, 4), reachable states: (1,2,3), (1,2). Grundy value: 1

          k = 5, set: (1, 2, 3, 4, 5), reachable states: (1,2,3,4), (1,2,3), (1,2). Grundy value: 3

          I calculated upto k = 7 and they matched with the sequence on OEIS. Am I calculating the grundy values incorrectly or is it just some coincidence that they are same? :/

          EDIT: Didn't see your edit, can you please explain why it depends on the values of exponents?

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

            For example:

            Take a set with only 1 exponent (n), its grundy value is n. Why? Because it works as a single stack.

            I see, you misunderstood the way the problem is modeled. You have a set of numbers and you will take a number k <= the greatest value of this set and subtract it from any number >= k. You erase any number that results in 0.

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

              Oops, really sorry for dragging this stupid discussion. I should really get some sleep now. Thanks for the help. :D

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

When the editorial will be available?

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

Could someone take some time to look over my solution and tell me what's wrong? I would really apreciate it http://mirror.codeforces.com/contest/851/submission/30083263

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

Finally reached cyan :D

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

After contest when you see brute force could pass :( #Div2 C

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

i submitted my solution for B in c++14 got WA on 40th test case on system testing and the same code i submitted in c++11 after the contest then it got accepted ....can anyone explain what is the problem with doubles and sqrt() sort of functions in different c++ compilers

link to the the code which got WA in c++14 30075619

and the same code that got WA in c++14 got accept in c++11 30083224

/* -_- depressed and saddened ....i dont know why i used sqrt funtion... though i could have compared the square of the distances using long long or i should have submitted in c++11 and simply could have got AC -_- */

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

    If u deal with doubles, dont forget to check equality like this if( abs( x — y ) < e ), where e is some small number, usually 0.000001 or something.

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

Arpa: The official results page seems to be blocked. Could you provide screenshots or something? Thanks

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

So happy that I skipped this contest. Problems and editorial seem so shit like the announcement. Thanks for wasing this round.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Now I know the importance of Geometry :D
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div 2E can someone point me to a tutorial on bitmasking and how it relates to DP? I got as far as "Grundy numbers on each prime, and it only matters which p^k appear" but couldn't figure out how to calculate them.

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

By when can I expect the tshirt to be delivered?

→ Reply