doreshnikov's blog

By doreshnikov, history, 3 years ago, translation, In English

Hello Codeforces!

Sorry for a bit delayed English announcement, we are glad to invite you all to Codeforces Round 744 (Div. 3), third division round held on Sep/28/2021 17:35 (Moscow time). This round was prepared by me and MikeMirzayanov and we hope that you'll find the problems interesting and enjoy solving them.

I would like to thank MikeMirzayanov for helping me with both writing and preparing the problems for this round. Since it's the second Div. 3 round held I'm involved in but only the first one I'm preparing problems for from zero all the way to the end, without his guidance it would've taken much more of my time.

Also special thanks to nizamoff, andreumat, QAZZY, Vladosiya, CtrlAlt, vladmart, Igorjan94, okwedook, ashmelev and Aris for testing the round and giving their feedback on the problems as well as to Gassa and geranazavr555 for proofreading and correcting the statements. This round is very noticeably better than it could've been without your contribution. And last but not least, thanks to everyone who'll be participating! This round contains 7 to 8 problems and is expected to be of decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 7-8 problems and 2 hours 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck and have fun!

UPD: Editorial is out!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Is there a way to become a tester if there is no communication with codeforces admins?

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

    For such rounds, I myself usually write requests to test those who have a long history of participation (years), have no incidents with code matches, and so on. I will write to you in PM :-) Thanks!

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

      Thanks! I would be grateful if you give me at least one chance.

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

      is there a specific level for the tester Would someone below expert be useful

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

      Hello MikeMirzayanov, my code was only once found plagiarised a few years ago because I was stupid back then and from that point on I haven't cheated at any platform. Can I still dream to become a tester at codeforces in some contest in the future?

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

        I think specialist isn't enough for testing maybe some authors would I have seen newbies test sometimes maybe it's good to see what a beginner could do but generally it's not very useful because the more skilled the tester is the more possibility he can find issues with the problem

        And I did that stupid mistake like 3 times not to gain any raiting I would never gain 1 raiting like that but I participated while I had terrible focus and i didn't want to lose so much rating before Scpc and got caught the last time and that made me feel like shit and I didn't do that again since that time but I guess it's too late to fix that who cheated once isn't trust worthy anymore because it's possible to not get caught if you put some effort on it they wouldn't trust you even if you won't do that again because maybe now you could cheat without them knowing :(

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

    It's also one of my questions.****

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

    @nizamoff your pp is awesome.

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

My first unrated round.

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

    I love seeing your progress chart. Inspiring

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

i hope to be specialist after this round ..

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

It may be a rare 8-problems div 3 round!

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

OH MY GOD! I can't wait for this div 3 contest! I heckin' love div 3 contests!

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

As a contestant, I hope the time complexity of me becoming an expert is $$$O(1)$$$.

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

    10000000000000000 is $$$O(1)$$$...

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

    As long as the space complexity of your corny jokes remains $$$O(1)$$$. :P

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

Will a non-trusted participant be rated? New one here can not be trusted.

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

    Yes it would be rated for non trusted participants with a rating below 1600

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

Just failed School's selection round for NOI.

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

    Just relax and keep going.I really admire that you have the opportunity to participate in information competition in the stage of middle school. The future will be full of light and hope,Just keep going. I believe as long as you persist on learning programming, u can become the person u want. No matter NOIP first level, or NOI gold medal,u still have the opportunity,u still have the hope and energy!!!!!

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

