Блог пользователя Ashishgup

Автор Ashishgup, 3 года назад, По-английски

Hi everyone!

I would like to invite you to another one of our rounds, that I set with my friends Jeel_Vaishnav, FastestFinger, Utkarsh.25dec, the_hyp0cr1t3 and ridbit10

We had two approved contests, but decided to merge it into one with more logical thinking ^_^

The round Codeforces Round 685 (Div. 2) that will take place on Nov/21/2020 17:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would really like to thank my co-setters and:

You will be given 6 problems with one additional subtask and 2 hours 15 minutes to solve them.

Good luck — let the games begin :D

UPD 1: The revised scoring distribution will be: $$$500 - 750 - 1250 - 1750 - (1500 + 1000) - 3000$$$

UPD 2: Editorial — Hope you guys enjoyed the round, we will hopefully be back sometime next year :)

UPD 3: Congratulations to the winners! :D

All Participants:

  1. noimi
  2. I_Love_Convex_Hull
  3. zhouzhendong
  4. dlalswp25
  5. peti1234

Official Participants:

  1. I_Love_Convex_Hull
  2. ptd
  3. afterall
  4. Khas_Profit_LLC
  5. imzzy
  • Проголосовать: нравится
  • +1117
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +220 Проголосовать: не нравится

As a tester, I haven't tested yet.

EDIT: I have just tested, and would like to say Ashishgup orz

»
3 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

Well that was a pleasant surprise, yet another Ashishgup round :)

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Indian Round

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

If I am able to solve problem A easily then it's not a Ashishgup round i was expecting.

»
3 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Looks like Ashishgup didn't get placed LOL so he is setting up contests.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    forget about him if he is placed or not are u placed or not ? he is already a grandmaster and u are saying he is not placed , what are u saying please check to his linkedin profile !! you will say then awoo tourist vovuh and all those who are preparing contests for all of us are not placed !!

    don't make any assumptions yourself !! attend the contest solve the problems !!

    Hoping for a good round with good problem sets Ashishgup as always!! all the very best everyone !!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    These guys have 100 hrs in a day!

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

AshishGup round:- Be ready for Interactive problems :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

there is div3 contest this month or not ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Yes.. After 4 days div3 will be held. See the codeforces calendar. You can add it with your google calendar. It's so helpful.

