When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

mesanu's blog

By mesanu, history, 14 months ago, In English

Hello Codeforces!

flamestorm, SlavicG, MikeMirzayanov and I want to invite you to Codeforces Round 849 (Div. 4).

It starts on Feb/03/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

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

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: _Vanilla_, badlad, Gheal, Phantom_Performer, Beacon, Nihad_Nabelsi, prvocislo, keta_tsimakuridze, Bakry, RedstoneGamer22, tibinyte, KrowSavcik, haochenkang, myvaluska, sandry24, BucketPotato, Vladosiya, pashka.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD: Editorial is posted.

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

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

Hell yeah!!

»
14 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Eat an ice cream for positive delta :D

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

    Done Sir.

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

    i did it and finally get a positive delta lol

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

    Ate this too much!!, Hope to reach specialist in this round.. After performing like specialist in some rounds, there comes one round such that sometimes I am not able to perform as expected. It's all about consistency.. Will try my best in tomorrow's div 4 round. Wish me luck :)

»
14 months ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, I suggest you participate!

»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it

As a tester, I enjoyed this round and I recommend everyone to participate!

»
14 months ago, # |
  Vote: I like it +27 Vote: I do not like it

As a newbie tester I recommend fellow newbies to participate :)

»
14 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I want this round to be unrated!!!

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just don't participated live and give it virtually after contest. Ez Win.

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

first unrated

»
14 months ago, # |
  Vote: I like it +36 Vote: I do not like it

As a tester, this is the best div4 I've tested so far.

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

[ Deleted ]

»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it

As a tester, I enjoyed this round so much I forgot I was testing

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

Another round for fast code writing.

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

First, please update the rating of the two past tests!

»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Eagerly waited for unrated contest.

»
14 months ago, # |
  Vote: I like it +45 Vote: I do not like it

As a tester, i loved this contest too much but not more than

Pringles

.

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I am very excited for this contest, may be it will be a good contest for all the newbies like me, to become pupil or specialist

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

Finally my time to shine.

I let my rating sink to be rated for div4. Lets go!!

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

Will I be rated for this contest?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes it will be rated for you. however, you will not be included in official standings because you have participated in < 5 rated rounds. this round is rated for all people with rating < 1400

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

At the end of the contest , some people will be happy and some will be sad, Be of the first kind

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

Can you please change the staring time of the contest? It starts after the Izho and info(1)cup contest. It would be great if you changed the time a bit later or to another day.

»
14 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

.

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

    The world doesn't work that way brother.

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

![ ](cf-meme)

»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's Goo

»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

omg mesanu and flamestorm setters

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

Good weekend, good div.4!!!

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

It's been six days since typeDB round has finished still no problem rating update and no user rating update. Something weird there's been about the codeforces recently.

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

deleted

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

Good Luck contest For Every One

This contest must be successful for EveryBody

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

OMG SlavicG Round!

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

Finally, my first div-4 contest after becoming specialist

»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Will I be rated in this round cause the rating of last div2 round hasn't been updated yet and I am still a pupil,but if last round's rating update I will become specialist.

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

ratings roll back again of Last Div 3

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

I'm wondering how the rating will change for those who turned to be a specialist in the last div2 round, if it is rated.

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

Does the Penalty start from the begin of the contest or my first visit to contest/codeforces?? like if the contest start on 2:00 and I enterd the contest 2:30 and solved a problem at 2:35. Then the Penalty equal 35 or 5?

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

congratulation SlavicG for becoming CM from expert

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

Woooahahshasfhazfz

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

