CoderAnshu's blog

Codeforces Round #793 (Div. 2)
By CoderAnshu, 6 weeks ago, In English

Hi Codeforces!

I am pleased to invite you to Codeforces Round #793 (Div. 2), which will take place on 22.05.2022 17:35 (Московское время). You will be given 6 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.

All problems in this round were prepared by me and rivalq. We have worked on this round for a long time and hope you find every problem interesting.

I would like to thank:

Score Distribution:

750 – 1000 – 1500 – 2000 – 2500 – 2750

Good luck and have fun! See you in the standings. Make sure to read the statements very carefully.

Thanks to ak2006, video editorials for some of the problems will be available on his channel after the round.

Congratulations to winners!!

Global Top 5:

  1. jiangly, superfast AK!

  2. Beduardo

  3. SSRS_

  4. neal

  5. turmax

Official Top 5:

  1. Beduardo

  2. Brewess

  3. Kizuna_AI

  4. MY_aespa

  5. csyakuoi

Special mention to AwakeAnay for the only Indian to AK the round!

UPD 1: Links to video editorials of Problem B and Problem C

UPD 2: Editorial for problems A-D is here.

UPD 3: Editorial for E is added.

UPD 4: Editorial for F is added.

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

»
6 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

AmShZ orz, The captain of Iranian testers

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

CoderAnshu supremacy!

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

I downvoted you. Then, your contribution was raised by 1

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

Orz

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

As a true cyan (tester), I would recommend you to try the next problem if you get stuck ( '◡' )

Also, if you wouldn't mind
→ Reply
»
6 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

As a tester, the problems are fairly interesting and quite challenging.

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

As a tester, I can confirm that the problems are high-quality and interesting, and cover a good range of topics, and would recommend participating in this contest.

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

As a tester, I really did test the round this time.

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

I hope it will be great #793 div.2

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

CoderAnshu lord supremacy. :)

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

A contest by Indian Coder after such a long time!!! Very Excited!! Hoping that this contest turns out to be the best in recent times.

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

    How can you forget #782 div2 by my friend Newtech66 just a month ago?

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

      Ohh yes! Now indian are making some interesting contest. And they do all this with hectic college schedule in India.(-_-)

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

    The best duos of India. (CoderAnshu and rivalq) supremacy

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

As a problem setter, I would really like all of you to participate.

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

I hope everyone will participate so it will be fun

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

i hope the round will be a bit better than previous

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

For the last two contests I have been fsting on problem D due to stupid implementation mistakes. Hopefully this contest I will be able to break the streak.(Hopefully by solving problem D )

Edit: Broke the streak by not solving D this time.:clownglasses:

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

As a tester, I get to write a comment for some contribution. hue hue hue.

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

Notice in the last line

Make sure to read the statements very carefully.

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

All the best Everyone !

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

Hopefully the "best of 2022" which were replaced in the previous round will be seen here.

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

I hope I solve about 3 problems and become a specialist !!

Good luck for all participant!

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

All the best for all participants

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

As not a tester,give me contribution!

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

No offense though

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

Everything is so sorted, just look at the testers list! Efforts put everywhere.

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

Much Awaited Contest

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

    of cource! it seems like very very very great contest and also much awaited.

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

Good luck Everyone :)

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

I will be taking part in this contest.. I am getting back after nearly 1 year.. wish me good luck bois!!

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

This contest will be harder than previous.Good luck everybody!!!!!!!!!!!!!!

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

yes i hope i don't forget to read the statements carefully ..... may my mind & focus help me

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

Btw, 793 is a semiprime number. Hope that means at least half of problems will be great!

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

Indian round will be on fire as always. Hope to solve 3 problems at least this time.

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

Good luck!

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

All the best to everyone

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

Best of luck to everyone!!

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

I hope the rating changes will be good for everyone! Good luck!

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

good luck to everyone!

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

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

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

A problem was not easy. And i don't think so it'5 750 rated problem

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