»
3 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Another Indian Contest...... India OP!!!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -103 Проголосовать: не нравится

    you're right, it's very OverPopulated

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -38 Проголосовать: не нравится

      India Over Powered . . . . More population means more downvotes on your comment

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится -46 Проголосовать: не нравится

        yeah overpowered caste system, religious violence, corrupt low iq leaders, trashy education system, garbage filled streets....

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится -18 Проголосовать: не нравится

          Though these all... We are doing exceptionally well in various fields... And you are commenting on the contest made by an indian...

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится

            who I'm pretty sure relied on external sources for his education, there's nothing Indian about it. If anything, he reached this level despite what India had to offer in terms of education.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
              Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

              please do not show your pessimism over here, even I am an Indian and gone are the days when we needed to solely rely on external(Here I think you mean foreign country) resources because we have our own set of good programmers and resources now thanks to many great efforts mostly in the form of YouTube Channels(Especially Codechef nowadays and individual efforts too by striver_79 demoralizer kazama460 and many others too.). But just think would we all would have grown to the extent that we are individually as a University or from any single Country. No, the sharing of knowledge and the Competition makes us all grow better and faster.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится +112 Проголосовать: не нравится

                I'll probably be downvoted here but just being honest.

                I myself relied a lot on external sources.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +4 Проголосовать: не нравится

                  Right, we all have learnt from external resources. I don't see how, it is a bad thing though. It just shows we are eager to learn and contribute further building on what already is there. Don't forget the good things people have to say about Indian youtubers(speaking of external resources) teaching stuff. Also More Population = More Competition = Better Stuff in the long run.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится +31 Проголосовать: не нравится

                I'm simply trying to refute the comment above that says India is OP when it's clearly not, i don't get what your point is. I don't mean to belittle the efforts of those "Indian" programmers, but let's be real here, their channels talk about a very small subset of what is out there related to CS, do you really think that's equivalent to a quality CS education? Also we're talking about a very small minority here(competitive programmers), most students are just having their time wasted by the system as we speak. For sure there are talented people in India too, all I'm saying is the system is only slowing them down.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  By saying India OP.. He was just cheering up.. And maybe you had a funny/sarcastic intention but think about the subject of your comments initially.. Making fun of population of any country can be seen as rude

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  a statement being rude doesn't necessarily make it false, people should develop a bit of tolerance, it's very easy to live in a fairytale being in denial of the problems that surround you. Pointing out the problem or ridiculing it helps expose it.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится

                  let me ask you one thing what country are you from? because every country has its problem. i m not denying that india doesnt have problems but we are trying to solve those and even if you want to expose our problems do it in a polite manner that doesnt hurt other feelings. our roads might be filled with garbage but your mind and mouth is filled with a lot more and a piece of advice instead of wasting your time here writing stupid comments and creating controversies why dont you participate in a contest and get atleast rated

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                  Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

                  I'm Indian. Every country has it's problems for sure, but some are way worse than others, like this one. I don't think i was being too rude, you guys are too sensitive. Calling my comments stupid is easy, give me valid reasons for why they're stupid. I'm doing good on my original account.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +2 Проголосовать: не нравится

                  Yeah every country has its problems and making fun of your own country's problem on an international platform is in no way gonna solve your country's problems. If you can't contribute to solve those problems then simply stfu

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится

                  i disagree, i personally changed my mind about a lot of things by listening to other people ridicule and criticize my ideas, and I've seen it work for lots of other people too. Ridiculing is helpful as it exposes how truly ridiculous your opinions were, politeness doesn't always work, people don't take you seriously if you're too polite, speaking from experience. Also, I am working on some stuff atm that'll improve the quality of education here hopefully, but i wouldn't tell someone to stfu because they're not contributing, either what they're saying is valid or it isn't, them contributing has nothing to do with the validity of what they're saying, unless it's directly related to contributing.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                  Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

                  Good to know that you are contributing to the Education but I think you should be sensible enough to not respond to those over-patriotic cringe proud comments everywhere. They will naturally get downvoted. Nothing can't be done about them. But ridiculing your own country's problems on an international platform in no way makes sense to me. If you think that you can contribute to solve or reduce the intensity of those problems. Then just do it internally. If you think ridiculing your country's problems on an international platform will expose them, then you are wrong. You will only motivate the racists that are everywhere. If you don't believe me you can read comments on this blog. It's just one example of many such occurrences. I know I am gonna be downvoted on this one. But that's what I wanted to say. Peace Out

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  "If you think ridiculing your country's problems on an international problem will expose them, then you are wrong. You will only motivate the racists that are everywhere."

                  I agree that there is some truth to this, I'll be more tactful next time. Yes I did expect a lot of downvotes from cringy patriots, but I said it anyway for the non-deluded crowd just to make them think about it, but i guess i could've done it in a more civil way. Appreciate the reply.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  Bhai, Hum aapko hi vote denge, aap election me to khade ho jayiye, kaha aap yeh competitive programming ke chakkar me phas gaye

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              he(and a lot of other people) excelled growing in the Indian environment even if they used external sources. And there are good sources in India as well. So, I don't see any point here.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Please tell me what the "Indian environment" provides, and why aren't most people like him if it's the magic of the "Indian Environment".

                I'm not denying the existense of good sources in India, I'm saying most sources are trash.

                "So, I don't see any point here"

                You're speaking as if it's very apparent that there's no problem with our education system. Do you really think that? Do you think most teachers out there are passionate about the subjects they're teaching? Do you think they teach well? Do you think they can take criticism about their teaching without getting offended and taking it out on their students? Seriously?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится

                  Yes, there are problems. More than often, I have cursed the Indian Education System myself. But u were simply being disrespectful. There is a way to put your opinion on a public platform. I am not saying that there is some magic in "Indian Environment". I was just putting forth the point that people excel in our environment as well.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Yes i agree that I could've expressed my points in a better way, I'll give you that.

                  "I was just putting forth the point that people excel in our environment as well"

                  And i agree, there are people like that, but that doesn't necessarily mean that the environment itself is generally good, because if it were, we would see Ashish Guptas everywhere (not implying that everyone should be like Ashish Gupta, I'm just giving an example).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  yes, the number of good coders in India is very less. And none of the top 20,30 coders are Indian. Even in software area we are pretty weak in innovation. That is the reason we are producing CEOs like Sundar Pichai and Satya Nadella but not people like Bill Gates and Mark Zuckerberg and Elon Musk. We have come a long way, but we still have a long way to go.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              Most people in any country don't start out in cp using their country's education system, at least I don't think...

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +17 Проголосовать: не нравится

          SALLE Bhosideke.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I am offended by something I completely agree with.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +45 Проголосовать: не нравится

    ah, whats an Indian round without a mandatory thread like this

»
3 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

This guy Ashishgup has different level fan base.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

As a tester, I would highly recommend this round.

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I think you should delete 'Announcement of Codeforces Round #359 (Div. 1)' ;)

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I just love Ashishgup rounds.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a CP enthusiast, can I be a tester?

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ashishgup Merging two approved Div-2 contests into one indicates we can expect round to be slightly hard and having more challenging problems?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Welcome to another Indian round. I hope everyone good ratings.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    you hope, but it's not possible that everyone will have a good rating.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Interesting math problems expected from these setters :P

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

as a contestant, i want my losing rating back :)

»
3 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

As a tester,

»
3 года назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Omg Indian round! So excited

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Kinda like the 2:15/2:30 hr format for the rounds. Hope it stays ^^

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Hope it's not like the last two rounds =)

(specially the one who had c1 and c2)

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

The great Ashishgup is back

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The tag of the blog Announcement of Codeforces Round #359 (Div. 1). When you open #359 you see an extra announcement in the contest materials section which redirects to this blog. Isn't misleading to use a wrong tag?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think it is a mistake. This announcement has wrongly been routed to that round. My guess is you won't find this announcement in today's round's contest materials.

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Are previous rating changes rolled back? I can't see my rating changes for last two contests

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I'll participate

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Nikhil_Medam where you at?

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Hoping to stay in div1

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