Can't wait to see hmzqaq's performance in this round. (He's duck_pear)

»
13 months ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

..

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

    You waste your mother's time for nine months.

    Marinush

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Stringforces!

»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Div4 round, like always!

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

G2 is quite hard for div4..?

»
13 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Who's the cool Pikachu in problem B?

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

Nice problem set, solved all😊

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

how to solve F?? by not getting tle

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems like lazy propogation on segment tree. Calculating the value is O(1) as sum of digits would convert to a single digit in 2-3 operations.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You have to realize that for any a[i] you really only do the operation a couple times, and then it becomes a 1 digit number, which won't change. So just keep track of the indexes that are 1 digit numbers and don't bother visiting those.

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

      There's no need for lazy propagation. Range updates and single queries can be done with a normal segtree storing differences of consecutive elements. 19192561

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

    You can either solve it using Fenwick tree like I did, or there's an alternative approach as well which doesn't use trees at all.

    The sum of digits operation will only be applied at most 3 times on $$$a[i]$$$. So, make an 3 arrays, the $$$1st$$$ one will be storing the numbers obtained by using the sum operation on all $$$a[i]$$$ once, the $$$2nd$$$ one is when the sum operation is used twice, and similarly for $$$3rd$$$.

    Now, all you need to do is to check for all $$$i$$$ in $$$[l,r]$$$ how many times it occurs.

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

      hmmmmmmmmmm,nice approach

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then it becomes a scanline problem? Or maybe coordinates compression with pref-sum? Or there are easier solutions?

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why 3 times?

      After 2 operations only a number becomes single digit number right?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Take $$$999,999,988$$$ it will become $$$1$$$ digit number after $$$3$$$ operations

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

    I solved it with dsu

    I observed that a number will not be updated many times so that I let a number to be updated no more than ten times.

    When the number of updates for a particular index reached >10 I will make the parent[i]= findparents(i+1)

    Using the above approach whenever an index would be encountered for greater 10 times it will be skipped to the next index and then with the help of dsu I will reach the required index

    My submission — https://codeforces.com/contest/1791/submission/191990981

    time complexity will O(n*10+q)

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Idk how u guys think of this solution during contest,but hats off to u guys..... I will upslove it tomorrow. Ok bye, Netflix............

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used DSU as well but solved it slightly differently. If any number is < 10 it will never need an update again and we can add it to the same set as the element at i-1.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No

        I mean the number of operations applied on a number cannot be greater than 3 (which I randomly took 10)

»
13 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Awesome contest.

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

Solved E and G1 in last 19 minutes of the contest!

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

Good problems this time, I had fun with F, first time using Fenwick tree by myself.

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

❤️ First time I solved A,B,C,D ✅ (in 32 min)

»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Screencast with solutions for all problems in case someone is interested.

»
13 months ago, # |
Rev. 7   Vote: I like it +5 Vote: I do not like it

A & B: implementaion.

C: 2 pointers.

D: Count the occurence of each different chars for every prefixes and suffixes. The answer is max(count(prefix(i))+count(suffix(i+1))).

E: Dynamic programming. Let dp[i][flag]=the maximum value we can get from first i elements, where flag is true if we've fliped the sign of a[i-1],a[i]. Similar with 1787C - Remove the Bracket.

F: A number can be updated of most 3 times (then it will have only 1 digit, which means, it will not be changed anymore) so we don't need to update a same element for more than 3 times. We can use segment tree to store the number of updates (although there can be simpler solutions, it's easier for me to copy a prepared segtree template).

  • For all 1<=a<=10^9, the maximum digit sum of it is 81 (when a=999,999,999), and for 0<=a<=81, the maximum digit sum is 16 (when a=79), and for 0<=a<=16, the maximum digit sum is 9 (when a=9).

G1: The cost of each portal is a[i]+i, sort them and we can get the answer.

G2: The cost of each portal is a[i]+min(i,n+1-i), but we need to add an extra cost if all the portals we've used are on the "right part" of the number line (which means they are closer to n+1 than 0). Therefore, we need to consider for 2 situations: First, consider we use at least one "left portal". We can use the left portal with minimum cost and sort the remain portals. Second, consider we only use "right portals". We also solve this situation by sorting, but we need to add min(2*i-n-1) to our total cost. First we use portals by the order of their cost, and when we can't use the next portal, we check all remained portals and try to use them.

By the way: MikeMirzayanov look at this please!

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E was one liner after some simple observation.

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

    Elegant solution for problem E:
    - If number of negative numbers is even then maximum possible sum will be sum of absolute value of all array elements. - If number of negative numbers is odd then maximum possible sum will be sum of absolute value of all array elements except absolute minimum one minus absolute minium one.

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

