sidprasad's blog

By sidprasad, 8 years ago, In English

Hi Codeforces!

Programming Club, IIT Indore and Fluxus 2017 are proud to present, for the first time on Codeforces, our flagship event, Divide By Zero!

The contest is going to be held on Monday, 20th Feb at 9:35PM IST.

Prizes: Codeforces T-shirts for top 15 overall and top 15 in India.

Thanks to the following people for making this round possible:

There are 7 problems, and 2.5 hours to solve them. The points distribution will be updated later.

Fluxus is the annual techno-cultural festival of Indian Institute of Technology, Indore. It is a 3-day event and generally held in the month of February. Started in 2011, Fluxus is the largest college festival of central India.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500-1000-1250-1750-2000-2250-2750.

UPD2: Thanks a lot everyone for your participation!

We hope you all enjoyed the contest. Yes, there were a few things we could've done better, and unfortunately the system was down for a while, We sincerely thank the CF team for dealing with it in the nick of time.

This was our first (of many, hopefully) contest on Codeforces. We request you to fill in this form with your feedback so that we can do better next time. Thank you!

The following users win T-shirts! Congrats!

Overall Top 15:

  1. y0105w49
  2. W4yneb0t
  3. V--o_o--V
  4. Merkurev
  5. anta
  6. I_love_Tanya_Romanova
  7. Endagorion
  8. BigBag
  9. HYPERHYPERHYPERCUBELOVER
  10. jqdai0815
  11. natsugiri
  12. mnbvmar
  13. halyavin
  14. Shik
  15. Aeon

Indian Top 15:

  1. Sumeet.Varma
  2. rajat1603
  3. xorfire
  4. memset123
  5. animeshf
  6. akulsareen
  7. shubham1694
  8. alecsyde
  9. AnonymousBunny
  10. ajinkya1p3
  11. mohitbindal
  12. wittyskull
  13. chintu
  14. ajs97
  15. polingy

UPD3: Editorial

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

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Good luck !

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

Great.Looking forward to it.

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

Cool! Must participate in. Thanks for contest

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

Hehe Now would be a fight because of the T-shirts)

Всё кароч, ща будет мясо из-за маечек)

»
8 years ago, # |
  Vote: I like it -18 Vote: I do not like it

13 people worked to make this round !!

so it has many cartoons and long statements :D

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

    You will be surprised.

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

    Everyone wrote one line in each problem statement :D

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

Someone posted a photo on the last round's blog..About Pigeon Hole theory.. 13 writers made me remind of that :'|

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

It had better the T-shirts was for random people from 1..500(for example).Then there will be a chance to win it!!!

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

...

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

It's not customary to ask if it's a rated, so I have to come up with different question...

"Prizes: Codeforces T-shirts for top 15 overall and top 15 in India."

Is it racist?

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

    Not at all, To Increase the chance to get candidates for onsite events at Host Location. I think it is just for promotion for Local Geographic.

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

    I don't know if it's racist, but it's definitely stupid.

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

      why when an Iranian writes a comments you guys gang up on him and give him/her some negative feedbacks and he is right its idiotic why cant you accept the fact that he is right and he didnt say anything to offend any one i know you give me dislikes but can u answer me why?

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

        It is none of your business ! :O

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

        "why when an Iranian writes a comments you guys gang up on him and give him/her some negative feedbacks"
        believe me, when I press down/up vote, I don't get into his/her account and see what is his nationality
        I just press the F button
        the point is that neither you or him didn't explain why do you think it's stupid and we don't think it's stupid, so we press downvote
        simple right ?
        we aren't racist if we gave downvote to someone

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

          "I just press the F button"

          Learnt something new today :D

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

          the thing you are saying is correct but i saw a bout a dozen comments that some of the was even my self that i wished good luck for the participants of some contest but ive got about 20 downvotes and i saw some guy offering a good product here which is absolutely irrelevant and he got more than 30 up vote soooo what is that u say and thank u for being reasonable not like the other guys

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

Well done! because you say thanks to MikeMirzayanov

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

So now codeforces is not just Russia, Spreading legs.

good work mike and team

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

    'Spreading wings' is the English phrase for expanding to and exploring new realms.

    'Spreading legs' means sexual enticement and promiscuity.

»
8 years ago, # |
Rev. 2   Vote: I like it +58 Vote: I do not like it

I don't know why, but I feel some math problems

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

Finally a contest with its time given in IST :D

No need to convert to IST from UTC :P

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

    ...you can see the contest in your local time if you go to the contests tab.

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