I believe in CoderAnshu & rivalq supremacy!

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

SwapOnPermutationForces.

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

    This justifies your WA on B.

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

      Well just because I didn't initialize the answer big enough :(

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

Yet another unbalanced round... #SpeedForcesOP

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

Now I can finally sit and watch my rank fall due to so many wrong submissions.

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

    Yeah, me too, thought I'm a master after I became a specialist LOL

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

      The difficulty rating for questions you have solved doesn't even signify how you became a Specialist!.. Anyways Congo

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

        Yeah sometimes luck plays a part too, and CF is not the only platform my friend

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

    Same here lol

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

    me too

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

Problems are tricy ig.

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

Would anyone please explain why the output of problem C is 7 for this input?

1

13

1 2 3 5 6 7 7 8 8 9 9 10 10

Thanks.

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

    Put 1 in the middle.

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

    That's 8

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

    10 9 8 7 3 2 1 5 6 7 8 9 10

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

    10 9 8 7 6 3 1 2 5 7 8 9 10

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

    Isn't it 8 ? Below would be the optimal order:

    Arbitrary order

    Edit: This answer is for Rev. 1 of the parent comment.

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

      no 13 is number of elements not in the array

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

        I understood that now. Initially I thought it is part of the array.

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

      No, Here first 1 is the test case number & 13 is the number of elements.

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

    Array: 10 9 8 7 1 5 3 6 2 7 8 9 10

    10 9 8 7 1 5 3 6 2 7 8 9 10

    In reverse: 10 9 8 7 2 6 3 5 1 7 8 9 10

    My Approach if u want to know
    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

FML, I think I have the solution for E. Rip. I think it involves traversing each tree in the forest and doing a tree DP.

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

Guys!! Hope you liked the round. Please share your feedback on every problem. I will be really thankful.

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

    Because i solved till C, it was very great round!)

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

    unbalanced and stupid problems

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

      Not fair. Frankly speaking, it happens not so often, but A was pretty. As for B, i am not a pro of bitwise operations, but even i didn't found this one too hard. And C... some stupid mistakes, but after about 30 min i did found the right solution by painting samples into notepad, so i do not think that this round was disbalanced

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

        Eeeew pupil, ofc it won't be unbalanced for you.

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

          What, how did ya call me????????? I am a specialist now, baby!!!!!!!!!!!!!!!!!!!

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

    I was able to solve till $$$C$$$, and it felt okay, I had almost got $$$D$$$, it was a nice constructive problem, and I don't know why I was getting WA on test 2.

    It would be really helpful if anyone can explain what does this means ? I got this on $$$D$$$

    My submission: https://codeforces.cc/contest/1682/submission/158075759

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

      I guess there is a problem in amount of your edges, the compiler is trying to say you have to print another edge, but your code started to answer on the next test case, so you probably don't have enough edges printed. Sorry if I'm wrong

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

        Yeah, you were right, thanks for your help, I got one test case failing "100100100100", and now it got accepted :)

        It's a very sad thing that I wasn't able to find this basic test case during the contest..

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

    good problems I solved till C (I was lucky), problem D was good but I didn't get any idea how to solve it (waiting for editorial), nice problems keep it up, and thanks for the round.

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

    strong pretests for most of the problems and very clarifying statements .thanks for the round.

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

    Questions are very interesting. From B to D all of them involved a decent amount of thinking. Loved the round.

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

    I got TLE for using unordered_map instead of map in C... Bad contest :(

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

    sorry @CoderAnshu, I was upvoting but my mouse sucks, I accidentally clicked on downvote, I am sorry for it. hope you don't mind it

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

LinearForces :-)

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

C felt kinda tricky.

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

Why does the number of solvers of problem C go so high?

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

I can solve D quickly, but I can't handle A,B,C.It's weird.

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

    how to solve D?

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

    god damn stupid greedy thought always messes up my first three problems. Well it sometimes works, but the moments it doesn't work really affect my mind.

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

amazing samples guys

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