This is one of most awaited contest for me , a week without contest on codeforces is hard :( .

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

I hope I can become blue after this round.

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

honestly, many of us was waiting for this round, thanks

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

Very nice! Looking forward to my first rated round

»
3 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I wish that i become Specialist after this round. Upvote for best wishes. Thanks and Good luck to all.

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

A round after more than a week. Wish ya'll the best of luck.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it
lighthearted meme
»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Always better to participate in contest instead chatting with gf. Hahaha

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Will this round be easier than the last Div.3 contest?

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

    This was my first comment, and I don't know why this is so downvoted why is it downvoted?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it -9 Vote: I do not like it

      If you are less than Expert. Then there are high chances for your comment to get downvoted. This happens with me too.

      Edit: thanks for proving what i said above.

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

I am on a streak lately, I became 5* on Codechef few days back and qualified for hackercup T-shirt too, I hope my streak continues!

Wish Me Luck!

UPD: Didn't do very good but since I avoided negative delta so I think the streak is still on.

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

Loved the gradual increase in difficulty in the last contest conducted by +doreshnikov , hope to see a simillar round today!

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

There is too much of a difficulty gap b/w A and B !! B is not at all a regular Div.3 B problem.

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

    B was an easy one if you have solved pancake sorting on leetcode . Here instead of reversing the array, we have to rotate it and with that less constraint even a brute solution will be accepted

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

      Any problem can be described "easy" in someone's perspective. But it wasn't an ideal Div.3 B problem.1.

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

implementationforces

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

Sorry to bother folks who are participating in today's round, but today's round requires a serious plag check, problem B had a sudden surge in submissions from 3K to 7K in just 5 minutes. Like seriously? I don't think B was an easy one to solve for most folks below the 1300 rating (I got it right after like 5-6 attempts).

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

    i agree

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

    Just because you can't doesn't mean anyone else can't.

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

      Firstly, who said I didn't? Secondly, I am referring to the sudden surge in the submissions for B in such a short time, not about who's able to solve the problem.

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

      I was able to do it mate

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

While Polycarp is on vacation Casimir is taking over.

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

Today's round had nice problems (especially F and G). Thanks to MikeMirzayanov for amazing m2.codeforces.com platform (I had connection problems and the lightweight version was very useful). :D

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

Enjoyed this round. Especially E2.

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

Holly… Amazing div. 3 round! Btw. anyone knows why cf-predictor is down?

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

    Mike must have closed off Codeforces API to reduce server load.

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

How to solve E2 ?

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

    Suppose l_i is the increase in the number of inversions if you add i_th element to the beginning and r_i is the increase in the number of inversions if you add i_th element to the end.

    It's easy to observe that neither of l_i or r_i depend on the order of first i-1 elements. So, just add min(l_i,r_i) to the answer at each step.

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

    For E2, first apply coordinate compression.

    Then, using a segment tree/binary index tree, calculate whether prepending or appending the element is better. It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.

    130179241

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

      It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.

      Is there a proof for this process working greedily? I mean wouldn't the answer change for the (i+1)th element change depending on where the ith element is placed? A bit confused over this intuition. (The position of the ith element may add to the inversion count of the (i+1)th element)

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

        Not really, the ith element can only be either added to the beginning or the end, so the only thing that matters is among the first (i-1)th numbers,how many numbers are smaller than the ith number if you are adding it to the beginning, and how many numbers are greater than the ith number if you are adding it to the end.

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

    You can also solve it using:

    C++ pbds
    
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a way faster than nlogn for E2? I was so happy when i came up with a multiset, but it still TLE

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

    I used coordinate compression + segment tree. Multiset won't work as you can't find distance in constant time. There is something called ordered set, maybe use that. I haven't used it personally.

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

Loved the contest, The Problem D on this contest is similar to a previous Div 3 round D problem.

Link to the similar problem : https://codeforces.net/contest/1506/problem/D

I request everyone , who read the problem D or solved it to go through it also once.

The concept required to solve both the problems are similar.

It is such a nice question on the application of Heaps(Priority Queues).

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

Good round. BTW, how to solve G?

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

    The final answer will always be less than $$$2*max(Ai)$$$ so you can make a 2-d dp of $$$n * 2e3$$$ where $$$dp[i][j]$$$ will give the minimum length of remaining part of segment on the right assuming that you are at $$$j$$$ distance from the start of the segment after processing first $$$i$$$ values.

    Code

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

      If I am not wrong, in your soln you have assumed there exists a soln when we never go to any -ve number. Can you give proof of this?

      P.S. Correct me if I am wrong.

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

        I initialised the first segment at positions greater than 0 as well to handle this case.

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

          So, you took all the points from [1,2e3] as possible starting points. Cool trick. I figured out that max ans will be 2e3 but didn't know how to maintain both the boundaries as well as current location.

          Thank you!

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

      Thanks a lot! I solved G!

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

Did I just participate in a div-2 round?

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

What would be problem rating of E1 ? 800 ?

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

why nlogn solution give TLE on E2?

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

    My segment tree solution passed. So, you must be doing something wrong.

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

      i was using policy based data structure. Its complexity is logn i guess?

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

        You have to read the documentation on policy based data structures, but I won't be surprised if order_of_key or count is $$$\mathcal{O}(n)$$$.

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

          count in a multiset is $$$\mathcal{O}(k + \log N)$$$, where $$$k$$$ is the count returned.

          order_of_key is $$$\mathcal{O}(\log N)$$$.

          Note: find_by_order is also $$$\mathcal{O}(\log N)$$$

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

            I think he has TLE because of mss.count(). He should use std::map. I think his code will be like:

                int n;
                cin >> n;
                int arr[n];
                for (int i = 0; i < n; i++) cin >> arr[i];
                op_set s;
                ll ans = 0;
                map<int, int> mss;
                for (int i = 0; i < n; i++) {
                    if (i == 0) {
                        s.insert(arr[i]);
                        mss[arr[i]]++;
                    }
                    else {
                        int pos = s.order_of_key(arr[i]);
                        ll ans1 = pos;
                        ll ans2 = s.size() - pos - mss[arr[i]];
                        //cout << ans1 << " " << ans2 << endl;
                        ans += min(ans1, ans2);
                        s.insert(arr[i]);
                        mss[arr[i]]++;
                    }
                }
                cout << ans << endl;
            
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, it gains AC: 130194814

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

                Why ans1 = pos . I think it should be more than that numbers less than a[i] will be in multiple frequency but your ordered set constains them only once

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

                  I have ordered multiset, because in using orset I have comp $$$\textbf{less_eqaul<>}$$$

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

              How are you Handling Duplicate elements?????

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

                std::map

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

                  Is your op_set ordered multiset or similar to multiset.??

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

                  ordered multiset

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

        Time complexity of mss.count() is logarithmic in size and $$$\textbf{linear}$$$ in the number of matches. So I think your solution is $$$O(n^2)$$$

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

    130192451 — AC with some changes to your code

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

    It was because of multiset's count function, it can go up to O(N) (N : number of occurrences of the number). Should have used a map to count the occurrences.

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

where to access the editorials of #744 (Div.3)?

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

Great round. But I would have appreciated some drawings in G, as in C.

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

RIP my rating . I was trying right shift in problem B :')

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

    RIP

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

    #metoo

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

      Such a waste of effort . After 1 hour , I have realize that .

      C,D,E1 all took 1 hour just . B took whole the time and feeling terrible for this >_<

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

    It took me 1 hour to solve problem C, but 21 minutes to solve D,E,E1, and E2.

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

      It took me 37 minutes to solve ABDE1 and 1.5 hour to solve C. 20 minutes to solve E2 (after the contest). Amazing!

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

    I also did the right shift first, after I just changed the value of shift offset from d to r-l+1-d.

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

I didn't able to solve any question By the way I try solve the first question but unable

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

As I remember, Problem D was already used in past contests with different statement but same idea

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

It would have been better if F had integers upto $$$10^9$$$ instead of 0's and 1's .

The problem would have been similar to this and we would have to just process Range AND Queries on individual components

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

My reaction seeing that the guy name was Casimir:

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

The problems were literally all over the place.
Even deciding which ones to solve was more difficult than E1.

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

How to solve G? something like dp?

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

Can someone elaborate the problem C please, still I can't understand what it wants!!

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

    It's asking you to check if you can construct a grid solely using 'V' shaped patterns of size K or greater.

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

      4 7 1

      Spoiler

      why here answer 'NO', There is a V shape from position 3 3 of size 1

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

        Because the first '*' in the first row is not a part of any V. The smallest V (K = 1) consists of 3 '*'s.

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

THE EASIEST E1 EVER! :)

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