can someone hack on problem F submission? I think it should TLE.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Done

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is mine hackable for F? submission

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think no if your segtree is ok

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Solved F without segtree, is my submission hackable :) ?

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Done

            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That means it must be solved with segtree? there is no other way?

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

                You can solve it without segtree. You can see solution in editorial or you can see tops' solutions. For example Jiangly solved it with DSU

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  can you tell what is going wrong in my code in the same problem.(I am failing test case 3rd i have used fenwick tree tough).

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

                  UB if mp[v[idx - 1]].size() is zero and operations is positive:

                  else if (operations > (int)mp[v[idx - 1]].size()) { 
                      cout << mp[v[idx - 1]][mp[v[idx - 1]].size() - 1] << endl;
                  
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I updated but still it is giving me same error.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  v[idx - 1]

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  still failed.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it
                  1
                  6 12
                  999999997 999999997 999999997 999999997 999999997 999999997
                  1 1 1
                  2 1
                  1 1 1
                  2 1
                  1 1 1
                  2 1
                  1 1 1
                  2 1
                  1 1 1
                  2 1
                  1 1 1
                  2 1
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  can I ask one question How are you so fast at debugging?(I also wanan be that fast that will help me a lot).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  No, I'm toooooooo slow. I should notice this bug after second-third code reread, but I was reading it during 11 minutes...
                  Now I was just reading your code and comparing it with some others: your BIT seams OK, then bug must be in other parts of code
                  I've checked update: OK
                  I've checked query: found UB
                  What's left? Only filling of mp, you just fill without check that this element is already in map
                  Just small advice: use local variables like:

                  this
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Fun problemset. Managed to solve everything in 1:08, which I am quite proud of. E was very elegant, F and G2 were also nice.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F was some standard stuff after you know it will take atmost 3 op to reduce the no to the final form.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, it is. But I still think it was nice.

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

i was expecting atleast one graph question xD

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

Great contest. Thanks guys :-)

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

Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.

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

My live screencast with explanations for all problems. I have tried to re-explain last problem in the end after I solved it. The problems were very interesting. I felt the last problem was a bit on the harder side for a Div 4 round.

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

What's wrong with this solution of E 192043725? Thanks.

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

    The return value of your sol functuon is int instead of long long.

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

    Sir it was int overflow

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

F was straight-forward lazy propgation question once you figured out it will take atmost 3 operations. I just copy pasted some template.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I could not find the template for range update and point query. I could only manage to find for point update and range query smh.

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

can anyone hack my G2?I feel it not correct,even i pass the pretest https://codeforces.com/contest/1791/submission/192031288

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

What is wrong with my solution for F? https://codeforces.com/contest/1791/submission/192046957

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are only calculating up to two operations for every number, while there are numbers like $$$999\ 999\ 988$$$ which become 1-digit numbers only on the third operation.

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

Can anyone tell me why my dsu based code is giving runtime error ! It's well under the time complexity and limit. https://codeforces.com/contest/1791/submission/191951510

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

What's Segment tree doing in a div 4 round ?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the editorial. The intended solution doesn't use segment trees.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Segment Tree is one of the ways of doing it.

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

Is there any penalty for unsuccessful hacking attempt/reward for Successful hacking attempt?

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

Very nice problems. Thanks for the contest. I managed to solve A,B,C,D,E,G1 within 50 minutes but could have had F as well if I knew segment tree.

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

Why G2 got a lot of hacks in first hour?

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

I can't understand how it works in Problem E. After all, we need to take exactly the neighboring elements and change the signs in them. If there are 7 numbers, for example -1 -2 -3 4 -1 -2 -3 the sum of 16 is not possible.

  • »
    »
    13 months ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it
    • First, take -3 and -1 as a boundary, then the array will become -1 -2 3 4 1 -2 -3
    • Next, take -2 and -2 as a boundary, then the array will become -1 2 3 4 1 2 -3
    • Last, take -1 and -3 as a boundary, then the array will become 1 2 3 4 1 2 3

    You can make all the element in $$$[l,r]$$$ positive if $$$a_l<0$$$ and $$$a_r<0$$$ and $$$a_{l+1} \cdots a_{r-1}$$$ are positive, so it is not correct to take neighboring elements.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Select 2 neighboring elements and change their signs. That's what the condition says. I don't understand it.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Think it this way: '-' sign can just travel anywhere along array, bcoz if we do operation on 1 positive and 1 negative number signs of them will interchange, in this way we can make '-' sign travel along array.

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