another bitforces will be happend

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

A > B and wrong on test 2 whenever the problem setter is Ashishgup.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

ITS LIT!

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Hope that I'll get the lost ratings in this round :)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

why Monogon gets this much upvotes more than any red?any reasons?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +73 Проголосовать: не нравится

    Because most other reds are smart and decided not to waste time farming contribution.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      do you mean creating second account named diagon?(just a joke as I don't have any proof :rofl:)

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        I confirm it's not him, also there's nothing like "Diagon" it's digon

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Nice contest, thank Ashishgup and your team. Goodluck to everyone !!!

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Ashishgup orz.

This guy has a different level fan-base.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Thank Ashishgup and your team for creating a contest for us ^_^

Thank Codeforces for creating a contest site.

Goodluck to everyone !!!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just asking since E1's score is 1500, will it be easier than D whose score is 1750 ?

»
3 года назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

I hope there is no game theory problem.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I am confident enough that this round is going to be div 1.5

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It's time for Ashishgup to make a jump in the top contributors list.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Wishing high rating to all of you. Good Luck for the contest

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck for everyone

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest Ashishgup

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Got destroyed

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

D has the similar idea with AGC002E.

E1 and E2 is really interesting.

Thanks for the contest :)

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Hint
»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

This is whining because I made several wrong submissions, but I think A is too hard. I think A in any contest should be trivial to every official participant ­— more like a registration button than an actual problem. If we are talking about div 2, it should not contain almost any observations, just implementing what you're reading.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    A is trivial. Look at the number of submissions

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    I got 4 WA on A and almost kill myself when got AC

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    Lol

    Seems like you're new to Ashishgup rounds

  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +33 Проголосовать: не нравится

    it should not contain almost any observations, just implementing what you're reading

    Then people will say they were judged in A on the basis of typing speed and not thinking skill.

    There should be some sort of idea involved , it can be very basic though for A .

    Note : I solved A after more than 3000 people solved but i don't think it was not suitable for being A.

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

    If I may offer my opinion as a tester, today's A is more prone to being WA'd by higher rated participants than lower rated participants, more CM+ testers went along the wrong route of divide then subtract than our specialist / expert or lower testers. Also I am curious what your solution was? The intended solution was min(n — 1, 2 + (n & 1)) (Odd -> Even -> 2 -> 1).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yep, this made me leave this contest also somewhat similar to this problem : https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/ .

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    A had literally 1 observation: if n is even, it can be reduced to 2 in 1 step. Also all the corner cases were already present in the samples.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Many other A's in div2s are like that (not direct implementation). Its better that way maybe as there is also a div 3

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I know that feel

    Spent 25 minutes and two WA on A

    But somehow it was obvious for thousands of other contestants

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I was so frustrated that I couldn't solve A. Ruined the whole contest for me. Solved B and went to sleep.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the great contest! How to solve E2?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    Let's say the answer array named A. Use the value of A[1] (which is at first still unknown) as a pivot, ask the xor value between A[1] to the rest of the number, and keep those values. At this moment, you already asked n - 1 queries.

    Then, look into your xor-s values, if there is at least two same xor result in different index (let's say index i and j), you can ask the and value of index i and j. The and value must be A[i] and A[j] since it is the same. Then conclude A[1] and the rest of the array. You only use in total n queries for this case.

    If there is no same xor values, then the array must be a permutations of 0..n-1. To find the value of A[1], you can use the index which has the xor value 1 and 2 to A[1], let's say the index is id1 and id2. Then, ask and 1 id1 and and 1 id2. From here, you know the correct bits of A[1] except for the least 2 bits. For the most right bit (the least one), you can use the result of and 1 id2 since the difference must only occur in the 2-nd least bit. For the 2-nd most right bit, use the result of and 1 id1 since the difference must only occur in the least bit. Last, construct A[1] and conclude the rest. You only use in total n + 1 queries for this case.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      It is simpler to look for 0 and n-1 xor values in the second case since n is a power of 2. These two numbers should differ in each bit. Then we can ask for ANDs with some third number and find those numbers with bitewise operations.

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    It's clear that either there exists $$$a_i$$$ and $$$a_j$$$ that satisfy $$$a_i=a_j$$$, or $$$a$$$ is a permutation.

    For each $$$i>1$$$, query the XOR of $$$a_1$$$ and $$$a_i$$$ and let it be $$$X_i$$$.

    If there exists $$$X_i=X_j$$$ (this can be checked with $$$O(n)$$$ complexity), it's obvious that $$$a_i=a_j$$$, so we just need to query the OR of $$$a_i$$$ and $$$a_j$$$ to get $$$a_i$$$ and then work out the whole array.

    Otherwise, as $$$a$$$ is a permutation and $$$n\ge4$$$, there certainly exists $$$a_{k_1}$$$ and $$$a_{k_2}$$$, where $$$a_{k_1}\oplus a_1 = 1$$$ and $$$a_{k_2}\oplus a_1 = 2$$$. We query the OR of $$$a_{k_1}$$$ and $$$a_1$$$, which is equal to $$$a_1$$$ except for the last bit. Then we query the And of $$$a_{k_2}$$$ and $$$a_1$$$, which is equal to $$$a_1$$$ at the last bit. And therefore $$$a_1$$$ can be calculated, so as the array.

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    You look at the point with maximum x, such that (x, x) is inside your circle. If any move from (x, x) loses, player 2 wins. After the first move, the state will be (0, k) and player 2 simply plays copy-cat, (k, k). This way we reach (x, x) when it's the first players turn, so he loses. In the other case, player 1 wins. I will let you find the proof and if you can't I will provide one

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      please give proof.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        you can see that $$$ d^2 >= (a * k)^2 + (b*k)^2 $$$, where $$$a$$$ and $$$b$$$ denote total up and right steps taken, now you can notice from the parity of $$$a + b$$$ whose move it is, now parity of all the maximum value of $$$a + b$$$ distance we will be same, so just calculate it, and that will be your winner.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Ok, in the second case, the second player won't want to do the same copy-cat thing for every move, obviously. At some point say we have (a, a). First player moves (a+k, a). Now say this is the turn when the second player doesn't want to do the copy-cat thing and moves (a+2*k, a). Player one moves (a+2*k, a+k). Now, if player 2 wants to avoid (a+2*k, a+2*k) that results in loss, he will move (a+3*k, a+k). This constant 2*k will give player 1 the win.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Update: Solved. The problem is in my loop range. Why my code gets WA? My code

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve A ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if N is even then ans is 2 else ans is 3 base case is for n=1,2,3

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    The question states that division by proper divisors is not allowed. So, it makes sense to keep the number even all the time. If you keep it even, you always can divide by its greatest proper divisor i.e. n/2.

    When n is odd, decrease it by 1. When it is even, divide it by n/2 (the greatest proper divisor). This is the optimal strategy.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve problem E2 ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My guest is to solve with the case of n = 4, then find use the same code for the case n > 4, but I have not figured it out yet :((.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Actually, there is a method to deal with 1451E2 - Bitwise Queries (Hard Version) with no more than n queries and the contrast that n is a power of two is not needed.

    Queries XOR 1 i for $$$2 \leq i \leq n$$$, the return value store in an array a.

    If all elements in a are all disjoint, then the ans[1] must be the only number in [0, n - 1] which not appear in a~.(**not true**)

    Else there must be at least one pair $$$2 \leq i,j \leq n, i \neq j$$$, such that a[i] == a[j], so query i, j, the return value will be ans[i], so ans[1] = ans[i] ^ a[j]

    Then ans[i] = ans[1] ^ a[i] for $$$2 \leq i \leq n$$$.

    Sadly, I had a handwrite mistake in my code and I'm not good at debugging Interaction problem, so I don't pass this problem in this contest.

    UDP: sorry, my method have a bug, thanks to ExplodingFreeze

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Distinct xors will not be sufficient to calculate a distinct array, consider:

      xors:0 1 2 3

      This can be 0 1 2 3 OR 3 2 1 0

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Note that a[i] donate the return value of Queries XOR 1 i. so I don't understand you.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I think in this case you have to use the fact that you will have XOR of all ones somewhere. So you have $$$a$$$ and $$$b$$$ with exactly opposite position of 1's. Then you take a third number $$$c$$$ and query $$$c$$$ AND $$$a$$$, and $$$c$$$ AND $$$b$$$, the OR of the two results gives you $$$c$$$ (and then you know the whole array because you have XORs).

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

WHAT THE HELL WAS PRETEST 2 OF C ..!!! :-(

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to approach problems like D in general? Is there any specific approach? This time I was able to guess the solution for D after thinking for an hour.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In this D I used Hit and Trail LoL.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well you notice that you need exactly some linear number of operations. So inuitively you just find all a1^a2, a1^a3 ... a1^an. We do this because, from here, if in three operations we can get a1, a1^a1^ai = ai for any i. And the way to get a1 is to also find a1&a2, a2&a3 and a3&a1. Now all you have to do is notice that s1 = a1+a2 = a1^a2+2*a1&a2 and so on for any two numbers. Solve these three equations and three variables. you'll get a1 = (s1-s2+s3)/2. And then we are basically done. Total n+2 ops.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Here's my approach. I hope you are familiar with the traditional Nim game of 2 piles in game theory. i.e.

    Suppose there are 2 piles of equal number of stones and in one move a person can remove any non-zero number of stones from a single pile and the first one to run out of moves loses the game.

    The winning strategy for the 2nd guy is making the same moves as that of 1st guy but in the opposite pile to that of 1st guy. The idea behind this strategy is to maintain symmetry at every point in the game.

    Now if you observe carefully, similar kind of symmetry is prevalent here. A move in horizontal and a move in vertical direction is equivalent to moving a distance of d*(sqrt(2)) radially along x = y line. so when our opponent makes a vertical/horizontal move, we counter it with a horizontal/vertical move respectively in order to maintain symmetry.

    By ensuring that this symmetry is maintained throughout the game you can figure out the strategy for optimal moves just as done in nim game.

    Edit: A much clear way to present the other idea would be think of 2 piles (1 for horizontal moves and another for vertical moves). Each pile has n moves. A guy is allowed to pick a single move on his chance. This is again classical nim game. The second guy picks a move from the opposite pile and can easily win. In case one pile has n+1 moves, then first guy wins.

    Hope this helps a little :P

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That was an OP contest. Really good stuff.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

for E1 i found xor, and of a1, a2, then xor, and of a2, a3, then found a1 + a2, a2 + a3, a1 + a3 using some formulas, then i tried to find rest a4, a5 ... using xor a1 ^ ai. got wa4, was i close to right solution?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I use the same method and got passed, don't know about the actual test case tho.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I was trying the same idea but this will lead to n+3 queries.. Couldn't reduce it by just one :(

    E: found the issue, you can get a^c from a^b^b^c

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do D :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    think about symmetry strategy, for example:

    (0, 0) =>

    (0, k) =>

    (k, k) =>

    (k, 2k) =>

    ....

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Each player can push the game to the maximum number of safe moves by increasing the smaller axis.

    So, the answer will be whether that maximum number of safe moves is even or odd.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Anyone who faced issues (TLE) in C with python?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

wrong answer Integer 0 violates the range [1, 4]

what is the meaning of this? I was getting this on the contest in problem E1.

this is my code:

my code
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    First player loses iff for all diagonals of the form $$$i + j = k$$$ have xor-sum equal to 0 (similar to Nim). Proof: if they are not 0, you can make all of them 0 with a single move (and you can't make them 0 if they already are).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose we define two state State 1- All diagonals have XOR equal to 0 State 2- Atleast one diagonal has non-zero XOR There exists a move from state 2 to state 1 and from state 1 a player is forced to move to state 2. So if there exists any diagonal with non-zero xor, then player 1 wins else player 2 wins. Hope you get the idea

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the logic for B?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

For me this was a disaster, if cf-predictor is right that was the biggest negative delta I ever got. No need to tell what I think about the problems ;)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    All the problems are quite tricky!

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

    It was a weird round, full of ad-hoc problems. Yeah, they aren't that great imo, but these are the sort of rounds that make you feel either great or terrible.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    adhoc adhoc adhoc everywhere even people passed D just with some guess. It took me a tough time to prove why that formula is correct but I think CP doesn't reward proofs over guesses same is the case with most of his previous rounds too in almost all of them first 5 problems will be just adhoc or formula. and after that are beyond the scope. Codeforces can be better transformed to adhocforces. I don't see much code in writing formulas. thus This is not code-forces.

  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится

    E1 was logically much simpler than D IMHO btw

»
3 года назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

the difficulty level of questions in my opinion: D<B<A<C

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    The problems where all more or less like: Find the key observation and solve easyly, or die.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I'm getting downvoted by those who found the key observation haha.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        may be you are wrong . i completed a,b,c under 30 mins and couldnt get any idea about D for rest of 2hrs :(.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only one who thinks D is easier than C?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve Z?

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Problem F is very similar to problem 1149E. (https://codeforces.com/contest/1149/problem/E)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B? It was harder than A and C for me lol

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    How to solve C? B is about to find if there is a s[l] in the left [0,l-1] or if there is a s[r] in the right [r+1,n-1].

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Hint
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check my simple solution

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I got really frustrated by not being able to solve A and somehow solved B while cursing myself about A , LOL . BTW could someone say the logic behind A ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      • $$$n=1:0$$$ moves.
      • $$$n=2:1$$$ move: $$$2-1=1$$$.
      • $$$n=3:2$$$ moves: $$$3-1=2,2-1=1$$$.
      • $$$n>3$$$ and $$$n$$$ is even:$$$2$$$ moves: $$$n\div \frac{n}{2}=2,2-1=1$$$.
      • $$$n>3$$$ and $$$n$$$ is odd:$$$3$$$ moves:$$$n-1=n-1, n-1 \div \frac{n-1}{2}=2,2-1=1)$$$.
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Let's consider if the value $$$\geq 4$$$. We know that for all even values, we can easily go to $$$2$$$ then go to $$$1$$$, so we have $$$2$$$ steps overall. For odd values, we can't do better than $$$\text{steps even} + 1 = 2 + 1 = 3$$$. Let's say we can jump to $$$3$$$ in one step (we can't jump into $$$2$$$ since the number is odd), is still takes $$$2$$$ steps into $$$1$$$ and it makes at least $$$3$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    consider string s=111010101000 , consider l=4,r=9 , of course sub-string[l-r] is a sub-sequence of but as per conditions we cannot take the same sub-string , the only way we can find another sub-string is if we can find s[l] before l OR s[r] after r . because constraints are small you can brute-force .

    how to solve C ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Hint
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

amazing round difficulty level of each question was up to mark

»
3 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

D is a bulshit. It's all my words about this contest. Sorryyyyyyy

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    I am not sure about that, but I focused on D and lost focus on E which resulted a huge negative delta :/ Sad thing that I am bad at game theory. I wonder, what is the actual proof for the problem? I don't like in general the problems which are mainly focused on intuition which results in a big gap in the scoreboard(for example, masters and specialists together in the same page).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      These problems might not favour you, but it can be argued that they give higher chances to lower rated people.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I can agree with you. After reading D I immediately go to E1. This intuition problems really rage me.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Actually, it's not just the intuition part.There are 2 ways to arrive at a solution.

        1) Use analysis, unravel each step and go from problem to solution

        2) Guess a solution using observation and try to prove it.

        The former is actually interesting,but the later is quite annoying at times,since it's not easy to see that observation,sometimes there is this blindspot where we miss it.But we have to accept that it is a part of the game.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You are absolutely right. But I have looked for reason why I was bad in this CF. I have already released my emotions.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          I used 3) Guess the solution, notice it works right for the second player if he wins but you're not sure about the first player, submit anyway and get AC

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Yea,at times even for experienced coders, it just doesn't strike.Btw can you elaborate on your soln for D ?

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Assume the optimal strategy is right, up, right, up, ... done.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                lol, how did you arrive at it ? I mean there are so many such constructions, why did you pick this ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +9 Проголосовать: не нравится

                  The second player can win with this strategy in case he wins (using this strategy). Then I just assumed there's nothing the second player can do to fight against the first player when he can't win with this strategy...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  that's a great way of arriving at it

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      see the main proof is that the path traversed until we move out of the quadrant of the circle is always maximum path will be followed as both the players play optimally. if this maximum path is of even length UTkarsh is winner else Ashish.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      The only thing I observed and took for granted is that all points on a diagonal (y-x = a) are either all winning or all losing. Then I just checked whether the point (x,x) which was just inside the circle was winning or losing. I don't believe this amount of pattern recognition makes a question bad.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Lol it seems like many high experts and candidate masters lost rating today according to this comment section

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That is actually very true indeed. It might be some psychological feeling that as a specialist or low expert, solving A,B,C fast is already good and submitting anything even if you got penalties on D is good as you have done already good. So that makes the person confident. Now, as a CM/high expert, that is not the case. We know solving only A,B,C will guarantee a huge rating loss so we know that 1 penalty would differ a lot. I myself tried to proof an optimal strategy for a lot of time but couldn't so I wrote any solution and got WA.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    counter test for you

    array is (1,1,1,1)
    n = 4
    your output is (0,1,1,1)
    
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      There is a shitty bug in the code. I couldn't find it during the contest. The solution is actually correct for both E1 & E2 except that blinder

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

WA on pretest 2 legacy continues ..

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +117 Проголосовать: не нравится

E2: First, let's learn $$$a_1 \oplus a_j$$$ for all $$$j$$$. We know $$$a_1 \oplus a_1 = 0$$$ and we can use $$$N - 1$$$ queries to learn the remaining values. We'll use the remaining two queries to learn $$$a_1$$$.

If $$$a_1 \oplus a_x = a_1 \oplus a_y$$$ for any $$$x \neq y$$$, we know $$$a_x = a_y$$$. We query for $$$a_x = a_y = a_x \land a_y$$$ and compute $$$a_1 = (a_1 \oplus a_x) \oplus (a_x \land a_y)$$$.

Otherwise, all $$$a_1 \oplus a_j$$$ are distinct. It means the hidden array is a permutation of $$$[0, N)$$$. There exists some $$$a_1 \oplus a_j = 1$$$; we query $$$a_1 \land a_j$$$ to learn all the bits of $$$a_1$$$ except its last. Finally, we take any $$$k \neq j$$$ such that $$$a_1 \oplus a_k$$$ is odd and query for $$$a_j \land a_k$$$ to determine the final bit of $$$a_1$$$.

To finish we compute $$$a$$$ using $$$a_j = a_1 \oplus (a_1 \oplus a_j)$$$.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This was my second contest.

Nice problems are given. Loved to participate in it.

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Just wondering, is there any reason the answer for problem B is "YES"/"NO" but the answer for problem C is "Yes"/"No"? It seems B and C was originally belong to different contest :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, everyone. It confused me for a long time. I wonder why this 99184980 got ILE on test 3.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

Can someone tell me why my E is wrong.

First I queried "XOR 1 2" then "XOR 2 3" then "XOR 1 3". This should be enough information to find element 2 and from 2 we can find 1 and 3. now we keep doing "XOR i i+1" from i=3 to i=n-1 to get all numbers.

I feel like I'm completely disregarding something because this algorithm takes only n queries bu then again I tried it in quite a few testcases and it seems to be right. Can someone pls help?

EDIT: I'm sorry guys, I misread the question to think "XOR i j" means xor of ALL elements between i and j.

Please ignore the thread :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I don't think XOR 1 2 XOR 2 3 XOR 1 3 is enough information for find out what is a2

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      I was kinda skeptical too about it, but on trying in random numbers it works.

      code for getting second element

      Again I might be completely overlooking something, so please bare with me lol

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can't get element 2 from that information. One example is when the first three elements are the same. All the xors give 0

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    First, because ($$$a_1$$$ xor $$$a_2$$$) xor ($$$x_2$$$ xor $$$x_3$$$) equals to ($$$a_1$$$ xor $$$a_3$$$), the third query is waste. So through these queries we can find only the relation between $$$a_1, a_2, a_3$$$, not the value itself.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      code

      Please find 3 numbers where it doesnt find the correct sequence for n=3

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Have you tried the case of this?

        3
        1 1 1
        
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It works

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            I wonder... I tried your code in my system, for the case of

            3
            1 1 1
            

            the interaction will be like this, isn't it?

            in: 3
            out: XOR 1 2
            in: 0
            out: XOR 2 3
            in: 0
            out: XOR 1 3
            in: 0
            out: ! 0 0 0 
            out;
            out: TIME: 0.000616 sec
            
            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится -9 Проголосовать: не нравится

              omg I just realized "XOR i j" is the xor of ai and aj and not xor between all elements between i and j.

              I'm really sorry lol

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        $$$[0,0,0,0]$$$ , $$$[1,1,1,1]$$$, $$$[2,2,2,2]$$$ , $$$\ldots$$$ are indistinguishable.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Basic XOR Operation
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    OMG I just realized "XOR i j" is the xor of ai and aj and not the xor of all elements between ai and aj. I'm really sorry lol, idk how i didnt see it for this long.

    Plss ignore the whole thread :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your code generates a right sequence given the values of XOR but it is not essentially the hidden sequence. Try this test case on your system — 4 1 2 3 0

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What is the approach for D ? one of the wierdest problems I have ever seen.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Link Why i got TLE in Problem D. I think in worst case number of iteration will be 166096404 so for 2 sec time limit this should pass easily.

»
3 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

In problem D my intuition was that Ashish and Utkarsh will travel in a way so that Manhattan distance covered is maximum possible . Also $$$x$$$ and $$$y$$$ will be multiple of $$$k$$$. Thus i took all possible values of $$$x$$$ and corresponding maximum possible value for $$$y$$$ and took maximum of $$$x+y$$$ say $$$dd$$$ . If $$$dd/k$$$ is odd then Ashish will win else utkarsh will win. Following is my code :

Could some one help me in proving my solution for D.

UPD : It can be proved on lines similar to the editorial.

short solution for D
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

My solution of D in pictures

If the number of steps the game ends in is odd, A wins.

If the number of steps the game ends in is even, B wins.

The strategy is that either player will force the game to the middle for the desired ending.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How do you simulate the strategy of going to the middle? Can you explain

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    it's not necessary that it should be in middle but main point was their max manhattan distance was same for all the winning points, hence middle is enough for proving.

»
3 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Whoever created E, thank you! Brilliant problem!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

-

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

F is poorly written

»
3 года назад, # |
Rev. 6   Проголосовать: нравится +11 Проголосовать: не нравится

I think in Problem D the second player wins iff $$$\left \lfloor \frac{d^2}{k^2} \right \rfloor$$$ is part of https://oeis.org/A061887, based on small test cases. (Will have to try it later)

Edit:

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    During the contest, I noticed something similar and quickly (bruteforce) generated results up to 100 to confirm. AC submission 99172404.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Problem E1 and E2 are excellent ! Nice problem <3

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks Ashishgup for such an amazing contest!! liked problemset

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The overflow in binary_search caused wrong answer on pretest 8 in Problem D.

https://codeforces.com/contest/1451/submission/99164462

I had to use cpp_int or sqrt.

The sample case for hacking this is

100000 99999
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    OH my goodness this is the same mistake from me see the 99184377.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But I think this is a rectification of this overflow.

    Spoiler
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

99129900 Solution A

This solution give RTE for prime no. greater than 10^6

But it passed in system testing

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

Spot the difference and feel the pain:

1) WA on pretest 12

2) Accepted

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What a brilliant contest. The difference level between the questions was just perfect!!!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