Can someone help me to figure out the mistake with my logic/code for problem E2?(thanks in advance)

Logic: During each insertion, let the current element be K, we add min(number of elements strictly lower than K, number of elements strictly greater than K) to the answer. I implemented this using PBDS multiset.

my submission

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

    I too have an almost identical solution (and an identical result).
    Considering that I created it with only ~15 minutes remaining, there must an embarrassing mistake somewhere in there.
    My submission

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

      ordered_set contains unique elements only once so this code fails for duplicate elements

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

    ordered_set contains unique elements only once so this code fails for duplicate elements

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

      I changed it to multiset by changing less to less_equal in the following segment:

      From:

      #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
      

      To:

      #define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
      
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh! they it may work, I always use pairs my code is similar to you.

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

    you are not doing mp[v[0]]++;

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

      my code works flawlessly now, thanks a lot bro

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

T~T,It was another very violent topic, and then I saw that I finished it in three minutes, but I felt good on the whole

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

How to solve G?

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

A to F easy solutions with Code and Explanations Happy Coding.

A
B
C
D
E1
E2
F
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    @Fawkes For problem 2 (B) the problem statement mentions: Any sorting method where the number of shifts does not exceed n will be accepted. `` So did this mean that when we take one interval i.e from I to n (like in your soln) we can only shift max n times or did it mean that the total number of shifts shouldn't exceed n?

    because if we take the example: 5 4 3 2 1 then for I = 0, we shift 4 times, and then I = 1 we shift 3 times so the total would exceed n, no?

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

      You may shift by more than 1 in a single operation. In your example, you pick shift by 4 (as a single operation) and get 1 5 4 3 2, which fixes 1 in it's correct place in 1 shift operation.

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

        I see, so it mean that the sum of all the interval shifts i.e << x sum of all such x's can exceed n but the total number of times we perform this shift must not exceed n, correct?

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

    what is the reason to decrease two big values by only one can not it be decreamented by minimum of these .I mean to say min(i1[0],i2[0]). why does not this process give best answer

    while(pq.size()>=2)
      {
        pair<ll,ll>pp1=pq.top();
        pq.pop();
        pair<ll,ll>pp2=pq.top();
        pq.pop();
        v=min(pp1.ff,pp2.ff);
        c+=v;
        if(v>0)
        ans.pb(mpr(pp1.ss,mpr(pp2.ss,v)));
        pp1.ff-=v;
        pp2.ff-=v;
        if(pp1.ff>0)
            pq.push(pp1);
        if(pp2.ff>0)
            pq.push(pp2);
      }
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Imagine three people with times: 6 6 2.

      You would answer 6, since you would pick both persons with a = 6. But the real answer is 7, those two people with a = 6 should talk with each other 5 times, and the last person should talk to both of them separatelly.

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Why am I not able to hack any solution or even been able to lock any problem during Codeforces Round #744 (Div. 3) ?

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

    Div 3 is different from Div2 and combined rounds. Here, you get a hacking phase of 12 hours after the contest ends.

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