Why my solution for problem D is wrong 191979249? and that is the code:(for single test case):

UPD: I solve it using this method and it is accepted

int n;
    set<int>h1; set<int>h2;
    cin >> n;
    char c[n]; int ar[n];
    for(int i=0; i<n; i++){
        cin >> c[i];
        h1.insert(c[i]);
        ar[i]=h1.size();
    }
    for(int i=n-1; i>0; --i){
        h2.insert(c[i]);
        ar[i-1]+=h2.size();
    }
    sort(ar,ar+n);
    cout << ar[n-1];
»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can check my answer

        int n;
        set<int>h1; set<int>h2;
        cin >> n;
        char c[n]; int ar[n];
        for(int i=0; i<n; i++){
            cin >> c[i];
            h1.insert(c[i]);
            ar[i]=h1.size();
        }
        for(int i=n-1; i>0; --i){
            h2.insert(c[i]);
            ar[i-1]+=h2.size();
        }
        sort(ar,ar+n);
        cout << ar[n-1];
    
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Well, it was surprising to me to know how the code for G2 went TLE during the comp (Though I know it was tightly bounded, it passed the given TCs after the comp, THE SAME CODE)...

Can somebody hack it or let me know if it is still tightly bound on those TL?

Here's the code — #192051148 Python o_O

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

Can someone explain F?

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

    I'll assume you read the editorial for F but could not understand that solution, so I'll go ahead and try to explain another approach.

    For each position i, we need to know how many times that position was modified by the operation. For queries of type 1, we get an interval [l, r] and we need to apply the operation on every position i from l to r. But how do we do that?

    We could have an array initially filled with zeros to maintain a counter of how many operations were done for each position. Say, for n=5, this array would start as [0, 0, 0, 0, 0], and if we got a query of type 1 in the interval [3, 5], our array would update to [0, 0, 1, 1, 1], as we did one operation on positions 3, 4, and 5.

    Now, a simple way to maintain this operation counter array would be to iterate over each position from l to r, whenever we receive a query of type 1, and add 1 to each position. But straightforwardly doing that would TLE, as it would take O(n) (linear time) to process each query of type 1.

    But what if we could do this update operation on our array of counters in O(logn)? That is where the data structure BIT (Binary Indexed Tree, or Fenwick Tree) comes in handy. We can do range updates (say, add 1 to each position from l to r) in O(logn). If this is your first time hearing about this data structure, I suggest you read a bit more about it. It can be a bit daunting to understand at first, but the code is really easy.

    Well, now that we can process queries of type 1 in O(logn) time, now we're left with queries of type 2. To process those, we only need to read the value present in our array of counter, for the requested position. After reading this value, we can apply the operation in a straightforward manner, as it is really fast.

    Here is my submission to make more sense of what I tried to explain. Please let me know if you have any more questions and I'll try my best to answer them.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    The naive approach would be to iterate from $$$l$$$ to $$$r$$$ and apply the changes as mentioned in the statement. However, the time complexity is $$$O(nq)$$$ for this approach which will TLE.

    Consider what happens when we apply the operation $$$a[i] := d(a[i])$$$ to an index $$$i$$$ (here $$$d(x)$$$ denotes the sum of digits of $$$x$$$). Clearly, $$$d(a[i])$$$ is $$$O(\log a[i])$$$, since there are $$$O(\log a[i])$$$ digits in $$$a[i]$$$, and each of them is upper bounded by $$$9$$$. So roughly the operation corresponds to doing $$$x \mapsto c \log x$$$.

    Intuitively, the idea is that this reduction is huge, and the number of times you will need to apply this operation till you get a single digit number is quite small. At least you can show that every time we apply this operation on a number having at least 2 digits, the number of digits never increases after applying this operation, and in fact it decreases by at least 1 after at most 2 operations. So you need at most $$$18$$$ operations (which is a very loose bound, and the editorial shows that you can replace it by $$$3$$$) under these constraints to get to a single digit number, which satisfies $$$x = d(x)$$$. So after a small number of operations on $$$a[i]$$$, you end up with a single digit number, after which applying the operation on it doesn't change the number.

    So let's do this mentally: maintain a (sorted) list of indices which have $$$a[i] > 9$$$. These are the indices on which doing the operation can potentially change the number. When you're applying the update on a range, you find the indices in this list that will need a change (the remaining ones are fine as they are). Let's not think about how we will find the indices at this point. For each index, we will process it at most $$$18$$$ times before it gets out of the list. So overall, the total number of indices considered is $$$18n$$$.

    Now using a std::set and lower_bound, you can find and update the (sorted) list in $$$O(\log n)$$$ time per operation.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, if we have list [1, 2, 3, 4, 5], and l, r = 2, 3, we start at a[1] = 2, then we check every other element <= r and if it's < 10, we erase it? So, if a[1] and a[2] will become < 10 after that, our list will be [1, 4, 5]

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

      used the same concept but i got runtime error on test 3 whats the issue ?

      code — https://codeforces.com/contest/1791/submission/192231836

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

        You did low = *it; after removing the iterator from the set. From here, iterators that are erased are not valid anymore. You should set the value of low before you erase it.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Approach
    Solution
