doreshnikov's blog

By doreshnikov, history, 4 weeks 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, I_Remember_Olya_ashmelev and Aris_244_ 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
  • +300
  • Vote: I do not like it

»
4 weeks 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?

  • »
    »
    4 weeks 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!

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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 :(

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

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

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

    @nizamoff your pp is awesome.

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

My first unrated round.

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

    I love seeing your progress chart. Inspiring

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

i hope to be specialist after this round ..

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks 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!

»
4 weeks 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)$$$.

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

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

  • »
    »
    4 weeks 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

»
4 weeks 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.

  • »
    »
    4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Just failed School's selection round for NOI.

  • »
    »
    4 weeks 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!!!!!

»
4 weeks 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 :( .

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I hope I can become blue after this round.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will be fun. I'm all fired up.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice! Looking forward to my first rated round

»
4 weeks 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.

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it
lighthearted meme
»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

My first round :)

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Enjoyed your first div3 round, hopefully will also enjoy the second one. Really excited about the div3 round.

»
4 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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.

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

Deleted

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I withdraw from this?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Going to be a trusted participant after this. Yay!

»
4 weeks 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!

»
4 weeks 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.

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

    Exactly bruh, The B is easily a 1000+ rated problem.

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

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

    Unless you know how to do selection sort.

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

implementationforces

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

i hate this round , all implementation based

»
4 weeks 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).

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

    i agree

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

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

    • »
      »
      »
      4 weeks 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.

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

      Yes you're right @20203246 I solved in 2nd attempt.

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

      I was able to do it mate

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

    there were a blog and a youtube chanel (same person) posted full AC code from A to E2 while the contest were ongoing

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

While Polycarp is on vacation Casimir is taking over.

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Enjoyed this round. Especially E2.

»
4 weeks 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?

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is so hard for me :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E2 ?

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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)

      • »
        »
        »
        »
        4 weeks 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.

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

    You can also solve it using:

    C++ pbds
    
»
4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks 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.com/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).

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

    Thanks, mate. Your solution cleared some of my doubts on heaps and priority queues. :)

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

Good round. BTW, how to solve G?

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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!

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

      Thanks a lot! I solved G!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

3 questions gang?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did I just participate in a div-2 round?

»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

What would be problem rating of E1 ? 800 ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why nlogn solution give TLE on E2?

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

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

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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)$$$.

        • »
          »
          »
          »
          »
          4 weeks 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)$$$

          • »
            »
            »
            »
            »
            »
            4 weeks 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;
            
            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, it gains AC: 130194814

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks 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<>}$$$

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

              How are you Handling Duplicate elements?????

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

                std::map

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

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

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

                  ordered multiset

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

                  Noiceee

      • »
        »
        »
        »
        4 weeks 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)$$$

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

    130192451 — AC with some changes to your code

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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.

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

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

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

    RIP

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

      I could have solved 7 problems today :) Disgusting .

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

    #metoo

    • »
      »
      »
      4 weeks 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 >_<

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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!

  • »
    »
    4 weeks 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.

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

      Yeah the statement was kind of misleading, when they shoes how the shift should work in the examples they started by the results, i got tricked too xd

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

    Same man!!

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

    same issue bro. ≧ ﹏ ≦

»
4 weeks 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

»
4 weeks 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

»
4 weeks 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

»
4 weeks 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
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Implementforces, Bruteforces :DD

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve G? something like dp?

»
4 weeks 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!!

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

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

    First , understand by yourself how a tick of size d is made.

    I hope you got it.

    Then , suppose you have a n X m grid . You have painted some ticks of length >= d on it .

    Now , in the question , you are given a painted grid. You have to tell whether this grid can be generated or not !

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

THE EASIEST E1 EVER! :)

»
4 weeks 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

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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>
      
      • »
        »
        »
        »
        4 weeks 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.

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

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

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

      my code works flawlessly now, thanks a lot bro

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thx for the contest

»
4 weeks 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
  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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?

  • »
    »
    4 weeks 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);
      }
    • »
      »
      »
      4 weeks 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.

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

        Ohh Nice explanation I was searching for that kind of test case . U have made it easy.I got it Thanks to u.

»
4 weeks 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) ?

  • »
    »
    4 weeks 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.

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

      Thanks, do you know why people downvote a comment like this?

»
4 weeks 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 :)

»
4 weeks 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.

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

    What was the key idea for A?

    • »
      »
      »
      4 weeks 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.

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

        Thanks.

        Damn, I got it, but... I read a problem too quickly and inattentively, that's why I lost an important aspect. The morality for me (and other beginners) is that I shouldn't hurry at the contest, there is enough time to solve all problems.

»
4 weeks 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