Nice round, with great problems.

Although the order of problems could be better, the problems were great!

Thanks :)

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

Most unbalanced div $$$3$$$ round ever :(

The difficulty was like $$$A < E1 < B < D < C$$$ as I felt.

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

    What was the key idea for A?

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

      In problem $$$A$$$, you can either remove $$$(A, B)$$$ or $$$(B, C)$$$, that means you've to remove $$$B$$$ whenever you're removing $$$A$$$ or $$$C$$$, so the $$$\text{count}(B)$$$ should be equal to $$$\text{count}(A) + \text{count}(C)$$$ to make string empty at the end.

      You just have to check that.

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

In problem F, I have used the fact that once some a[index] becomes 0, it will always remain 0 and will turn a[(index+d)%n] to 0 as well..

So, at each step if there's no new index where 0 is formed.. ans will be -1, else we can store these new indices to use them in the next step till all indices are converted 0.

So, if at each step "X" new indices are formed.. the process will go on for N/X iterations .. making it X*(N/X)

I am not pretty sure about this complexity and method.. Can someone provide a counter case/hack it, or affirm it ?

Submission

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

Who made these test cases? E1 hacks are going insane with very straightforward hack.

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

    Can you give an example? I don't know what makes so much solutions to fail :0

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

Can someone explain approach for C plase

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

    Try to find potentional center cells,say {x,y} and calculate the minimum of its left and right arms, say d. If d>=k, add a tick in another grid of size d at {x,y}. After you have done this for all potential center cells, check whether the original grid and the grid you made are same or not. My solution:130153692

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

B submission WA I was trying to solve be for more than 1 hour but it was still giving the wrong answer. The codeforces engine was giving a different answer and my machine was giving different. Mine was correct. I later submitted the problem with very minor change and it got accepted. It was some undefined behaviour I guess, if anybody could explain why that happened, I would be really grateful. Accepted Solution

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

please take a look into hack #758216, the result is "unexpected verdict".
(I mistakenly submit invalid input, then I got such result. Maybe the validator of G is wrong.)

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

I have tried a video solution for the problem F: https://www.youtube.com/watch?v=8qC3qyQsE8s Hope it will help you if you need it.

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

Hi any one could help me to solve problem D, give me the idea or full code, this is my code i got WA, cause their is no tutorial, thanks in advance, and sorry for my English. void solve() {
int t; cin >>t; while(t--) { int n; cin >>n; vii v(n); lp(i, n) { cin >>v[i].f; v[i].s = i+1; } sort(v.rbegin(), v.rend()); vii ans; int i=0, j=1; while(v[i].f&&v[j].f) { ans.pb({v[i].s, v[j].s}); v[i].f--; v[j].f--; for(int a=j;a+1<n && v[a].f < v[a+1].f; a++) swap(v[a], v[a+1]); for(int a=i;a+1<n && v[a].f < v[a+1].f; a++) swap(v[a], v[a+1]);

}
    cout <<sz(ans)<<"\n";
    rep(i, ans) {
        cout <<ans[i].f<<" "<<ans[i].s<<"\n";
    }
}

}

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

    When posting your code, try to include them in spoiler and block tags, so that they maintain their indentation. As for D, the basic idea is to use a max heap, (priority_queue in C++). The idea is to take two indices with the maximum sociability every time and have them meet each other. Their sociability decreases by one everytime, so, you decrease that and if their sociability is still greater than 0, push them back into the max-heap.

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

      can you please explain as to why letting two with the max sociability meet each other would result in maximum no. of meetings ?

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

        We would want to make sure that the number of meetings is the maximum. Taking the indices which currently have the maximum sociability does this, because everytime, we are decreasing the sociability, so the indices that have maximum sociability changes after a point of time, which means meetings are scheduled as long as they are possible. Let us take a counter-example: say, A={1, 2, 3}. Now, if we considered the indices with the minimum sociabilty, we will be able to schedule only two meetings-> (0-1) and (1-2). On the other hand, if we considered indices with the maximum sociability everytime, we will be able to schedule 3 meetings-> (2-1), (2- 1) and (2-0).

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

I would like to report a system bug in problem G.

When I submit my solution, it gets time limit exceeded at test set 22. But when I looked at test set 22, it have three test cases, and first one array length is 10000. But problems says the total number of G does not exceed 10000, so it is not a valid test set.

I look at others solutions passed during contest, and the total number is 18. So test set 22 is not generated by authors, but by hackers after the contest.

Then I tried to generate an invalid test set (3 test cases with total number of n 30000) and hacked others code (I only hacked people who are not officially participate the contest), they all succeed.

Therefore, please remove these test sets that sum of the n > 10000, and rejudge these hacked solutions for problem G. It is unfair for participated who solved problem G but exe time is larger than 333ms.

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

It's rare to see something like this : same same same same same same same same same same same same same same same ....... code.

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

    you are right lots of cheaters got high ranking but it is worthless if you dont know the logic and directly submit it.

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

Thnx for great round, even though I wasn't so luky. Anyway I may have misunderstood problem B, I used Bubble sort considering swaps as d = 1 circular shifts, on paper it all make sence but yet it get me wrong answer on test 2. this is my submission 130155379 , could any good one of you help me with it ?

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

    Swapping adjacent elements is not an efficient way of sorting the array.

    To go straight to the point, the maximum number of operations/shifts your program could need is $$$\frac{n(n-1)}{2}$$$ when the the array is in the form $$$a_1>a_2>\dots>a_n$$$.

    By the way the number of such swaps needed to sort the array is the same as the number of inversions in the array if you want to look into that.

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

I'm new here, so the round should be rated for me but, the contest is showing itself in the unrated section in my profile contests, also I'm not in the standings. I did solve 4 questions during the contest. Can anyone tell me what's this issue?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
C was more difficult than D according to me. I ended up using most of the time to solve C. It just got stuck in my head. E1 was a joke. 

Lesson: READ. READ ALL PROBLEMS.

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

    Better Lesson: See the submissions in dashboard to find next easiest problem.

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

What is invalid test in Hacking? I have also used endl but dtill getting this error?

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

    Send ur generator

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

    there's strict check for tests. I guess you added extra space in the end of line

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

Could anyone please help me understand why I got TLE in E2? I used Fenwick tree + coordinate compression, so this should be O(nlogn) but somehow it fails in testcase #18.

My attempt from the contest (or slightly modified version that's easier to read).

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

    Same here but with seg tree, I really don't understand

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

      Omg found it, man. It's because of the unordered_map. Here is the solution with unordered_map and Here is the solution with map. The first one fail with 2 seconds while the second passes with 343 ms. Like BROO. Why is this happening? I thought unordered_map is faster than map :(

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

        Damn, you're right... Wow, this feels terrible.

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

        It is always sensible to use map over unordered map. You may think that unordered map can give you O(1), but cases can be generated to exploit it's hashing method which will result in Collison everytime you want to use it which will be O(n). Long story short, use map which guarantees O(lgn).

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

          Of course I would do that but I didn't know about it. I just thought the unordered_map is just a map where the keys are not in order. :) Fml

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

          but if tests are not generated to kill hashing method, unordered_map runs faster than map.

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

            Totally. I think the idea is that in most cases an additional log(n) doesn't matter enough (and doesn't give TLE) so using std::map over std::unordered_map would be strongly preferred for me in the future since it makes me not worried about anti-hashes.

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

I think E1 is more suitable for the difficulty of B than the actual B...

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

Hi !

is there any one who can help me with this ?

in problem B , the first test ,my output to testcase 3 is : 2 : 1 3 2 — 3 4 1 but is gives me a WA : wrong answer Element a[0] = 4 is greater than element a[1] = 1 (test case 3)

but its not logical ! if you shift the elements in the way that I said , the array will be sorted !

can you find my mistake ? my submission : 130240370

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

    I guess what you are referring is the Jury's answer. for every [l,r] that you're considering you do cout<<l<<" "<<r<<" "<<1; instead do cout<<l<<" "<<r<<" "<<(r-l); The question says left shift so all the number are shifted towards the left and the first number goes to the last. According to your intepretation the opposite happens. 130115425 have a look at this for reference

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

I have solved four questions in this contest and having rank between 2500-3000, but now they are saying that I have copied the solution of the problem, but I haven't. I am coding in ideone.com, is there any problem with it. I thought after this I will have a 1300+ rating. please help, how will I convince that I do not copy any solution...

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

In D, the most common solution that I have come across involves heaps and priority queues. However, in my initial approach I used DP by modelling the problem as the 0-1 Knapsack Problem. I 1st calculated the sum of the sociability of all the people in a test case, and since each talk would require the sociability of both the participants to decrease by 1, the maximum possible talks in a meeting is (sum of sociability)/2 Therefore, the size of the knapsack can be set equal to (sum of sociability)/2 and the weights set and the values set will be the same, i.e., the input array of sociability of each person. Therefore, by finding the maximum weight that can fit inside the knapsack, we can maximise the number of talks in the meeting. However, my solution fails on the 69th test case of the 2nd test set. Here is my submission. I would appreciate any help in pointing out the flaws in my logic or implementation.

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

Solutions to all problems in video format :)
solutions

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