»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

my first fst round... it teach me a lot.

»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone tell me why this got hacked for G1? Submission https://codeforces.com/contest/1791/submission/191967985

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

Did they change tests for C. I had done a typo in my code, a <= was == but it went through during the contest and it was accepted, it was accepted after the competition as well, but just today it turned into being not accepted. From a positive rating change to a negative rating change, nice.

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

I didn't get the rating. Does anyone get ? **** NOTE: This is my first contest

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

I like how G2 has like 58 tests but still wrong greedy solution gets AC

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

i have some issues with the problem F I used https://cp-algorithms.com/data_structures/fenwick.html#finding-sum-in-one-dimensional-array they skipped my submisions

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

what can i do i get skipped my problems

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code might have significantly matched with someone else's code then. You can check your talks or post about it on a specific blog about same.

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

My solution is skipped and i didn't Cheat we just at same university and think in same way

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ~ think in same way
    hnmm that makes sense

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

I recently got a message from Codeforces team that my solution 191923515 matches with 192031691. But I used the segment tree code template from 188598221 which was used long ago in some contest and I usually use the same template as this one. MikeMirzayanov please check it once, I haven't copied the code from some other user, I just used a previously used template of code which I usually use for implementation of segment tree. We all study at the same university so we use the same template of code we shared once. I hope the plagiarism is removed and my solution is judged.

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

Hopefully, this was my last rated Div. 4 round.

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

I got a mail from the codeforces that my solution 191964891 for the problem 1791G1 significantly coincides with solutions heavierfire/191964891, abhinav.maurya202/191979043. It is a pure coincidence case and I have not copied it from anywhere. The variables used in the code are pretty common and there is a very high probability that it can be used by others. And also the logic for the problem was also very standard in my opinion.

So I request you to please have a look and consider my submissions for the contest.

flamestorm, SlavicG, MikeMirzayanov and mesanu

Thanks

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

Hello Codeforces and MikeMirzayanov

I recently received this message that my code (191979043) significantly coincides with solutions (191964891) of this another person code whom I don't know and have no single information about him,

Attention!

Your solution 191979043 for the problem 1791G1 significantly coincides with solutions heavierfire/191964891, abhinav.maurya202/191979043. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I don't have no "conclusive" evidence. I didn't share my code with anyone, and I didn't even share my idea with anyone before contest finished. I use my local VS Code editor to write code, so my code is unlikely to leak.

This problem is simple, we just need to sort after adding the indices and anyone could have come up with this idea, and the solution is short. Also my way of writing code is also very simple. So coincidence can happened. So check this again please. And please give my rating back

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

I don't know why the code of my F question (191945896) and (191987078) in this competition is so similar. I didn't have anyone around me at the game and none of my friends that I knew were playing. That account is not my account, both of these accounts are not rated, there is no interest relationship between me and that person, and I do not need to provide the code to that person in div4 competition

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

can anyone please help with approach on problem F