»
4 weeks 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.

  • »
    »
    4 weeks 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

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

      Look at the solutions that fail by TLE. It should be pretty easy to see why.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain approach for C plase

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

    this is my solution to it , you must try to find the root that genirat left and right diagonal and put them like visited or used, and if it must be big then k or equal the left and right *, the code, sorry for my bad English.

    void solve() {      
        int t;
        cin >>t;
        while(t--) {
            int n, m, k;
            cin >>n >>m >>k;
            vector<string> s(n);
            lp(i, n) cin >>s[i];
            bool vis[n][m];
            clr(vis, 0);
            for(int i = k; i<n; i++) {
                for(int j=k; j<m-k; j++) {
                    if(s[i][j] == '*' && s[i-1][j-1] == '*' && s[i-1][j+1] == '*') {
                        int a;
                        for(a=0; i-a>= 0 && j-a>=0 && j+a<m && s[i-a][j-a] =='*' && s[i-a][j+a] == '*'; a++);
                        if(a >= k ) {
                        for(a=0; i-a>= 0 && j-a>=0 && j+a<m && s[i-a][j-a] =='*' && s[i-a][j+a] == '*'; a++) {
                            vis[i-a][j-a] = 1;
                            vis[i-a][j+a] = 1;
                        }
                        }
     
                    }
                }
            }
     
            bool b= 1;
            lp(i, n){ lp(j, m) if(!vis[i][j] && s[i][j] == '*'){
                b = 0; break;
            }
            if(!b) break;
           }
           cout <<(b ? "YES\n" : "NO\n");
        }
     
     
    }
    
  • »
    »
    4 weeks 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

»
4 weeks 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

»
4 weeks 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.)

»
4 weeks 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.

»
4 weeks 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";
    }
}

}

  • »
    »
    4 weeks 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
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

    • »
      »
      »
      4 weeks 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 ?

      • »
        »
        »
        »
        4 weeks 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).

»
4 weeks 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.

»
4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And they are almost submitted at same time. Someone mentioned that a youtuber released video editorial for problems when contest was running :(

  • »
    »
    4 weeks 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.

»
4 weeks 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 ?

  • »
    »
    4 weeks 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.

»
4 weeks 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?

»
4 weeks 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.

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

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

»
4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Send ur generator

  • »
    »
    4 weeks 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

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

problems were good

»
4 weeks 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).

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

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

    • »
      »
      »
      4 weeks 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 :(

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

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

      • »
        »
        »
        »
        4 weeks 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).

        • »
          »
          »
          »
          »
          4 weeks 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

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

»
4 weeks 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...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will probably get downvoted to hell for saying this but this round had a bunch of issues....

»
4 weeks 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

  • »
    »
    4 weeks 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

»
4 weeks 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...

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

    if u wrote the solution in secret mode, then no problem otherwise everyone could have seen your code and they may have used it. So in that case it is a problem. You have to ensure that your code doesn't gets public during the contests.

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

      I have not been aware of this fact, so in that case, I will be rated or not?

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

    There have been many cases similar like yours, because when you use ideone.com in public mode, everyone can see your code and copy it. There is no way for you to convince me that you did not copy the solution. The best way to solve this problem is in the next contest, you should use ideone.com in private mode.

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

    -_-

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

I am new to codeforce.I used two accounts one in which I try the codes and the other on which I submitted I realised it is showing me that the code coincides which is obvious because both are my accounts .I realised that this can't be done so I won't do it next time but what about this time will I lose out on the ratings?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi mike , I just got a message from codeforces that my code matches with atarax/13017197. But in that question, everyone's logic was expected to be the same and the implementation was also expected to be the same even though there are some differences in the implementation of both the solutions(my solution, atarax/13017197). I don't even know this guy he is from some different university that I don't even know about. And I do have a clean record I have just one such message in the past that's because i was new on codeforces at that time and I didn't know that I can't submit the same solution from 2 different id's (both were my id's); Please help me out if you can.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the cheaters are not rated ?? They should deserve negative delta!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When we will be getting the editorial?

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Solutions to all problems in video format :)
solutions

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest with interesting problems.

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.com/contest/1579/submission/130266275 just by using map your code gets AC

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In this round #744 Div.3 I was falsely accused of cheating/plagiarism even though I used a self written code except of this part while (pq.size() > 1) {

while (pq.size() > 1) { int num = pq.top().first; int idx = pq.top().second + 1; pq.pop(); int num1 = pq.top().first; int idx1 = pq.top().second + 1; pq.pop(); num--; num1--; I copied it from this reference This

but I just changed a few things like instead of outputting the top I just signed it to an integer of num and index and did it twice because I needed the largest 2 numbers and made the while loop from 2 because I needed at least 2 numbers. as if the rest of the code I've always been writing my code the same way even if you try to look at my older submissions you will notice so. I hope this issue is resolved and Thanks.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

Can someone help me understand the offset in problem B? From the problem description: [1,4,1,3] -> [3,1,4,1], offset 1 and [4,1,3,1] -> [3,1,4,1], offset 2. I understand this, l and r for these are 1 and 4.

Then there's this example: [1,3,2,8,5], where choosing l=2, r=4 and d=2 yields [1,8,3,2,5] Shouldn't this be [1,2,8,3,5]? Am I missing something stupid? Any help would be appreciated.

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

    It was [3,1,4,1] then it became [1,4,1,3] after moving all the elements to the left by 1. Also they are in cycle so if it is in the first position and wants to move to the left by 1 then it will become the last. Same thing with this it was like this at first [3,1,4,1] and after offsetting it became like this [4,1,3,1].

    I hope I helped you.