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

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

Hello Codeforces!

Asymmetry and I are glad to invite you to Codeforces Round 743 (Div. 1) and Codeforces Round 743 (Div. 2), which will be held on Sep/18/2021 17:35 (Moscow time).

Each division will have 6 problems and 2 hours to solve them. All problems were written and prepared by Asymmetry and me. The round will be rated for both divisions.

We would like to thank:

We've put great efforts into preparing this round and we hope that you will enjoy it.

Good luck!

UPD: We would also like to thank Ari for testing the round and KAN for translating the statements into Russian.

UPD2: Here are the scoring distributions:

Div. 1: $$$500$$$ — $$$1250$$$ — $$$1750$$$ — $$$2500$$$ — $$$2500$$$ — $$$3250$$$

Div. 2: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$2250$$$ — $$$2750$$$ — $$$3500$$$

UPD3: We are sorry that the round became unrated due to the long queue. We hope that you enjoyed the problems anyway.

Winners

Congratulations to the winners!

Div1.

  1. tourist

  2. Benq

  3. VivaciousAubergine

  4. ecnerwala

  5. Molewus

Div2.

  1. ChenRui

  2. rainboy

  3. OguriCap

  4. _October

  5. Dallby

UPD4: Editorial is out!

  • Проголосовать: нравится
  • +878
  • Проголосовать: не нравится

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

Since Monogon had ascended into the coordinator realm, I became the new VIP tester.

btw, as a VIP tester, I tested

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

As a tester, I wish you sunny weather ^^

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

As coordinator I want to thank the VIP authors Asymmetry and Markadiusz

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

Looking forward to participate

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

Challenge:hit 200 downvotes under this comment (bye bye contribution)

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

As a coauthor, I wish everyone best of luck and a positive skill delta after the contest.

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

As a tester, I wish everyone happy rating :)

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

Don't wanna miss the contest but suffering from anxiety and depression for the past few days.Hopefully I will overcome anxiety and depression soon and start playing in contests

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

    Mental health is much more important than competitive programming, so take it easy, hoping for some well wishes from a fellow stranger.

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

      Yeah,I am going to meet my psychologist today for that reason.Being mentally strong is important in cp too.Because you can have all the skills in the world but if your mind is unstable during 2 hour contest I Don't think you can deliver your best.Anyway,I am going to consult my psychologist soon and come back strongly.And thanks for your kind words.Cf has really been like a family to me

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

        I hope you become well in the coming days and I wish the best of luck for you in the contest

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

          Thanks for your support.Unfortunately I am not stable enough to give today's contest but hopefully I will be giving every contest in cf from 23rd September.I wish you all the best in today's contest

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

            Thanks turzo_sawroop , I'm still working on a strategy to reach a better level but I think it will take some effort and time to reach a higher rank

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

              • solve 1/2 1300 rated problems

              • solve 1/2 1400 rated problems

              Do these three things everyday

              • solve 2 1500 rated problems

              Do this in every week

              • Don't miss any contest

              Do all these in the next 2 months and be confident and always believe you can be as good as anyone.

              Hopefully your rating will be between 1200-1300 after that

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

                From my experience, I think you just need learn the basic technique to get rating >1600. Do too much easy problem doesn't make your skill better.

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

kickstart round is also scheduled from 17:00 UTC on the same date, can u guyz plz prepone the round?

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

As someone who wants to hit -69 contribution mark, I request y'all to downwote for high ratings. thank you!

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

As an old, almost retired contestant who grew up in the same school as the authors, I'm thrilled to see what my younger comrades prepared :)

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

Interesting division 2 scoring distribution. I expect (and hope for) a sizeable jump between C and D.

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

Early scoring distributions! :D

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

I am a newbie and started giving contests on this platform from this month itself. Excited for this another upcoming contest!! All the best everyone!

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

    I am a specialist and started giving contests on this platform from last year itself. Excited for this another upcoming contest!! All the best everyone!

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

      I am a pupil and started giving contests on this platform from this year itself. Excited for this another upcoming contest!! All the best everyone!

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

        I am a future expert and started giving contests on this platform 20 yrs ago. I was excited for this then upcoming contest!! All the best everyone!

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

Target to solve A, B & C asap to get a good rank, D seems to be much harder based on rating distribution.

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

Noice looking contest good luck :> HEHEHE HA

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

I hope a good result for everyone !

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

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

Very good stuff worked to prepare this contest I guess, thanks

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

As your father,I want some contribution

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

I just want to say that 743 is a prime number.

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