I hasn't had a T-Shirt before :'(

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

Can I register now? I forgot yesterday and now I am seeing it's Registration is completed!

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

    Of course you can. You should click that "Register now »" and join it.

»
8 years ago, # |
Rev. 3   Vote: I like it -103 Vote: I do not like it

India is becoming popular day by day in terms of organizing programming contest in Codeforces.

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

    YES !!! INDIA ROCKS !!! ALL OTHER COUNTRIES SUCK !!! :) :) :)

    इंडिया !!!!!!!!!!!!!!!!!!

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

      WHY ALL THIS DOWNVOTES !!! :( READ THIS BUTTHURT OTHER COUNTRIES !

      Its the contribution of Indians to every field known to men that makes India one of the greatest country of the world . In the words of other great personalities :

      Will Durant, American historian: "India was the motherland of our race, and Sanskrit the mother of Europe's languages: she was the mother of our philosophy; mother, through the Arabs, of much of our mathematics; mother, through the Buddha, of the ideals embodied in Christianity; mother, through the village community, of self-government and democracy. Mother India is in many ways the mother of us all".
      Mark Twain, American author: "India is, the cradle of the human race, the birthplace of human speech, the mother of history, the grandmother of legend, and the great grand mother of tradition. Our most valuable and most instructive materials in the history of man are treasured up in India only. "
      Albert Einstein, American scientist: "We owe a lot to the Indians, who taught us how to count, without which no worthwhile scientific discovery could have been made. "
      Max Mueller, German scholar: If I were asked under what sky the human mind has most fully developed some of its choicest gifts, has most deeply pondered on the greatest problems of life, and has found solutions, I should point to India.
      Romain Rolland, French scholar : "If there is one place on the face of earth where all the dreams of living men have found a home from the very earliest days when man began the dream of existence, it is India. "
      R.W. emerson, American Author: In the great books of India, an empire spoke to us, nothing small or unworthy, but large, serene, consistent, the voice of an old intelligence, which in another age and climate had pondered and thus disposed of the questions that exercise us.
      Hu Shih, former Ambassador of China to USA: "India conquered and dominated China culturally for 20 centuries without ever having to send a single soldier across her border. "
      Keith Bellows, National Geographic Society : "There are some parts of the world that, once visited, get into your heart and won't go. For me, India is such a place. When I first visited, I was stunned by the richness of the land, by its lush beauty and exotic architecture, by its ability to overload the senses with the pure, concentrated intensity of its colors, smells, tastes, and sounds... I had been seeing the world in black & white

      Some great facts about India: 1)Each and every 28 states and 7 union territories of India, have their own LANGUAGE, CLOTHING, CUISINE and LOOK.

      2)India alone has the highest number of languages in the world with more than 300 I guess.

      3)In India alone you'll find all types of food ranging from sweetest to most spicy food on Earth. I'm not talking about foreign cuisine or restaurants. Its the local food of different states.

      4)On this planet, you will notice that the highest number of religions present, are in India. More than 8-Christianity, Islam, Judaism, Hinduism, Jainism, Sikhism, Zoroastrianism, Buddhism.

      After reading all these facts , you might be convinced that India is a great country . If you are , you have clearly misunderstood what makes a country great . Its not the history that makes a country great . India is a barren naked land without its cultures, its colors, its religions. However, as a person cannot be deemed great for the clothes he wears; his shoes or hairstyle or the fragrance he chooses to spray over himself, I doubt if greatness should lie in the clothes of cultures, color or monuments India wears. Not only is such a statement highly propagandist, it deems other nations with perhaps equally diverse cultures, peoples and religions un-great. For greatness is a crown for the elite few.

      And for all its culture, its history, its religion, its minarets, its color, India like any other country is made of people. Human beings. Little pink creatures, with dark hearts. This is again not a license to greatness, because every country I know of, is made up of human beings.

      The man on the street, the rickshaw puller, the tobacco- paan seller, will easily enter into an animated debate on the issue of India’s greatness. To them, all the corruption, the famines (and the Rs. 3 cheques), the electricity shortages, the broken roads, the stinking sewers, peddled to them by their hindi dailies, are signs of a nation gone to the dogs, faltering and staggering and falling.

      But the same paan-wallah, the rickshaw puller, will glue themselves to any available radio set if India is playing hockey/ cricket; will talk in higher, happier tones of Sunita Williams, as if she were their blood sister; and celebrate the Indo-US nuclear deal (without being sure of its meaning). Thus is India great, for its people never give up hope. For all our rot and rust and famine and flood, we never stop believing in the Indian dream. Thus, we call her "Mother India" for its peoples are always expecting.

      In the end , its the people of India (except those corrupt politicians) who make this country great .

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

        ALL OTHER COUNTRIES SUCK !!! :) :) :)

        Thats why u have been downvoted(i think)

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

Hope there won't be cheaters :) Good luck everyone.

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

    no cheaters means no work for you :D

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

Codeforces judging system seems down! God knows what will happen! :(

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

Good luck to everyone

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

I hope to redeem myself from the previous contest. :)

»
8 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Will it be a rated one? I did not see u guys mentioning it anywhere.

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

"largest college festival of central India" — every central India college fest claims this :P

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

I hope it's good contest

»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

The points distribution shows that the problems don't have gap in their complexity! Good!

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

feel sleepy at midnight zzz~

»
8 years ago, # |
Rev. 2   Vote: I like it +78 Vote: I do not like it

Rating prediction for this contest could be found here (after contest begins)

Extensions:

About CF-Predictor

Good luck & high rating to everyone!

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

damn . cant understand problem c again :|

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

too easy I forgot to submit !!

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

Why the solution of number B is in queue for a long time????

»
8 years ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

admit it
great contest
UPD : LOL the judge system has downed since I wrote this comment
but despite of all these issues, I think the problems are very interesting and the problem statements are very clear

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