What's the solution to D?

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

    I create egdes as a circle, find a edge to remove, then for each two node (x, y) I need to change the degree, I remove the edge of (y, y + 1) and add the edge (x, y + 1) 158057894

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

      amazing simple solution! I have done a garbage code, by using link list and removing subgraphs of size 3 from boundary. In the end size 3 or 4 graph remains which is handled separately.

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

    If number of $$$1$$$'s is odd or there are no $$$1$$$'s at all the answer is "no", because the sum of degrees should be even (each edge is considered in $$$2$$$ degrees) and we should have at least $$$2$$$ leaves.

    To construct a solution, if the string is all $$$1$$$'s, just choose anyone of them to be the root and connect it to all the other nodes.

    Otherwise, connect each $$$0$$$ to the node before it ($$$0$$$ at node $$$1$$$ is connected to node $$$n$$$). Now we have chains starting with $$$1$$$ and ending with $$$0$$$ (call such endpoints "tails"). To make all the nodes in these chains valid, we have to connect odd number of edges to the tails.

    To do so, if all the $$$1$$$'s are consumed in the chains, just connect the tail of any chain to the tails of all the other chains. Otherwise, choose any unconsumed $$$1$$$ and connect it to all the chain tails and to any other unconsumed $$$1$$$.

    Such construction guarantees that no intersections occur, as we first add some edges between adjacent nodes (can't be intersected) and at the end we choose only one node and connect it to some other nodes.

    Submission

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

can anyone explain that how to solce c :*

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

    I just binary searched the answer. You can in linear time check whether an answer X is possible. Although I have to say it was tricky to implement, two WA submissions and like 30 minutes debugging for edge cases

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

    All numbers that appeared two or more times can appear in LIS of both original and reversed array. Then we distribute all numbers that appeared only once evenly in LIS of original array and reversed array. Note that we can share one number in both LISs, so the answer is x + (y + 1) / 2 where x is the number of numbers that appeared two or more times, and y is number of numbers that appeared once.

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

    I just count how many number appears 2 times or more as m2, 1 time as m1 and the answer is m2 + (m1 + 1) / 2.

    Example: 2 2 3 4 5 6 6 -> 2 3 6 5 6 4 2

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

Spent near one hour on E and then realized I made the wrong observation. I think A-E are all great problems.

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

Those who solved problem C with unordered_map, depending on the compiler version, fall on test 26 or 28. Test 28 is a my hack test :)

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

I think Problem B was slightly confusing in my opinion.I am not able to understand B problem clearly.

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

how to solve E?

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

    Build a graph with $$$(x_i, y_i)$$$ as edges. For each i, find path from $$$i$$$ to $$$a_i$$$. A pair $$$(x, y)$$$ can be swapped if the edge $$$(x, y)$$$ is the end of two paths. Edit: add code 158085317

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

      By "...the end pf two paths" do you mean the path where all of it's subtree nodes are located in their correct position?

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

        Sorry I don't get what you mean but I just realized that it may be beneficial to name an edge with its index rather than its two end points since vertices are moving. Let's say the path from $$$i$$$ to $$$a_i$$$ consists of edge $$$e_{b_1}, e_{b_2}, \dots, e_{b_n}$$$, and path from $$$j$$$ to $$$a_j$$$ consists of edge $$$e_{c_1}, e_{c_2}, \dots, e_{c_m}$$$. If $$$e_{b_n} = e_{c_m}$$$, we can swap that edge. Then remove that edge from the end of two two paths and look for another edge that is the end of some two paths.

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

          I see. But how do you do it in linear time for checking i and j?

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

Great round! Especially enjoyed E and F.

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

Good luck for everyone!

:)

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

i literally did c in 8 minutes by using same approach as in editorial but was not confident enough and waited for it to fail main tests. but it passed :) edit: people made it hard just because it is problem "C". conclusion: don't judge a book by its cover

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

    that's so true, i suppose C can be easier than B for those who have no idea what bitwise is

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