A good contest!!

»
3 года назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Nice Round , really enjoyed it

»
3 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Ashishgup make proud India. Love you sir♥️

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

good round. Actually on D I got wrong answer just because of type of d and k, when I change it into unsigned long long int, it perfectly worked, but in the statement it was written that d <= 10^5 and 1 =< k <= d. Can anyone explain this situation? thanks

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    unsigned long long int sul = d * d; This won't work because d is integer.. d*d will overflow giving wrong value then the wrong value will be stored into sul.

    So you need d itself to also be long long before multiplying.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

The testing of E is so goddamn slow
10+ minutes to run the full set of tests O_O
Really don't understand what is the point of those huge arrays in the input if the whole task is not about performance

»
3 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

can someone please review my code for Circle game my solution : ( first I let Ashish and Utkarsh travel vertically(along y axis till (number of moves)*k<=d ) then I switched them horizontally ( along x axis till (the condition x^2 +y^2 <= d^2 holds true and updated number of moves ++ ) finally if number of moves are even Utkarsh wins else Ashish wins )(I am a newbie started coding this month please help ) here is my code :

 #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  int32_t main()
 {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
       int d,k;
       cin>>d>>k;
       int m=k;
       if(d%k==0)
       {
           if((d/k)%2==0)
           {
               cout<<"Utkarsh"<<endl;
           }
           else
           {
               cout<<"Ashish"<<endl;
           }
       }
       else
       {
           int a = d/k;
           a=a*k;
           int b = d/k;
           while(true)
           {
               if((d*d)>=(a*a)+(k*k))
               {
                   b++;
                   k=k+m;
               }
               else
               {
                   break;
               }
           }
            if((b)%2==0)
           {
               cout<<"Utkarsh"<<endl;
           }
           else
           {
               cout<<"Ashish"<<endl;
           }
       }
    }
    return 0;
  }
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Authors, please upload editorials!!!!