Judge system down :(

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

It seems like queue of hack is very big! Submitted about 8 minutes ago , Still in queue!

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

Queue :(

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

10 minutes in queue.

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

Seems like unrated round :(

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

Whatever Happens!! I want to see ratings changed!! :P

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

Just after the announcement on 'C' judge system went down! Submission of 'C' everywhere!!

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

Is the system divided by zero?

Cf get runtime error xD

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

    yeah i have no idea why i am getting runtime error

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

      did you ever figure this out? also got runtime error on B pretest 5 with python

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

        yeah same here; thats because of overflow with range/xrange switching to while loop may help.

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

          Thanks, would never have guessed that. It works fine on locally on the same example with pypy and python2.7.12.

»
8 years ago, # |
  Vote: I like it -19 Vote: I do not like it

solutions are in queue for a very long time . Contest might become unrated.

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

The contest should be unrated.

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

please extend the time of contest

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

    yes please extend time if its rated.

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

either time should be extended or the contest should be made unrated!

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Not only the judging system ... The whole site is maybe slowed down :( Any page is taking near 3-4 minutes to load.. My Internet Speed is ok.. :(

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

Make it unrated!! 25 min wait times are unreasonable.

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

    The time was extended, queue stabilized, I dont see any reasons to make it unrated ...

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

      When one submits a Wrong solution and think that this was right.....

      But after ~25 minutes he found that it was wrong -_-

      This round should be unrated :(

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

      Maybe the main reason it's good round for you?

»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Some people for some reason do not have access to debug tools other than codeforce which went down for an hour. Rated, seriously?

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

In Problem C I used the trivial solution :D I do the operations until I find that my array is repeated :D

Will this exceed the Time limit in some cases ? :p

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

    If you are checking for repetition, each of 'k' iterations could take O(n) time for comparison and O(n*log(n)) for sorting. So if the array doesn't repeat then there is a good chance that the solution would timeout.

»
8 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

RIP those that didn't saw the unusual time limit on Problem C.

It took me 2 hours to realize that (+ xi <= 1000) and then write solution with O(k*1000)

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

    Same here :(

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

    Should not it be k*1023 ? 959 xor 64 is 1023

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

    How does this solution look like?

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

      Use counting sort kindof. So you now how much elements you need to xor and how much will remain the same. 24848957

»
8 years ago, # |
Rev. 2   Vote: I like it +162 Vote: I do not like it

So many times someone said (Swistakk for example) that scoring should form something closer to a geometric progression. My G submitted in last minutes after two WA's is worth 912 points. Awesome. I hope that my B will pass because it's worth more.

Was points loss adjusted to a longer contest? If not, it only made things worse.

EDIT: fortunately my B passed

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

    Points loss was the 2:00 formula for a 2:30 + 0:10 contest. Did asking that really take less effort than subtracting 2 numbers?

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

      Subtracting what 2 numbers? I still don't know how to easily say if points loss was adjusted.

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

        In a 2:00 contest, a task worth x points should lose x/250 points per minute.

        Check what minute you submitted, how many points below the maximum you are (not counting points lost to wrong submissions) and discover that you indeed lost x/250 per minute.

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

          Why should I know/remember that x/250 formula? And we're talking about dividing here (or at least multiplying) so things become harder than just subtracting ;p

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

            You should remember it because if you did, you could have predicted your score for G (and maybe hacked instead) instead of whining after the contest.

            Disclaimer: I agree that this is a bad mechanic and should be changed.

            Disclaimer 2: Solving G is probably a more fun and productive use of your time than hacking, unless you just want rating.

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

              I don't have to remember it because on the problem page I can see (on the right side) how many points I would get submitting right now. I knew during solving that I won't get much. It was still an optimal strategy after hacking — I have read all solutions to A in my room and hacked many of them. Following your logic: you should find me on the leaderboard and see that before arguing.

              My ranting has goal: organizers should use better scoring and should always (?) adjust scoring. It will make contests better.

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

                You should wait for systests to finish before mentioning the leaderboard.

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

                  Why? I got TLE in G and my hacks weren't canceled. Which of my comments makes less sense now?

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

                  The statement that solving G is better than trying to get even more hacks.

                  Of course, arguing based on 1 data point isn't very convincing, I'm just shitposting for the sake of shitposting.

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

                  I think we don't agree about the definition of "optimal strategy" in a case when a player (participant in this case) doesn't have full information about the game.

                  EDIT: Also, congratulations for your place. Let's say that your strategy turned out to be more optimal. What an ugly sentence I've just created.

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

    ranting part 2

    I think that tricky tests with f = 0 or w = 0 in 768F - Barrels and boxes should be included in pretests. You can't expect people to hack this problem because in most of rooms at most 1 person solves such a problem. So you just give WA's to all people that miss that thing. And for many it was misreading the statement (understanding that both f and w are positive), not forgetting about corner case.

    Let me also say something positive: I liked 768G - The Winds of Winter.

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

    Hello not adjusted drain, my old friend. I've come to butthurt about you again.

    I can't believe that not adjusted drain and bad scoring is still a thing. Completely trivial D, E worth 1750 and 2000 points and G worth 2750, sounds legit.

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

Could someone please explain how to solve B? Thanks.

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

    Notice that, x will produce an array of length 2log(x)⌋ + 1 - 1. Let's call this number len(x)

    I solved it recursively,

    f(x, l, r, s) = number of ones at the intersection between the intervals [s, s + len(x) - 1] and [l, r]

    If [s, s + len(x) - 1] is totally contained in [l, r] then the answer is x. If they don't intersect, the answer is 0.

    Otherwise, f(x / 2, l, r, s) + f(xmod2, l, r, s + len(x / 2)) + f(x / 2, l, r, s + len(x / 2) + 1)

    Answer is f(x, l, r, s = 1)

    I think this solution is too complicated, though :(

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

      Thanks! Any solution is better than no solution to me :)

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

    Divide n by 2 until it is 0 and put that in an array in ascending order.

    You can see a pattern generated by the number and the final set.

    Take the index of one 1/0 in the list. Then take the highest power of two that divides that index. The expoent of the power will be exactly the index of the corresponding number that generated it in the array that we built. Therefore, if the number in the array is even, it will be 0, if it is odd, it will be 1.

    Thus, we can just iterate from l to r, checking the powers of two, and adding 1 or 0 to a counter according to the prebuilt array.

    i.e. suppose n is 17

    the array built will be 1 2 4 8 17

    suppose l is 12 and r is 16

    12 is divided by 4, which is 2^2, the index 2 in the array is 4, which is even, so the position 12 in the list is 0

    13 is divided by 1 which is 2^0, the index 0 in the array is 1, which is odd, so the position 13 in the list is 1

    14 is divided by 2 which is 2^1, the index 1 in the array is 2, which is even, so the position 14 in the list is 0

    15 gives the same as 13 (and actually every odd index)

    16 is divided by 16 which is 2^4, the index 4 in the array is 17, which is odd, so the position 16 in the list is 1 and so on.

    I find that this is the simplest way to solve the problem (my solution was 17 lines long). Unfortunately my solution received Runtime Error because I forgot to test when n = 0.

    Expected complexity O(log N + 50 * (R — L))

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

      Thanks! Would you mind explaining the proof behind your method?

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

problem B why i get TLE ..complexity is O((r-l) LOGN * LOG N ) ?

r-l <=10e5

here

»
8 years ago, # |
Rev. 2   Vote: I like it +212 Vote: I do not like it

read G

persistent dynamic online balanced link-cut tree decomposition

hack greens instead

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

    I used a segment tree of multisets only.

    For each vertex we want to know the list of sizes of trees that will remain after this vertex is cut. Let BIG and SMALL denote the biggest and smallest of them. It's enough to consider moving some subtree of BIG into SMALL. It's optimal to make the size of moved subtree of size as close to (BIG-SMALL)/2 as possible. Let's see how to do it.

    We compute preorders and we build a segment tree of multisets. For any interval we want to know the set of sizes of subtrees with preorder in this interval. In O(log2) we can ask a structure about a size closes to some value.

    There is one hard thing left: if BIG turns out not a child of our vertex but its parent and everything above, then we should differently consider subtrees starting from somewhere on the path from our current vertex to the root. If the size of subtree was X initially and our current vertex is v then cutting and moving that subtree moves size X - a. So we need a second segment tree of multisets that will store sizes of subtrees that start somewhere on a path from the current vertex to the root. As we move deeper in a tree, we should remove elements from the first structure and insert them in the second one.

    EDIT: I got TLE. The complexity is with not so small constant factor. Maybe it can be implemented slightly better.

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

      I think you can get O(nlogn) if you use fractional cascading.

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

      Errichto, what did you do to get rid of TLE using segment trees of multisets? I tried to represent the multisets using maps, so we avoid some dynamic allocation, but I still got TLE: 25420160

      For the AC (25418820), I had to switch the preorder segment tree to use vectors instead of multisets (the merge sort style segment tree). This makes the segment tree unable to support updates, so I had to use "DSU on tree HLD style" to maintain the set of subsizes of outer vertices.

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

        Some constant factor optimizations. If I remember correctly, the main thing is that I replaced small multisets with vectors.

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

          And you sort these small vectors for every update, if necessary?

          Edit: Or maybe you just run linear passes, since the vectors are small?

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

    My reaction : https://ibb.co/i703Yv

»
8 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

Was B really hard or was it just me :(

edit — just a stupid mistake :/

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

    I think we have to find places of 0's and put them vector (maximum amount of them are 51). Then just find count of them in range [l, r]. After print r - l + 1 - cnt. O((l - r) * 51).

    UPD: This solution will get TLE and MLE. Sorry for wasting time.

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

      Not quite, consider n = 8

      [8]
      [4 0 4]
      [2 0 2 0 2 0 2]
      [1 0 1 0 1 0 1 0 1 0 1 0 1 0 1] 
      

      Thus 2^3 has 7 0s, so 2^50 Should have 2^50 — 1 zeros.

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

      I did segment tree way, divide left and right, check if the segment falls within range. But something went wrong, and I just couldn't debug it :(

      At least I found the mistake now

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

        Maybe looking solutions of top participants will help..

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

    it was interesting,but if you do a bit of brutforce on paper you would realize this:

    1.the resulting aray for number n is composed of res(n/2)+n%2+rez(n/2) 2.the number of elements it will have is 2^(log2(N)+1)-1

    this observations suggest a recursive function

    so you do a q(long long number,long long l,long long r) my code is here:https://ideone.com/kFdyY1

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

What's the matter with last contests? Bug, bug everywhere :(

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

Problem E get WA on pretest 17, can't find the bug..

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

    How do you solve it?

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

      Just some game theory about NIM.

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

        What do you do with NIM? I tried to think of something but failed.

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

          just do brute-force and fits the TL, but I don't know why I fail pretest 17..

          I use following state definition and brute force to calculate every dp[i][0]
          map<ll, int> dp[80];

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

            I found a pattern.
            1 repeat 2 times
            2 repeat 3 times
            3 repeats 4 times and so on..
            so grundy[1]=grundy[2]=1
            grundy[3]=grundy[4]=grundy[5]=2
            grundy[6]=grundy[7]=grundy[8]=grundy[9]=3... and so on.

            Edit : Sharing code, just in case someone wanted to see. It took about 8 secs on my pc.

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

              That pattern is simply: grundy[i]=maximum number j that 1+2+3+...+j = j*(j+1)/2 <= i

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

            You can just do brute-force to figure out that the Grundy numbers for the starting positions for each pile are 1, 1, 2, 2, 2, 3, 3, 3, 3... Then you won't need to slow your solution down by doing brute force.

»
8 years ago, # |
  Vote: I like it +241 Vote: I do not like it
if(n>2){

int lol=rand()%2;

if( lol%2 ) printf("NO\n");
else printf("YES\n");

return 0;

}   

get accepted on pretests in E ))))))))))))00000000)))))))))0
http://codeforces.me/contest/768/submission/24852367

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