Nice contest with interesting problems.

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

Hello, I solved 1 problem in Div 3's contest yesterday. But my rating went down. What is the reason?

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

    Your rating depends on your previous rating and your rank, not on how many problems you solved. Read this for further understanding.

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

Failed system testing for Problem E2, could someone tell me why this is TLE? The second last test case also had 200000 length but it passed well within the time limit. My code

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

    It is the unordered_map in the worst case time it's time complexity for insertion can be O(n) and not O(1). https://codeforces.net/contest/1579/submission/130266275 just by using map your code gets AC

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

      thanks, that's tragic. makes me wonder when the unordered_map shouldn't be used since i even passed the pretests so didn't give it a second thought

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

        Sometimes you might want to use pbds hash maps, like cc_hash_table and gp_hash_table. There are helpful tutorials on CF — the authors even mention how to prevent excessive hash collisions, which might be helpful for the casual unordered_map as well.

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

          I followed this blog and was able to pass the test cases. should I just keep it in my template? haven't seen anyone using this though

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

            I've seen ppl using this; personally I've used it a few times. But in this very case, it wasn't needed — note that ordered_set is very slow, but it is enough to complete this task. The operations we need to support are "add x to the set" and "count how many elements that are < / <= are on the set". If we somehow distinguish equal values appearing on distinct positions, we can complete this task simply with order_of_key queries. My suggestion is, instead of adding x to the ordered_set, add f(x) = (x * BASE) + pos, where BASE is some constant (sufficing BASE > n) and pos is the position of the added value. Now, for all values y < x, f(y) < x * BASE, and for all values w > x, f(w) > x * (BASE + 1) — 1. As you can see, the queries are pretty straightforward now, and we don't suffer from unordered_map etc.

            To conclude, sometimes changing the values might be easier and more efficient than the hash function.

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

Can someone please tell me the approach for F and G.

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

    F: If a position has a value of 0, it will never change. If a[i] = 1 and a[i + k] = 0 (where k is the length of rotation), then we can make a[i] = 0 in one turn. (maybe you need to switch a[i] and a[i + k], I don't remember if the rotations are left or right oriented)

    Let's build a circular graph of n vertices. If a[i] = 0, then dist[i] = 0, else set the initial distance of vertex i to inf. Then use a multisource BFS from all vertices with dist = 0 to compute the answer — the edges start at vertex i and go to vertex number i — k (mod n). Whenever a vertex labeled with 1 is accessible from a vertex 0, we add him to the queue, update the "distance" etc. The answer is the maximum distance over all vertices (or -1, if for any vertex v, dist[v] = inf holds after the computation finishes).

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

when will the editorials be released? (sorry for being a little impatient)

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I there any other approach to solve this problem other than using priority queue ?