Wish Me Cyan !!!

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

"An Unexpected error" is showing up whenever i am submitting my solution!!! Anyone else facing the same issue????

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

Queue :(

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

too long queue :(

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

A contest after ages and what we see is a Queue

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

unrated please

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

QueueForces T_T.

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

such a long queue , it has to be unrated .

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

15 minutes since A is in queue.....

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

too long queue:(

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

while true: dequeue()

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

please extend the contest by 15 mins at least due to the long queue.

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

    don't make it unrated because the problems are really good.

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

      just cause you solved , this is unfare to wait for 20 min to get wa verdict

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

        i never said it is fair to not make it unrated but an alternative is to extend it since a contest is much awaited by everyone.

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

          imagine waiting for B and then getting wa after 30 min for some silly stuff , meanwhile some guy solved after 30 min and submitted in first go , I dont think extending contest will justify now

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

This should definitely be unrated!

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

The contest must be unrated . Such a long queue

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

I think there should be a clear guideline in Codeforces when the round should be unrated. Because queue in first few minutes can severely affect the rating in case there is a difficulty gap in the problems.

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

Why so long queue??

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

Too long queue, please, make this round unrated

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

The queue is too long today? i submitted a solution 5 mins back and still it's not judged yet.

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

MikeMirzayanov what type of queue is used for submissions, my submission at 7 min is not yet judged but some user's 12 min sol are judged. Please help!!!!

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

If unrated, my possibility of becoming CM will be ruined for this time.

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

Unrated please!!

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

Why queue is so long?

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

Покормите пожалуйста хомяков!

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

Is it unrated?

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

20 mins just to get wrong answer so sad

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

The contest should be unrated cause of long queue!

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

Годы идут а кодфорс не меняется

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

I am waiting for more than 30 minutes, still my solution is not judged .

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

Disgusting queues

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

Such a bad queue :(

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

Me: submits

Codeforces: Click this

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

Imagine submitting before 30 min and getting WA. :))

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

It'll be unrated, there's no point participating. There's no better way to compensate for never getting results on pretests.

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

queueForces

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

it's unrated no doubt just have fun solving problems

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

Nice round. It's a pity that this round is unrated(

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

Great questions, sad the round will be unrated.

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

Second person to solve C only for round to get unrated xD

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

I thought the problems were really nice, so I'm disappointed that the round went unrated.

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

will it be unrated for div 1 also?

still 0 announcement

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

When I solved A and B under 15 minutes, the round gets unrated. Of course, why not :(

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


Thousands of submissions are in queue and only one of them is running. why?

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

B and C were so beautiful, very sad it's unrated.

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

this is not expected from such big organization please fix this for once I did so good in the contest (a and b) this fast (i'm newbie) :(((

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

Results of other OJ:

Result of Codeforces:

lol

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

Feels sad man , when first contest you give goes unrated :(

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

nowdays Long queue is common problem in cf. please do something MikeMirzayanov :(

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

Imagine waiting for a Codeforces round for 1 week... and this.

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

Unlucky comeback after ~2 years of inactive. F.

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

unraited...

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

How to get rid of queues on CF?

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

It was the first contest I liked in probably the last 12 months and seeing it getting unrated this way, I feel sad for the authors very much. Markadiusz and Asymmetry I liked the problems a lot and hope to see you guys with another contest soon!

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

Problem 1C seems to be the same with Problem C in 2020-2021 ACM-ICPC, Asia Kunming Regional Contest.

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

cucked my comeback

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

The problems are nice! Because it is unrated now, I can sleep early today LOL :)

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

This is still a good problem collection and worth trying out. I will still try to do my best even if it's unrated.

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

1-gon's first round got unrated due to the long queue. Now Asymmetry and Markadiusz set their first round coordinated by 1-gon, and the round got unrated due to the long queue. RIP

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

logic behind b?

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

    Since a[0]!=b[0] we need to make those two elements so that a[0]<b[0]

    That is, we iterate all a[i], and foreach one we find the smallest possible j so that a[i]<b[j] That pair of i,j need i+j operations, we search for the min such pair.

    We can find the smallest j for a given i by binary search on the prefix arrays of a[] and b[]. make preA[i] the smallest value in a[0..i], and preB[j] the biggest value in b[0..j]. Binary search the smallest j where preA[i]<preB[j].

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

      We can avoid binary search since we know the numbers in a[] are 1, 3, ..., 2n-1. Create an array c[] such that c[k] gives the index j for number k i.e. if a[i]=k, we get j by c[k]. To fill c[], we can iterate over array b and store index j for all numbers smaller than the current no in b.

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

        Doesn't this require sorting, which yields linearithmic time complexity either way?

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

          No, the numbers are relatively small compared to the length of the input (<=n), so a simple loop, described above, is enough.

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

            Oh I completely misunderstood that comment. I got it now, thanks!

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

give editorial ASAP.
I have to do a lot of homework.

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

    well I think: 2020 -> 0022 -> 0020 -> 0002 -> 0000

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

    2020 -> 2002 (swap 3rd and 4th element) -> 2001 -> 2000 -> 0002 (swap 1st and 4th element) -> 0001 -> 0000

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

The problems were good. (especially Problem B...able to do in O(N)) PS: All the best for Kickstart buddies. :)

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

Any thoughts of problem E? It seems to be a dp problem, but I didn't figure out the recursion formula.

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

For problem C, we first figure out if it is possible to finish the whole book by SCC (strongly connected component). If size of some (possibly 1) SCC are greater than 1, then it is impossible to complete the book. After that, we use 2 min heap to store pages with indegree 0. First heap stores current traverse. Second heap stores next traverse.

Link for my submission

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

    Using SCC is a bit overkill and definitely a waste of time for this problem.

    The goal (when checking if understanding the book is possible) is to check if there is a cycle. We can do that with a DFS (or multiple, in case of a DAG, which we are dealing with here) which, instead of marking a vertex visited, can set two different kinds of flags.

    The DFS works as follows:

    1. Set flag "in progress" for current vertex
    2. Consider all neighbours, for each 2.1. If its flag is "in progress", then a cycle is detected 2.2. If its flag is "unvisited", then run the DFS on the neighbour.
    3. Set flag "visited" for current vertex

    We can count the result with a DFS too, using dynamic programming on a DAG. Every vertex with no outgoing edges receives value 1, because that chapter will be understood during the first reading of the book. Every other chapter will be understood after all its prerequisite chapters are understood, so the result for the chapter is the maximum of the results for the prerequisite chapters... but slightly modified to account for the order of the chapters in the book.

    I'm not the best at explaining so maybe my code will help.

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

      topological sort :|

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

      I actually used a different approach. I made two heaps : the first one is the "main" heap, the second one is the "pending" heap

      The "main" heap's purpose is to store the progress chapters you can learn right now given that you're already learn all required chapters. Meanwhile, the "pending" heap's purpose is to store the chapters which you have learned all the required chapters but the chapter number is less than the chapter we currently on

      So let's process the chapters one by one starting by those which have no requirements. (E.g. the ones which have 0 in-degree)

      Each time we're processing of the current chapter (let's say we name it U) we do this :

      • check all other chapters V which has U as requirements

      • subtract V's degree by 1

      • if V's degree become 0 then : A. If V > U, then this chapter comes after U, then put it on the "main" heap OR B. If V < U, then this chapter lies before U, since we can't read it backwards, put V to "pending" heap

      on the end of each processing, if our "main" heap becomes empty, put all chapters in "pending" heap to "main" heap and increase the number of read by 1 (because this means we will start re-reading the book)

      To check if it's impossible, just check if after we're done with all the processing, there exists at least a chapter we haven't processed before

      My implementation

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

        This work is O(nlog(n)) though due to the heap! But it's still a fine approach.

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

How to solve div2 D?

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

    First of all, xor of all the elements of the array should be $$$0$$$ (xor of all the elements of the array isn't changed after any operation).

    From here, I am assuming that xor of all the elements of the array is $$$0$$$.

    If n is odd, it's always possible to change all the elements to $$$0$$$.

    Note that if $$$a_{i}=0$$$ and $$$a_{i+1}=a_{i+2}$$$, $$$a_{i}\oplus a_{i+1}\oplus a_{i+2}=0$$$. This is the main idea of my approach.

    Now select indices $$$n-2,n-4,...,1$$$. It's easy to observe that now the first element of the array will be $$$0$$$ and $$$a_{i}=a_{i+1}$$$ for all even $$$i$$$ less than $$$n$$$. First element will always be $$$0$$$ because it is the xor of all the elements of the array Now select $$$1,3,...n-2$$$. After these operations, all the elements of the array will be $$$0$$$ and total number of operations performed is $$$n-1$$$.

    If $$$n$$$ is even, you can split it into two subarrays of odd length. So if you can find an $$$i$$$ such that $$$i$$$ is odd and xor of first $$$i$$$ elements is $$$0$$$, you can change all the elements to $$$0$$$, otherwise you cannot.

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

      Oh holy crap this is brilliant. And here I got stuck with some greedy ifological strategy which... I'm reasonably confident would work but I didn't manage to implement it.

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

        Yeah, such approach can work too but I had to consider many different cases.

        Basically: we iterate from left to right, either A keeping all elements behind 0 or B leaving all elements behind 1 (for simplicity ensuring that the current element is 1 too after previous operations).

        A: if applying the operation to the current $$$i$$$ will result in zero xor, we do it. Else if the $$$i$$$th element is 1, we ensure that $$$i+1$$$ is too; we know that $$$i-1$$$, if it exists, is zero, and we can zero $$$i-1..i+1$$$, and if it doesn't, we switch to B.

        B: if applying the operation to the current $$$i$$$ will result in zero xor AND there's an even number of 1s behind us, we zero $$$i..i+2$$$ and 1s behind us two at a time. Otherwise we ensure that the next element is 1 (working through a few cases it can be shown that if it's 0, the current xor must be 1).

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

    First you must have an even number of 1s in the array, otherwise it's impossible to change all elements to 0s.

    Then group all the 1s in pairs: (1st, 2nd), (3rd, 4th), ... we will solve the problem by changing each pair of 1s to 0s repeatedly:

    1. if there are an even number of 0s between two 1s, we firstly change those 0s to 1s by performing operations on i such that $$$a_i=1, a_{i+1}=0, a_{i+2}=0$$$ repeatedly. Then perform operations on i such that $$$a_i=0, a_{i+1}=1, a_{i+2}=1$$$. Note that assume the indices of the two 1s are $$$l$$$ and $$$r$$$, we must have either $$$a_{l-1}=0$$$ or $$$a_{r+1}=0$$$ in order to solve this case.
    2. if there are an odd number of 0s between two 1s, similar to case 1, we first change all zeros to ones except for the rightmost zero. Now we have $$$1\dots 101$$$, then we perform an operation on 101, then do the similar thing on case 1 but from right to left. Note that there are no extra requirement to this case.

    So the strategy is firstly find one pair that can be solved then solve the remaining pairs from that pair in both direction. If none of the pairs can be solved, it's impossible to change all 1s to 0s. Submission: 129221560

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

How to solve div2 B ?

  • »
    »
    3 года назад, # ^ |
    Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится
    since array a is odd numbers and array b is even numbers.
    so lexicographically smaller/greater is defined at index 0.
    so only comparing values at index 0 is enough
    
    
    let cost[x] = # swaps to move a value v < x in array 'a' to index 0.
    
    ans = 2n
    and iterate over i = 0 to n - 1:
      ans = min(ans, i + cost[b[i]]); // i <- #swaps to move i_th number in array b to index 0
    
    if iterating is over.
    the ans will be the answer
    
    ----------------
    how to create cost array?
    intialize cost array with max value = n
    for (int i = 0; i < n; ++i) {
        cost[a[i]] = i;
    }
    for (int i = 1; i < 2 * n; ++i) {
       cost[i] = min(cost[i], cost[i - 1]);
    }
    
»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

My segment tree solution for Div1 A

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

Can anyone help me to find a counter case? 129205285

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

    Correct answer is 3 yours gives 2.

    I have used a similar approach with the topological sort, except instead of storing the chapters to be read in the next iteration in vec, i just added n to the chapter and pushed it into pq. 129229753

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

      Thanks a lot, but i was so dumb that i forget priority queue stores greater elemnet first. I thought it keeps smaller element first. You just saved a lot of time mine.

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

I have tried a video editorial for problem C :book https://youtu.be/KWkkZEGffZw . Have a look at it..and if have any doubts let me know in comments

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

Can I change the statement that a[i] is (0/1) to [0,100000] on Problem 'Xor of 3'.Is there a solution?

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

editorial is also still ``in queue'' LOL

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

For Question B, Can Someone please tell me why my approach is wrong? https://mirror.codeforces.com/contest/1573/submission/129231370

My approach is that our task is to make a[0] < b[0], this can be done by two ways, either bring the closest number which is greater than a[0] in 'b' to the 0th position, let's say it is at j-index, then the answer will be 'j', or bring the closest element from 0 in a which is less than b[0], and the final answer is the minimum of both!

Any counter test-case which fails this approach would be highly appreciated!

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

    You are only considering making the swaps on either a or b. In some cases it is beneficial to do the swaps on both arrays.

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

Is div1 B supposed to make us feel pain?

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

waiting for editorial ...

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

orz Molewus for the round being unrated.