How to solve E? I could not find out the Grundy numbers of the states?

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

    Brute forces could do the trick.

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

    I wrote a bruteforce and found its like 1,1,2,2,2,3,3,3,3... ith value repeated i+1 times...

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

    The Grundy number of each i is the maximum number j such j * (j + 1) / 2 <= i

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

    For every number a[i], calculate c[i] — number of 1 bits of a[i], and then it's just like at normal NIM game, xor between all c[i], 1 <= i <= N, and if this xor sum is equal to 0, the answer it's "YES", otherwise "NO"

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

    In dp(n, mask), we can modify mask to mask only 30 bits, because we will not subtract x (x > 30) from n more than once.
    solution : 24854077

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

the slow of system was to show as what's happening when you divide by zero :D

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

For F, I just realized that I misread the conditions, so in particular, if there are no wine barrels, it seems like the probability is 1 (since there is no stack with height <= h, the condition is trivially satisfied). I printed zero, since I misread it as there is at least one stack, and all stacks have height > h.

I'm surprised that this case isn't in the pretest. Also, I'm not sure I like having the condition that there may be zero wine barrels or food barrels since this is hardcoding special cases and not really related to solving the main problem.

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

    I have the same bug, I misread it as "It is guaranteed that he has at least one food box AND at least one wine barrel." :-(

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

      Same here. I was wondering why F is F, cause it seemed to be too easy for one of the hardest problems. Now I see that the trickiest part of the problem was "read the statement carefully and do not forget to handle corner cases" )

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

    I'm much more stupid. I asked a question:

    "It is guaranteed that he has at least one food box or at least one wine barrel."
    is it equivalent to saying that 1 ≤ f, w?
    I'm asking because there is 0 ≤ f, w just before that

    I got answer: It's equivalent to 1<=f+w

    ... and I misread that answer and understood 1 <= f, w

    ;_;

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

    I was aware of that case and I hoped to hack someone. Unfortunately noone else submitted this problem in my room.

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

    More than 80 submissions failed system test because of this reason. :( And there are about 120 accepted submissions!

    It seems like authors are trying to decrease the number of accepted submissions for last problems by excluding special cases from pretests, instead of adding harder problems!

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

      ...

      Problem is as hard as many people are able to solve it (the more people can solve it, the easier the problem).

      It does not matter whether you almost solved the problem but you missed a special case or you did not have any idea how to solve it (no partial scores in codeforces — I recommend Hackerrank).

      The fact that almost nobody else in the room is not solving it and can't hack the solution, does not matter. You should think of all the cases upfront, before even submitting it.

      If you did not think of all the cases, you fail the problem. If it was a full feedback contest, then you would see the results during the contest. I totally do not understand your concerns.

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

        A problem is what is said in its statement. Weak test data doesn't make it easier, and weak pretests doesn't make it harder.

        "Problem is as hard as many people are able to solve it."

        I agree. But we have different opinions about "solving" a problem!

»
8 years ago, # |
Rev. 2   Vote: I like it +144 Vote: I do not like it

If feel this contest simply ... ought to be unrated. Nearly half the contest was feedback-less and the last 2 problems simply don't deserve their place as F and G for a division combined. I really appreciate the problem setters' efforts, but still.

Edit. As geniucos told me earlier, this was more of a Div2 + Div1 contest than a Div1 + Div2.

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

    Actually I said Div2 — Div1 (but your comment is not far anyway) as last div2 contest seemed to be harder than this one. Rated or unrated, one thing is for sure: the contest could hardly be regarded as good for div2 only, let alone a div1 + div2.

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

      It was for Div0 — for participants who like corner cases and hacking :)

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

    I also think so,A-F implementation only,G didn't read.And i'm only violet.

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

    Well, feedback-less problem is a good reason to make a contest unrated, but its difficulty is not.

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

      It was just a second reason (even though it shouldn't be required as you had to wait for up to 20 minutes to get the feedback for one of your submissions). From other point of view, the quality of problems and pretests was the lowest I've seen lately (or, actually, ever) in a CF round. I just can't believe that E was solved by 567 people and half of the sources on F failed on a case in which W or H is 0 (which of course was not part of pretests). How could the assessment of the difficulty of the problems be so far from the reality?

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

        Also, I still can not fully understand why did they have to express a statement about precision in such an odd manner in D. Saying eps < 10 - 7 implies picking eps = 0 would have been valid, too, rendering the first statement useless to begin with.

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

In problem F, is there any way to handle the case when q is divisible by 1e9+7?

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

    The task statement simply says q^-1 without mentioning that, so I (and probably a large percentage of the other 253 submissions) just assumed that case doesn't happen. I kinda hope we all get WA on systests.

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

      What should be q^-1 mod 1e9+7 if q is divisible ? Does it exist ?

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

        No, but if both p and q are 0 mod 1e9+7, then the reduced fraction p/q can lead to a well-defined pq^-1.

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

          Oh i see! but if p is not divisible then the answer simply doesn't exist. So i guess the problem is wrong ? :P

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

          According to the statement, formally, that is not the answer we should output in this case.

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

    The contest is named "Divide by zero", an evidence of the availability of that deadly corner case???

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

    Did you ask the judges during the contest?

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

    Cannot because q = C(f, f+w)

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

      Really nice reinterpretation. However, when H = F = W = 0, the answer should be 1 (as the probability for something that does not exist to have a particularity is 1). Of course, such cases cannot do anything but increase the beauty of the task (and the set, as it was ranked as second hardest)

      PS: I was being sarcastic on the part about the beauty of the problem, in case it's not obvious

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

    I actually asked them and they said such case will never happen.

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

Good problem-set and a well balanced contest imo. (Although it might have been on the easier side for Div 1 contestants)

Failed to calculate the Grundy Number for E question though. How is it calculated?

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

    bruteforce?

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

    i wrote a dp(number , mask) and ran it locally to get all values from 0 to 60 (took about 5 seconds to run)

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

I just screwed up this round but this might be the last pretest-passed submission. Cool

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

During the contest I (because of rushing and skipping the details) was solving such version of F: A configuration is good if any pile of wine has > h boxes. Is it still solvable in faster than O(N^2) time?

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

Does somebody know what pretest 4 on problem D was?

I've looked through other participants code,but the main ideea was the same.

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

Should I cry now or later ?

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

For Problem F, when f or w equals to 0, as a result ,p equals to 0 too.And how to calculate the inverse of 0 under mod 1e9+7?

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

Just a little feedback from me. I liked all of the problems, I think they are all pretty nice. But weren't they way too easy (at least up to F, didn't read G)? I know I wasn't among the fastest solvers but still, I read E early and solved it quite fast IMO. Also, I knew how to solve F almost immediately after reading it, bad that I read it too late. But anyway, difficulty is a relative term, depending on people and types of problems. So, nice round, thanks :)

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

    I think most problems were on the same level roughly. So most were on the easier side, but only A was the trivial implementation task that ABC usually are.

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

    Easy for you. I only managed to solve C correctly.

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