Great problems, although didn’t solve E.

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

Why unordered map gives tle on codeforces?

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

    Hash collision resulting in O(n) per access?

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

    Mp.reserve(1024); Mp.max_load_factor(0.25); adding these under map declaration should avoid hash collision

    → Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

is CF getting harder or people are getting so much better? Feels like an 1800 rate problem a few months ago would be just 1600 now. So many solved C

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

    This is happening everywhere. Just look at AtCoder ABC contests and you will see that newer ones are getting harder.

    It's just a natural progression of things.

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

    Or There are many cheaters.

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

    It's actually case3: The question was easy

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

bullshit pretest for C

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

    Why would you use an unordered map when it is quite easy to exploit the hash collisions for it lol

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

    Congratulations!! You've reached the time which every coder reaches where he switches from hash map to map

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Here is some feedback, loved the round overall! I think BCD in particular are excellent.

A
B
C
D
E
→ Reply
»
6 weeks ago, # |
← Rev. 4   Vote: I like it -7 Vote: I do not like it

Is it just me or do these submissions look so similar? - https://codeforces.com/contest/1682/submission/158041174 - https://codeforces.com/contest/1682/submission/158063005 - https://codeforces.com/contest/1682/submission/158043928 - https://codeforces.com/contest/1682/submission/158045408

I think C was quite tricky, with the number of ACs, either I am dumb or there are a lots of cheaters.

They have very similar code structures, and declare the same variable name, conveniently on the same lines, and they are all submissions from the same place.

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

    Tbh I felt the same. Usually C problem has 2-3k solves during the contest but this time it was more than 4k. Maybe some cheaters got code from somewhere or I wasn't able to think properly.

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

158034396

why TLE?

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

    Because you use unordered_map

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

      Doesn't it satisfy time constraints(nlogn)? I have used it many times. What else should we use then here? (sorting would have also taken nlogn)

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

        unordered_map for int can degenerate to O(n) for lookup/insert (map is guaranteed O(log n)).

        But yes, sorting and then linear pass will work too.

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

    you can read this blog for efficient using of unordered_map

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

    check this

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

Nice round, loved the problems.

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

Why the guy's submission is so werid? https://codeforces.com/contest/1682/submission/158020409

update: also this guy's submission: https://codeforces.com/contest/1682/submission/158055059

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

    his non-contest submissions are actually normal. Obviously use comment to bypass the plagiarism detector. I think in the past several months, they have found a way to trick the CF cheat detectors. That's why there are so many ACs for easy to medium problems now.

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

such a poor round wasted 2 hours

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