No editorials from last 2 contests :(((

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The blog post is linked to a completely different contest lol. image

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can anyone explain what's wrong with this simple approach for C ?

Spoiler
»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

I like the round overall, but D seemed too adhoc-ish and just like in the previous one was solved by a lot of people without much reasoning. Except that this time I was one of those people.

»
3 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

E was a really great problem. Couldn't solve it in contest time though.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

685 div 2: winner registered the same day. 684 div 2: winner registered the same day, used 3 different languages, and took 6 minutes to solve the long implementation question (c1/2) 682 div 2: winner was a newbie pre-contest

Am I the only person who finds this a little odd, or even suspicious? Are extremely good coders creating new accounts to win the contest? Is anyone able to explain the case with multiple languages and very dubious solve times?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    many contestants are doing this thing and it's a bad thing !! We must get rid of these fake accounts, as they affect others

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Anyone else to whom the rating changes seem suspicious?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Apparently, the CF Predictor was wrong calculating this round's deltas and took rating from 2 contests ago

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

  cf-predictor told me I'd be orange after this contest... now it was a lie... :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    cf-predictor isn't using your latest rating to calculate the delta. Check the rating on which this contest's delta is based here.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      So cf-predictor used a lower rating as input and got a higher rating as output?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        No. cf-predictor used a lower rating (1718 < 1997) as input, showed a higher positive delta (+158 > +81) and got a lower rating (1876 < 2078) as output.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I submitted the same code for problem C which hit TLE again after the contest:

https://codeforces.com/contest/1451/submission/99178885 (rejected in contest)

https://codeforces.com/contest/1451/submission/99199972 (accepted after contest)

Is python just too unreliable with large inputs? I was already following the advice from here. It looks like plenty of submissions got through with nearly identical code.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I had this problem a few times. Usually adding the line

    input = sys.stdin.readline

    to your header code does the trick. If not, there are FastIO configurations with are worth considering for inputs as large as 10^6. Check out my submissions for the header code I use.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Isn't that the same as doing:

      s1 = sys.stdin.readline().strip()

      s2 = sys.stdin.readline().strip()

      Which is what I had there. Normal input() failed pretest 2, so it is a massive improvement, but still doesn't seem to be enough.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I can’t be sure why one failed in contest but passed afterwards: that is indeed odd. But if you add that input = ... as header code, it is then used for everything. In your code, for each of up to 10^5 test cases, you’re still using normal input()

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Couldn't upvote twice. Loved the ProblemSet.

»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Am i the first candy -> grandmaster?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -34 Проголосовать: не нравится

...

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Looking at the Testers... should've uttered 'Versatile', did utter 'Colors!!'

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem at position D should not be like this. It is like finding pattern, if you guess it right that yay!! otherwise you can't do anything.

»
3 года назад, # |
Rev. 8   Проголосовать: нравится +1 Проголосовать: не нравится

These two solutions are no different from each other. I tried submitting one in PyPy (with fastIO) during the contest it recieved TLE for pretest 7 and was accepted without any fastIO in cpp later today.

PyPy solution

CPP solution

FML :) I wonder how conqueror_of_tourist goes on despite such hurdles.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Here is hindi video editorial for A to E2, with solutions and thought process. here

»
3 года назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

I've just read F and... WTF? How is it possible that it actually happened? It's a clear copy of 1149E - Election Promises. It's not stolen from any other website, but from CodeForces and this F doesn't have anything more than mnbvmar's problem. I know that it's not important if it comes to some easy problems or something, but this was the hardest problem on this round. Also, 300iq coordinated both of these rounds, that's really suspicious.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Please help i dont understand why my solion for E2 is marked similar to ptd. I sweat to god I came up to the solution on my own and didnt copy it from someone else, nor leaking it to ideone. Please help. MikeMirzayanov Ashishgup

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can attest to his innocence too. I used a local compiler during the contest and never have had contact with him before (we're in different countries). The system could have made a mistake because there are only that many ways of implementing a relatively trivial idea, one that doesn't use algorithmic ideas as well. Seeing his performance, I can tell that he would have received an okay delta, so I really hope that the writers and Mike would look into this.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    221's solution: 99162733, my solution: 99173403. Even ptd also confirmed that he compiled his code locally and doesnt even know me (thank you). Please check it asap MikeMirzayanov Ashishgup

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Happy for my first time to win in div2! XD

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where difficulties of problems of this contest?

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Best problemset I've seen in months