Is problem E's solution the same as nim problem? I saw some codes pass the pretest doing the same thing as the nim

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

    You can reduce it to a modified Nim, but just Nim won't pass. The second sample test is a winning position in Nim, but a losing positiom for the custom game.

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

please Explain why i got TLE ?

problem B ..complexity is O((r-l) LOGN * LOG N ) ? r-l <=10e5 Here

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

    Which is too slow. You need or better to pass.

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

      Not really, I'm quite sure my solution is (r-l)*log(n)*loglog(n) :)

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

        i modified it ..i used tree map to as MEMO for count Function and it ACC now

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

What was the approach for D? I computed the log of numerator and denominator of http://math.stackexchange.com/a/1007107/115535 . Then binary search till the desired n, number of days, is obtained. But could not pass the pretests!

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

    any ideas, guys!!!

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

    my idea is dynamic programming with dp[i][j] mean the probability at day i you get j orbs and it can be calculated as dp[i][j] = dp[i — 1][j — 1] * (k — j + 1) / k + dp[i][j] * j / k

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

      Thanks, you mean, dp[i][j] = dp[i — 1][j — 1] * (k — j + 1) / k + dp[i-1][j] * j / k, right?

      And also, what was the bound on num days?

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

    I had the same idea, but I didn't have time to code it...

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

    You linked to the formula in the second answer i believe.This formula is wrong. You are dividing the number of preferred combinations by total combinations assuming that each combination has equal probability of occurring, which is not the case. If you take a combination X[1], X[2]....., X[k] where X[i] is the frequency of type i, then this combination has probability of occurring (N! / (X[1]!X[2]!....X[k]!) / kN , where N is the number of days. This probability will be different for different combinations.

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

is supposed to TLE in B?

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

In problem C, if k is even nothing (besides sorting) in array won't be changed yes? If I'm wrong please correct me.

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

I think main tests of problem D are too weak.

If k = 2 and p = 1000, the answer is 2 (probability is 1/2, which is greater than )

However, some source code (example: 24838082) outputs 3 but passed main tests.

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

    I can't believe that k = 1 and k = 2 are not included. I think they should add those into the tests and rejudge before the ratings are released.

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

      Obviously they updated the ratings without rejudging. Contest authors these days tend to ignore comments from the community.

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

      Adding tests after the contest leads to strange situations. Should people be afraid to post "hah, my solution is wrong for this test: ..."? And what about solutions with hashes? Many solution can be hacked once you see it.

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

        This case is obviously different from hashing. We are talking about tests that should have been included when the problem is prepared.

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

          It's impossible to define a clear border — to say when tests should be added. I used to have the same opinion you have now. After many conversations and some thinking I changed my mind. Contest have clear rules: organizers prepare tests and your task is to pass them. You should be able to solve all valid tests but this is not what you get AC for. You get AC for passing tests prepared by organizers. Sometimes it allows to squeeze some too slow solution or get AC with an incorrect one — but judging is automatic and everybody is equal.

          EDIT: But ofc. I agree that tests should be strong in the first place and it's organizers' responsibility. Though I failed that task many times myself so I'm trying not to be very harsh to someone who did the same :D

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

            I agree that tests should not be added if it is ACM or IOI format where contestants get their results live, or if the points are given per case like in HackerRank. But I don't think that's an issue in Codeforces because the contestants well know that there will be system tests.

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

              All my arguments work for contests without full feedback too.

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

            Regarding the hashing problems, I agree that tests on hacking some hash functions should not be added in normal circumstances, as hashing functions can usually be hacked once you see it. So it is enough for the organizers to prepare cases that can reject the solutions that are wrong because of other stuffs.

            As you mentioned, organizers should be responsible to prepare strong tests. And it is obvious that corner cases should be regarded as part of strong tests as it is one of the contestants' goals to figure them out.

            If the tests are too weak(as mentioned by HYPERHYPERHYPERCUBELOVER), there are three main reasons that we should add tests in my opinion:

            1. As mentioned by microtony, adding tests after contest under Codeforces format do not create any unfair situations as those solutions still passed pretests. Contestants can still regard the new tests included in the System Test.
            2. It is organizers' responsibility to include such tests before the contest. So when those cases are not included, still, it is their responsibility to include them afterwards. Otherwise, organizers can be excluded from adding strong tests as they have no consequences even if they don't do so.
            3. It is unfair to those who have handled those corner cases if stronger tests are not included and added. Contestants who have handled corner cases should be ranked higher than those who have not. And moreover, it is much more important to guarantee so under contests with prizes as these may affect the ranking.

            I'm sorry if i wrote too long, but some of the recent contests were facing similar issues which lead me to think seriously.

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

              I understand reasons in favor of your opinion. You must understand reasons against it.

              Do you want a situation when after a contest people stress test solutions of others and try to break them, to move one place up? Someone will have to decide if a test should be added indeed, while it's impossible to clearly say what is a corner case and obviously should be added and what is not.

              still, it is their responsibility to include them afterwards

              ok, they can do it for upsolving

              It is unfair to those who have handled those corner cases if stronger tests are not included and added

              But they got AC and in the long run caring about corner cases gives better places obviously.

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

              It is possible that if the authors had come up with these tests, they would've included them in pretests. If I was an author, I would definitely do this. In this case it would've affected the competition in other way, so adding them now is not fair.

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

G with 978 points :(

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

Editorial Please !!

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

Can some one explain the logic of 3rd question?

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

    problem c look at the constraints 0<=ai<=1000 and 0<=x<=1000 , that means you will have at most 1001 distinct numbers in the initial array . and after taking xor with number you can maximum number with with all the 9 bit set .

    Fact 1: A^X=B , B^X=>A Maintain the count of each number arr[K][number]=count , after K operations . so when you are taking xor with i , that means you are taking roughly count/2 numbers and changing it to x^i . That means roughly count/2 element count increase for x^i .

    as K will be very huge and you make state for odd and even operations . - See code Solution

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

Seems that Problem E requires submitting a table, or your program needs to have a small constant. My program uses about 2.5s to calculate all the answer, which gives me confidence to submit. Then got TLE for big N only because N is very big :(

Constant... Constant... Constant...

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

Why did so many F's failed systests? I can't see any kind of corner case

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

    I think it is w=0 or f=0 (if w=0 answer is 1, if f=0 answer is w > h ? 1 : 0)

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

Practice season please.

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

I guess that without assert my B would be AC :/ Listen me my dear friends, don't use asserts on cp, just don't. :D

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

    I was telling you many times — do test your code. You should have run it for n = 0 before submitting.

»
8 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Sorry for the error.

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

    min = Math.**max**(min, a[i]);

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

    Can you explain how you tested it on the failed test case?

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

I messed up this contest...a silly mistake in problem A..(instead of i--,i was doing i++) . I messed up last contest also...was declaring array of size 10^5 instead of 2*10^5 for problem A. What is happening with me?

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

    The same happened with me. Just take a relax and do not think about anything. After some time you will surely be back on track :)

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

When can we upsolve?

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

[Problem D] Just curious, what did "the probability of (...) is at least , where ε  <  10 - 7 mean?

Assuming that our task was to find the minimum number of days after which the probability of collecting all the orbs is larger than : did you check if for all the feasible inputs the answer will not change when the float precision errors are taken into account? For example, the answer could have changed when pi = 500 ± 10 - 200 and our solutions (DP based on some floating-point calculations) wouldn't even notice that.

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

    I wrote the same solution in python using only integers, for all k I tried (including k = 1000) it gives the same answer as the c++ solution with long doubles and ε = 10 - 7.

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

    I wonder if using doubles and comparing the value against could be the reason for WA in test 19. 12 red coders including me got WA in that test.

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

      You did the comparisons against , though. :(

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

        Oh, I guess that's the reason. Thanks!

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

      I also got a WA on test 19 because a precision issues, but I was comparing against instead of .

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

      I'll be very sad if that's what causes WA :( I resubmitted to add epsilon.....

      [Edit] WA Case:

      935 1
      2
      

      I got 4607 with epsilon and 4608 (correct) without it ._.

»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

for B i used the same approach but he got ACC and i got TLE ? i use Java and he uses C++ .

c++

JAVA

THAT'S NOT FAIR ?

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

    c++ solution uses memoization in count function

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

      thank you very Much i didn't notice that ? how can i do the same in Java ?

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

        use a map, if a number is already count, you can find it's count in map

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

          yes i got ACC now .. thank yoooou very much .thank you lovely guys <3

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

problem D ->

http://codeforces.me/contest/768/submission/24841958 Why do i get wrong answer on pretest 4 , i used dp solution ??? on my machine the code outputs the correct answer , also on cpp.sh.

can some1 figure out what is wrong with my code ???

ive compiled with gcc 5.4.1 and also with 6.2.0 same result (the correct result) thank you

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

please add problems to practise.

»
8 years ago, # |
  Vote: I like it +66 Vote: I do not like it
balanced
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have an O(logN) solution for B. We can observe that the sum of number of ones in the expansion of n is n. f(n,l,r)=f(n,1,r)-f(n,1,l-1) and so now to calculate f(n,1,r) we can see where exactly r lies. Let M be the mid point of the expansion. If r lies to the left, we have a single call to f(n/2,1,r). Else we add n/2, n%2 and f(n/2,1,r-m), which is the remaining sum.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Sad story here
»
8 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

Can anyone explain the logic in the following code? I am not getting the point why k%1024 is taken? Please help me out. Problem C. Accepted solution link: http://codeforces.me/contest/768/submission/24852093

Accepted code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
int n,k,x;
vector <int> v;
cin>>n>>k>>x;
for(int i=0;i<n;i++)
{
    int a;
    cin>>a;
    v.push_back(a);
}
if(k>1024)
    k=k%1024;
for(int j=0;j<k;j++)
{
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
       if(i%2==0)
         v[i]=v[i]^x;
}
sort(v.begin(),v.end());
cout<<v[v.size()-1]<<' '<<v[0]<<endl;
return 0;

}

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

After an hour of meditation I still cannot understand the following solution: 24828716.
Could someone, please, explain it? =)

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

    First he's reversing the bit-pattern of 'n'.

    In the final generated sequence, the i'th number corresponds to the k'th most significant bit (MSB) of input 'n' (where 'k' is the position of least significant 1 in binary representation of i).

    Ex: n = 5 (101 in binary)

    generated sequence 's'

    s : 1 0 1 1 1 0 1

    i : 1 2 3 4 5 6 7

    k : 1 2 1 3 1 2 1

    i to k, for i = 6: 6 = 110 in binary, the least significant 1's position (k) in 'i' is 2

    similarly for i = 7, k = 1;

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

      I have also observed all of that, but this isn't really an understanding of the algorithm :)

      I'd like to know the conceptual thing. Generalization rather than the details.

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

My collection is complete!

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

In C problem , i supposed that the cycle is small. But how should I prove that the length of this cycle is smaller than 100 ? :) my accepted code :

http://codeforces.me/contest/768/submission/24855247 edited

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

Someone knows why this n*log(n) solution for problem C gets AC? http://codeforces.me/contest/768/submission/24855627 Weak test cases?

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

Unsual time and variable limits on problem c! :|

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

Hey, can someone tell me: There has been several instances where using a memo table and solving a dp problem recursively has gotten me TLE while an iterative solution done extremely similar would get AC. Is there something inherently wrong or restricting with recursive dp or is it something I'm doing wrong?

Here's an example from this contest:

In contest recursive: 24838211

Out of contest iterative: 24854866

There is a noticeable difference in the in contest one as I was using binary search on the day, but I don't think that was what was getting TLE, if it was please tell me. Thank you!

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

    In general recursive dp (with memoization) has same complexity although with a higher constant than iterative dp. That is because of function call overhead .

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

It's a pity I don't see my id in homepage. Hope to add top 5 in div2 to announcement. :)

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

I don't know why my code outputs too many answers in test case 7. Please tell me the reason! http://codeforces.me/contest/768/submission/24859236

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

HELPPP PLEASE — Im getting CRAZY/NUTS/COCONUTS

REGARDING PROBLEM C, I submited three identical solutions but with different results wrong , right1 and right2. The only diference is the vector size (1025, 1024 and 1500 respectively). all should work since the probolem uses only the first 1024 slots.

I suppose it is somekind of undefined behaviour, can someone please help me? this is driving me crazy...

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

    Only the 1024 version should be AC. You have a for loop: for(int i = 0; i<v[ATUAL].size(); i++){. If you have 1025 in your code, the last value of i will be 1024. Two lines later, you access v[OUTRO][i^x], which will be out of bounds if x > 1.

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

Did anyone get their T-Shirts? I haven't received mine yet...

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

    Actually, the International T-Shirts are done. The Indian ones are taking time. We are trying to finish that as soon as possible. We are deeply sorry as it is taking lot more time than expected.