A should have been little easier :( I wasted more than 20 mins thinking there should be easier solution for A by having right one in my mind. Lesson learnt: Solve what comes to your mind first for A atleast

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

In 3rd Problem, If the array a = [1,2,2] , Then according to codeforces, correct answer is 2. Can anyone explain how is it possible. My Claim : Answer should be 1 and not 2 since it is asked "strictly increasing".

Thanks in Advance !!!

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

    2 1 2

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

    a = 2 1 2 a' = 2 1 2 (reversed)

    second and third element form LIS edit: Boy but you got it in the Contest? Hopefully it's only due to luck

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

      Hi,I also have similar doubt, we also need to check that the singleton element which we are considering to add in both the sequence should be either minimum or the maximum element otherwise we won't be able to add it in both the sequences.

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

        a = 1 3 2 3 1 (LIS)

        a = 1 3 2 3 1 (LDS)

        2 is neither max nor min

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

          Sorry, my bad I thought subsequence needs to be contigous. Thanks for the help bro.

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

I don´t understand the problem B, why is {0,2,1} = 0?

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

    Because sorted array will be 0,1,2 and to it you need to swap 1 and 2. And of 1 & 2 is 0.

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

      you are absolutely right, I was the one who made a mistake with the operator and I thought it was the minimum hahaha (((

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

    swaping 1 and 2 is sufficient ans = 1&2 = 0

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

Thanks for super fast editorial.

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

Good Round, I loved thinking about problem C, it was simple but tricky. going to remember it always. A great Round from an Indian problem setter.

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

for problem :c

test case :
5
1 1 2 3 3

the given answer is 3,could some one please explain how it can be 3.

i am getting answer as 2

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

is there any method to solve A without dividing the string?

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

I have some doubt in problem C.

For this test case

14

150482826 299981842 846268930 299981842 16711396 299981842 160038184 87399809 36731648 410799926 150482826 16711396 410799926 355178268

answer is 7, but my solution is outputting 6, may I know the problem here?

(My approach is to build a sequence greedily by sorting the array and then taking minimum of them and then placing rest of the numbers on left and right of that minimum found (leftMost after sorting) (Counting them just), so that I get a strictly increasing sequence even if reverse, numbers that come twice are put in either of the sides.)

Then I output the final answer as min(leftSum, rightSum) + 1

I am counting these leftSum and rightSum in the above approach.

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

    You are almost correct, but instead of always taking the minimum as the one being used by both the "leftSum" and the "rightSum", you can choose any of the number to be shared by both sequence. An example of this is "5 3 4 5 3" where both the left sequence and the right sequence used "4" in the LIS. Hope this helps :)

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

Thanks for this wonderful round!

I am finally a CM.

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

in problem B, with the input:

1

8

0 1 2 7 4 5 3 6

it seems like the answer is not correct, if im wrong, pls point out my mistakes.

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

    in problem statement it is clearly mentioned that value of X will always exist so this kind of test case not possible.

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

It's a little bit hard to ac the C for me,but C is a good problem!!!

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

Totally shit contest @coderanshu teri maa ki chute lawde

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

    tumhari maa ke paas lund hai kya bhai , bhagwan tumhari maa ka bhi chut de, I'll pray

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

It's Indian territory. love IIT CoderAnshu

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

In problem D:

for input of: 1 4 1100

my submission: [submission:https://codeforces.com/contest/1682/submission/158117585] gives output of: YES 3 4 1 3 2 4 but the accepted answer is: YES 2 3 3 4 4 1

but I think my printed solution should also get accepted.. can someone please help me with this one. Thanks in Adv!!

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

    (1, 3) and (2, 4) intersect internally in the circle.

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

Please help me

My solution for problem E got RTE in test 8, but I don't know why; please tell me why

Thank you!

My submission: https://codeforces.com/contest/1682/submission/158149795

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's first time, that I got warning from codeforces, that my code of a problem of this round coincides with another solution of a person. I am surprised how could it be. I have checked both codes. Steps are similar. I am afraid will it going to block my account casually. For small problems steps can be similar by chance. What should I do now?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I never imagined, that i will be writing my very first comment on codeforces on this problem. I just some minutes ago, seen the message from system of codeforces. The message is that my code for problem 'A' and problem 'B' is matching with another person's code. I just shocked because I have written that code 100% with my intellect only. Even both problems are having WA multiple times, then it got accepted, because i was trying to decode the solution and even my rating has gone negative after this contest. I don't know that person, to which you are saying my code is matching. I have checked his code also by reference you send in message. I found that some variable name is matching in problem 'A' and very few things are matching in problem 'B'. First of all those both the problems are having very very short lines of code. Approx. 10,000 coders solved that problem, And you are fully confident that, if my variable names got matched or some other things(don't know how you checked) matched, then you with full confidence, just sent me message with declaration that i cheated and my rating changes reverted(even i loosed rating in this contest) And saying that I have to prove, what proves I should present here. I even not visited website ideone.com. I did it in my own offline compiler. What should i Do?

Attention!

Your solution 158032468 for the problem 1682A significantly coincides with solutions jaydevbambhaniya1/158013400, MANISH_SAHU/158032468. Your solution 158046434 for the problem 1682B significantly coincides with solutions MANISH_SAHU/158046434, jaydevbambhaniya1/158068875

→ Reply