Vladosiya's blog

By Vladosiya, history, 2 months ago, translation, In English

Hello! Codeforces Round #834 (Div. 3) will start at Nov/18/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

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

Note that the penalty for the wrong submission in this round 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 a trusted participant of the third 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 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.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, DmitriyOwlet and Vladosiya.

We would like to thank: mumumucoder, Enkognit, orloffm, TeaTime, ilyamzy, Olympia, oukeree, 74TrAkToR, molney, elseecay, bigDuck, Nickir, Be_dos, OAleksa for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

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

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

Div 3 after a long time...

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

YEAHHH div 3 is the best opportunity to become a specialist.. ;D

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

As a tester give me contribution

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

    As a not tester, I gave you contribution

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

      As a not tester, I gave you contribution too :)

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

        As a participant, I gave you contribution too.

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

          :))

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

            As a contestant, I gave you contribution too.

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

              :/

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

                As a newbie, I have nothing but to see.(^///^)

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

                  as newbie too, I can understand you my friend :/

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

                  You are pro-newbie, I am just newbie. (●'◡'●)

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

    Negative contribution given boy....

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

OMG DIV 3! HOPING FOR GLACEON COLOR!!! never, Leafeon. is the best :sunglasses:

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

Omg blue round

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

Div.3! Hope to Specialist!

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

Aleksamaster is the best tester , Oro najjaki

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

Among us

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

End term Exams and contest on same day :(... I guess I'll miss my becoming pupil chance ..

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

GL

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

Good luck to everybody who gives this contest. Cheers.

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

All the best everyone for the contest.

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

I swear, this time I am going to change color!

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

OMG Blue Round

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

Time to change my rating.

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

opportunity to get some plus after a long time..

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

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

    I relate!

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

    I can relate too

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

    Really thats so true. But because of that university exam my mind was already exhausted and messed up in such easy problems :(

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

    HOW CAN WE KEEP PHOTOS IN COMMENTS?

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

I will try my best to become expert.Only need 20 scores,best wishes.

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

Hoping For 1300 :)

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

OMG div 3 , hoping for big +ve delta

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

someone please help me understand this statement. what is the true meaning of this statement? how it will work?

Note that the penalty for the wrong submission in this round is 10 minutes.

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

    Every time you submit a wrong submission 10 minutes of penalty gets added to you after getting accepted on that problem.

    the penalty is calculated as the time spent on all the problems you solved (for ex. if you solved A in 8 minutes and B in 35 minutes your penalty is 8 + 35).

    the penalty is used to rank the contest's participants, if two participants have solved the same number of problems the one with smaller penalty ranks higher.

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

****I am waiting.I will do my best.

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

OMG Div. 3 it is good opportunity to get GLACEON COLOR!

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

Never miss the rounds that written by ITMO University team

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

where I will get the contest link

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

    Go to the contest section Codeforces page. Find round 834 and register before the contest

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

Div3!!

Hopping for green color(Pupil)

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

Good luck everyone, I hope everyone enjoys the round. Don't worry about rating. As a programmer we should enjoy contest more than having the tension of rating change.

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

Good luck for everyone . Do your best to be the best !!

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

I didn't compete with you a month ago, so i am in a hopeless situation, what should i do?

»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

It would be nice to finally fix language selector issue and remove excessive use of flags.

Sources with supporting arguments:

Codeforces Language Picker -- chrome extension to see how fixed codeforces language picker would look like.

Please support the initiative and stop reinforcing poor UX practices.

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

Good luck everyone :)

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

Goof luck everyone!!!

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

Hope to become an Expert.

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

What if it is my 5th rated round? Will I become trusted participant if I will solve a problem in it?

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

great

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

omg blue round

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

I hope to become a specialist soon

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

This round seems to be a more interesting one:)

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

NO!!!!! I lose again

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

How to solve G?

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

    I used a greedy idea:

    Starting from the reverse direction...

    However, I haven't proved this idea in the contest, so I'm not sure about the systests. If someone else who have proved it can mention it here, then it would be helpful.

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

      Why max unused? We want the minimal permutation, so should not we place minimum in the range?

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

        Notice that I am iterating from index N to 1, so using the maximum ones at higher indices is more optimal than using the minimum ones.

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

      It seems logical...

      Everytime you pick the maximum possible choice and you ignore smaller values which have higher chances of being used in another pair than the max value ($$$1$$$ is smaller than $$$n-1$$$ values, $$$2$$$ is smaller than $$$n-2$$$ values, and so forth...)

      So even if it can be used somewhere else also, no problem because there is another smaller value you can put there (and if there isn't, it's impossible to construct the permutation).

      Getting the max guarantees the smallest permutation also.

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

    I used a Maximum Segment Tree.

    • Initialize int[] answer of length n which will store our final permutation. On every odd position(0 based indexing) fill the elements of int[] b. Because we want minimum number to be in front position, so it makes sense to keep the maximum element on the second position.
    • Now we have filled half of answer array. Now we iterate integers from n to 1 and check if its not present in answer, find the right_most element in answers array which is less than this current number. So we can safely place this number on left hand side of the found number. Now delete this number. This type of operations can be done by segment trees.

    My solution is not clean as wrote in hurry in contest and its a newbie's code. My AC 181520850

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

    If you are a braindead grey (like me) and never thought to solve the problem backward, you can also binary search on a lazy add/min segtree.

    https://codeforces.com/contest/1759/submission/181510473

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

    Solution for G:

    From $$$i=n/2 \space to \space1$$$,for each $$$b[i]$$$,find $$$max(x)(x<b[i],x≠b[j])$$$ .

    Proof:

    Note $$$X=max(x)(x<b[i],x≠b[j])$$$.

    Consider $$$"... Y\space b[j] ... X\space b[i] ..."$$$ and $$$"... X \space b[j] ... Y\space b[i] ..."$$$.Because $$$X$$$ is the largest number less than $$$b[i]$$$,we get $$$X>Y$$$,the former has a smaller lexicographical order.

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

      Yeah It is so easy compare to other problems:(

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

What was the correct approach to solve problem C?

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

    You can consider cases like: a == b then answer is 0 distance between a and b is >= x then answer is 1 distance between a and l or a and r is more then x and then distance from that end is more then x ( to the b ) then the answer is 2 and the last case is to make the deistance to one of the endpoints equal to at least x, and this just adds 1 to the previous case, so the answer is 3 in the last case, if you can't do that than the answer is -1

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

    Check if ans==0

    If possible use 1 step, else

    if possible go to left or right end, then to b, else

    if possible go to left end then right end, or to right end then left end, then to b.

    else not possible.

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

    you only have limited startegies: go left boundry then right boundry thn target go left then target go right then target go right then left then target just check if you can do the transition in these cases and print the minmum number of steps you can do to reach target (b) using one of the above stretegies or print -1 if all of the above stregies are invalid ps : ofcourse if a == b you don't need to do anything so the answer is 0 so the answer will be 0, 1, 2, 3 or -1

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

      Hey, could you probably tell what edge case I might be missing on?

      https://codeforces.com/contest/1759/submission/181515633

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

        hmm, honestly i don't understand your logic what i did was simply for each strategy to check if you can go from a point to another using abs(p1 — p2) >= x that was very simple you can also take alook at mycode for example i check if i can go from a to l and from l to r ad from r to b as follow: abs(a — l) >= x and abs(l — r) >= x and abs(r — b) >= x if this condition is true you can use this strategy

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

          Thanks for responding. Honestly, I think I am doing the same thing.

          These are each of the if conditions.

          1) If starting temperature is the ending temperature, then print(0)

          2) So, if I cannot go to the right extreme and I cannot go to the left extreme, then I am printing -1.

          3) If the difference between starting point and ending point is greater than x, then printing 1.

          4) If I can only go the left extreme, then I am checking for three conditions again :

          -> Whether I can directly reach to the ending point from the left extreme (with diff greater than x). If this is possible, then print(2)
          
          -> Otherwise go to the right extreme from left extreme and check if it is possible to go to the ending point from right extreme (with diff greater than x). Therefore print(3)
          
          ->Else print(-1)

          5) If I can only go the right extreme,

          -> Whether I can directly reach to the ending point from the right extreme (with diff greater than x). If this is possible, then print(2)
          
          -> Otherwise go to the left extreme from right extreme and check if it is possible to reach the ending point from the left extreme (with diff greater than x). Therefore print(3)
          
          -> Else print(-1)
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Take a look at Ticket 16432 from CF Stress for a counter example.

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

              Thanks I was actually printing -1 in the else case but should've printed 2.

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

            yeah you are right i got confused from that too many conditions in your code :) btw, ignore the message i sent too, i discovered that i misunderstood your replay about starting and ending point and couldn't sent another replay because i got limited messages

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

              Np. Figured it out. Thanks.

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

    The important thing to realize is that the answer is between $$$-1$$$ and $$$3$$$.

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

what's the silliest mistake a person can ever make? i got 3 penalties in E just because i was sorting array before taking the input.

like this

maybe i could have got my first 2 digit rank in Div 3.

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

I feel like F is about finding every corner cases (which I wasn't able to)

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

I felt problem D to be tougher than E & G :|

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

    Me the same. I wasted too much time in D and then found out E was much easier to figure out. But it was too late... :(

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

Can someone tell me what's wrong in my submission of D

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

    I am not sure what is your code doing. But i found a test case:

    1
    513943340 921893439
    
    Brute Force Output: 
    256971670000000000
    
    Obtained Output: 
    462549006000000000
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was interesting...

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

Can any one tell, what would be the difficulty level for the problem D?

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

can someone explain problem c and d

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

    The answer of problem C lies Between 0 to 3.. Otherwise -1. Try to figure out how this logic is true!!

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

    My solution for D:

    k zeros at the end of a number means that this number can be represented as 10^k*a, where a is some number. 10 = 2 * 5, therefore, in the answer we need to maximize the number of pairs {2, 5}

    1) Decompose n into prime factors and count the number of 2 (let it be q2) and 5 (let it be q5). If q5 > q2, then we need to add q5 - q2 twos in the price increase coefficient. If q2 > q5, then q2 — q5 fives. If q2 == q5, it means that we cannot "collect" tens from two numbers and add a zero to the end of the answer.

    2) After that, I started picking up a number from [1; m]. We need as many 10 as possible in the answer multipliers, so I multiply the number (2 or 5) that I lacked to create pairs with multipliers of the number n, abs(q5 - q2) times by itself. tmp = (q5 > q2 ? 2 : 5)^abs(q5 - q2)

    3) Then, I need to maximize the quantity of 10 at answer and, if there is solutions with the same number of zeros, need to get maximum. So we can increase tmp variable. To increase the number of tens, you need a number that can be represented as 10^k * a. This is easy to do if you take a digit of the highest digit and add to it (the length of the number - 1) zeros. For example, when m = 21345, you need to take 20000. So we have to do something like this:

    r = m // tmp
    t = int(str(r)[0] + (len(str(r)) - 1) * '0')
    tmp *= t
    

    4) When working with the tmp variable, it is necessary not to forget that it cannot be more than m, so it is necessary to set conditions that tmp <= m everywhere you are increasing tmp.

    The answer is n * tmp or n * m if there isn't solutions with zeros at the end.

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

181495692

can someone tell me where i went wrong in problem B . my approach was 1<=i<=m add b[i] and s = total sum.

find if there a n such that n(n+1)/2 == total sum . then yes or else no .

why wouldn't this work

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

my solution for 'A' was very stupid can it pass hacking and system test or will it get tle (due to using substr) can someone try to hack it?

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

My code return negative value in problem D but i am doing only multiplication in my code. can someone please help me with that

here is my submission 181501309

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

    When you are multiplying it's crossing the limit for integers. Try with long integers

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

    What you are facing is integer overflow, try using 64-bit integers.

    That is something you will often have to care about.

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

how to solve F?

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

    Observation 1. The maximum answer is $$$p-1$$$, One case where this happens is where the number is a single digit.

    Observation 2. A full carry across one or several digits happens only once at most.

    Now think of it like this. How many steps do we need when our number is 0? That's $$$p-1$$$. Now, how many steps do we need when we have a few more digits existing in the number, smaller than the last digit? Might be smaller than that, but we may still have to run a full cycle. For this reason, we manage two variables, $$$\mathbf{pp}$$$ and $$$\mathbf{pk}$$$. $$$\mathbf{pp}$$$ is the smallest number connected as a continuous group with $$$p$$$, $$$\mathbf{pk}$$$ is the same but it is for the last digit. These two variables serve as boundaries. To be precise, $$$\mathbf{pp}$$$ serves as the boundary before the carry, $$$\mathbf{pk}$$$ serves as a boundary after the carry. So, you should be very well able to case-work with $$$\mathbf{pk}$$$ on whether we need a carry or not. Now the rest is just implementing the carry, and fiddling with these two variables (and the last digit).

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

      phew, i was scared that you abandoned CF after 4 days of inactivity

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

    Solution for F:

    Note $$$k=a[n]$$$,consider $$$k->k+1->...$$$

    Case1:

    $$$k->k+1->...->p-t$$$

    In this case, there is no carry bit.$$$0,1,..,k-1$$$ must appear in $$$a[]$$$.

    $$$p-t$$$ is the largest number that does not appear in $$$a[]$$$.

    Case2:

    $$$k->k+1->...->p-1->0->...->k-t$$$

    In this case, you should recalculate $$$a[]$$$(consider carry bit),note it as $$$b[]$$$.

    $$$k-t$$$ is the largest number that does not appear in $$$a[]$$$ and $$$b[]$$$.

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

Great Contest!

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

Accidentally hacked jiangly submission with Ticket 16429 from CF Stress :)

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

    coooooool!

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

    jiangly's algorithm: the greatest element of an array is always the last element.

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

How to solve D ?? Made me drop the contest..

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

    Just find out how many 2 and 5 you get from m and (1<=x<=n) if(x==1) answer will be m*n; otherwise m*x;

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

      Sorry can you elaborate ??

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

        You'll get $$$n$$$ 0's in the suffix of the answer if the factorization of $$$n * k$$$ ($$$1<=k<=m$$$) contains atleast n fives and n twos. Greedily check if you can get $$$x$$$ zeroes in the suffix of the answer for every x uptill about 18 should suffice (since n * m is atmost 1e18).

        For example, if you want $$$x=5$$$ and $$$n$$$ contains $$$4$$$ 5s and $$$3$$$ 2s in it's factorization. Then you require such a k that has atleast $$$x-4$$$ 5s and $$$x-2$$$ 2s

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

        ~~~~~

        ~~~~

        first i'll find out no of 5 and 2 in m; while(m%5==0) { m5++; m/=5; } while(m%2==0) { m2++; m/=2; }

        then i have to find a number x. let x=1; x<n; i'll try to equalize no of 2 and 5. ex. if(m2>m5) multiply 5 with x;(x<=n) same for m5.multiply 2 with x;(x<=n) if both of them are same multiply 10 with x;(x<=n)

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

Here's my Submission of problem B. Getting WA in 69th test case which can't be seen. Can anyone help me providing me with a test case that will help me find out the loop-hole of my code?

My idea:

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

    Take a look at Ticket 16430 from CF Stress for a counter example.

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

    wait the sum of the elements he found + the sum of the lost elements must be equal to some n where n = n(n+1)/2 this should do right ?

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

I think more people will solve E if E and D swap position

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

Could someone please explain why my code for E fails on test case 3? https://codeforces.com/contest/1759/submission/181515762

I have used the following approach, there may be at most 3 orders of choosing potions whenever we encounter an astronaut with health greater than the humanoid's health, and they will be GBG BGG GGB

The final answer should be the maximum of the number of astronauts we can defeat using one of the three orders. Please point out the logical inconsistency in my approach or provide an example where my code fails.

(the recursive way to solve this did strike my mind, but I decided to do it this way as it seemed simpler)

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

    As the humanoid can gain more health as it consumes an astronaut, you should iterate until you cannot consume an astronaut anymore instead of binary search the position at the beginning. After that you will drink a potion then try again that strategy. There are 3 ways to drink potion (2,2,3), (3,2,2) and (2,3,2) so just try all of them.

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

Can somebody tell me what's wrong with my B code? (Pretest 4 WA)

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

    your intuition ?

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

    I figured it out, I thought the original permutation's size can't be over 50, but the problem statement never actually said that, only the found elements can't be more than 50

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

Personally to me, it felt more like a div4 round. The maximum difficulty rating for the problems of this contest should be around 1700 or 1800 I guess.

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

Someone please tell me how the humanoid can absorb the astronaut with power 15 in the case 7 of Problem E. It says that the humanoid can absorb an astronaut with power strictly less humanoid power. It confuses me a lot.

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

    Use blue first.

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

      Oh!!! I think the solution is greedy, which is not valid. I think too simply. Thank you very much !

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

Take a look at submissions of the rk8 NightSky_Yozora.

Obviously, there are 4 coding styles in his submissions:
Problem A, B, C is solved by the first person;
Problem D by second;
Problem E by third;
Problem F, G by fourth.

it's a violation of the rules, isn't it?

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

    Sir, what about Sneh_Patel_0701 he has cheated in previous rounds too. But didn't get caught. Now he is going to become expert. Is there any punishment for them?

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

Can someone point out what I may be doing wrong? What edge case I may be missing?

https://codeforces.com/contest/1759/submission/181520511

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

1759D - Сделай круглым

Greedy approach : We will try to append as many 0's at the end within given constraint How to find it ?

Let's take input examples : 6 11

  • We can have 30 60 90 120 ...
  • But only 30 and 60 falls within constraint
  • 6*5 = 30, k = 5
  • 6*10 = 60, k = 10
  • 6*15 = 90, k = 15 not possible

Now we will build our answer by checking if I append zeros can I get some k such that it falls under constraint, once we can't append 0's we will break loop

How to do it? How to find possible values of k? Well it's easy, we can use some mathematics


We will check if I can have some possible number as z*10 z*100 z*1000 and so on... z [1, 9] z should be minimum possible as we are using greedy
we have our n as 6 so to append 0 at the end I can have z*10
n   = 2*3
ans = z*10
so we have ans = n*k, 1 <= k <= m
n = 6 k = 5  z = 3 ans = 30
n = 6 k = 10 z = 6 ans = 60

How to find k ? Let g = gcd(x, n) = (10, 6) = 2 then k = x/g = 10/2 = 5, k can take minimum value as 5 within given constraints But as we have to find max answer if we append some zeros so we will find k as k = (11/5)*k k = 10

Here's my code

#include <iostream>
#define int long long int
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;
    while(t--){
        int n, m;
        std::cin >> n >> m;
        int x = 10, ans = n*m;
     
        while(1){
            int g = std::__gcd(x, n);
            int k = x/g;
            if(k <= m){
                ans = k*(m/k)*n;
            }
            else
                break;
            x *= 10;
        }
     
        std::cout << ans << "\n";
    }
}

Thanks :), You can ask doubt

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

    can u explain little more how exactly u getting logic to finding k?

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

      k = x/gcd(x, n) x goes from 10, 100, 1000, ...

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

        now i get it thanks

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

        I tried doing this but it was always giving wrong answer in C++ (probably some overflow issues or something like that) but it worked fine in Python

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

    Hi, @djay24 What's your intuition behind (m / k) .?? like, you used k = (11/5)*k, why are you doing so, can you explain.?

    Thanks in advance.

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

      1 <= k <= m Initially k is minimum possible value it can take within given constraints So k can take values from k, 2*k, 3*k, 4*k, ... z*k, I have to find such z such that z*k is maximum possible but less than equal to m, so I am multiplying by (m/k) factor... That's why initially k = 5 but after we can see k = 10 is best answer so k = 5*(11/5)

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

Is there a problem with hacks in problem F? Any hack in this problem still in the waiting process. Screenshot-2022-11-18-200635
Also Some of them give unexpected verdict. MikeMirzayanov

Upd: Hacks still in waiting state after 6 hours problem F hacks

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

What is wrong with my B task submission ? Every time I generate the sum of an arithmetic progression using 2*a1 + d(n-1)/2 * n and check if they can be equal

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

    It fails for this TC

    1
    9 9
    11 6 5 13 7 10 2 3 12 
    
    Expected Output: NO
    Your Output: YES
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wait the sum of the elements he found + the sum of the lost elements must be equal to some n where n = n(n+1)/2 this should do right ?

    why wouldn't this work?

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

Binary Search in Problem B.

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

    wait the sum of the elements he found + the sum of the lost elements must be equal to some n where n = n(n+1)/2 this should do right ?

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

E and G are far far easier than D (did'nt read F yet)

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

Has anyone solved E with a memorized dp? the recursive approach is very simple but i cant seem to get my head around implementing a dp solution.

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

    What is your state? I had an iterative dp where $$$dp[i][j][k]$$$ denoted the max cost achievable till index $$$i$$$ if you take $$$j$$$ green potions and $$$k$$$ blue potions in total. While transitioning, I tried to take $$$l$$$ green potions and $$$m$$$ green potions in the $$$ith$$$ step. If the cost achievable without taking these $$$l$$$ potions and $$$m$$$ blue potions was greater than $$$a[i]$$$ then I greedily add $$$a[i]/2$$$ to my answer and then multiply by 2 and 3 on the basis of how many $$$l$$$ potions and how many $$$m$$$ potions I took.

    Submission

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

      Thanks, makes a lot of sense! i had the same 3 states but had trouble differentiating the cases where the potions were taken before or during the round.

»
2 months ago, # |
  Vote: I like it -9 Vote: I do not like it

177670435``

````````Please, Who can help me to find out the queetion of problem D. I guess my code's part of maximal price of several possible variants is wrong.because the Checker Log told that expected: '874999993000000000', found: '749999994000000000'.

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
typedef long long ll;
ll m,t,n,cnt1,cnt2,sy,i;
ll qpow(ll a,ll b){
    ll sum=1;
 while(b){
if(b&1) sum*=a;
 else a=a*a;
 b>>=1;
 }
return sum;
}
signed main()
{  
 cin>>t;
 while(t--){
cnt1=0;cnt2=0;
cin>>n>>m;
ll good=n;
while(1){
if(n%2==0) cnt1++,n=n/2;
if(n%5==0) cnt2++,n=n/5;
if(n%5!=0 && n%2!=0) break;
}
if(cnt1>cnt2){
 sy=cnt1-cnt2; i=1;
 while(i<=qpow(5,sy)&&i<=m) i*=5;
 if(i>m) i=i/5;
 if(i>qpow(5,sy)) i=i/5;
 
 while(i<=m) i*=10;
 i=i/10;
 ll tmp=i;
while(i<=m) 
 i=i+tmp;
 i=i-tmp;
 cout<<good*i<<"\n";
}

else if(cnt1<=cnt2){
 sy=cnt2-cnt1; i=1;
 while(i<=qpow(2,sy)&&i<=m) i*=2;
 if(i>m) i=i/2;
 if(i>qpow(2,sy)) i=i/2;
 while(i<=m) i*=10;
 i=i/10;
 ll tmp=i;
 while(i<=m) 
 i=i+tmp;
  i=i-tmp;
  cout<<good*i<<"\n";
} 
} 
 return 0;
}- - 
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hello!can i get some help please

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

      guy you... have a mistake in function qpow. Remove else, because you should increase a in every iteration.

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

        oh!thank sincerely!!!,I finally solved the fuking problem, -----love from china

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

My feedback to the round authors (just for problems A-D (problems I managed to solve in the contest)):

A: Easy implementation problem, the problem statement could've been written more simply because I needed to look at the examples to understand the problem without spending like 5 minutes. It shouldn't be like that since this is Div.3 A problem.

B: OK problem, nothing else to say.

C: Good problem, even though I don't prefer problems with $$$l,r$$$, and many if statements like this one. I like the problem.

D: Best problem (rating $$$\leq{1400}$$$) along with 1748B - Разнообразные подстроки in the past few weeks in my opinion. It's always interesting to solve number theory problems.

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

The feeling when Div. 3 round was more problematic for you than Div. 2 round XD

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

i have a problem.In problem e ,java,i use the same algorithm to solve this problem,but three different sorting methords(priorityqueue, Collections.sort,Arrays.sort),the first two is accepted,but the third one has TLE.Can anyone figure it out?

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

    Arrays.sort uses a dual-pivot quicksort algorithm. Unfortunately, its worst case time complexity is $$$O(n^2)$$$.

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

What could be the rating of Problem D?

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

Solutions were already there on YouTube I check the timings. People just copied from there. So unfair

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

Goof luck everyone

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

can anyone please explain me the approach for problem C? I can't figure it out!

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

    you only have the following options:

    1. if a is already at b -> answer is 0
    2. if difference between a and b is >= x -> answer is 1
    3. from a go to l (if possible), then to b (if possible) -> answer is 2
    4. from a go to r (if possible), then to b (if possible) -> answer is 2
    5. from a go to l (if possible), then go to r (if possible), then to b (if possible) -> answer is 3
    6. from a go to r (if possible), then go to l (if possible), then to b (if possible) -> answer is 3
    7. if none of the above is possible, then answer is -1, otherwise it is the minimum of all the cases

    for steps 3-6, we chose either l or r and not any other temperature because its always efficient to use an operation go to the farthest possible index.

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

I like this competition very much. The F and G questions are very simple, which is simpler than the level questions in div2. They do not involve advanced algorithms and data structures, and their meanings are very clear.

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

    i wasn't able to solve F without implicit segment tree with lazy propagation and binary search on it(got MLE 2 times xd)

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

      I remember it was a line segment tree binary, someone did it, maybe you wrote it wrong.

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

        yeah, memory consumption was huge because i didn't use shared ptr or vector, just raw pointers..

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

Can someone please clarify if it was rated? I participated in the contest and solved A but I was not rated. What are the rules for being rated?

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

    The contest doesn't even show in my contest tab. What is the reason for that? Can someone please clear up the confusion?

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

As a pku fresher,I bravely tried. Then made my ability clear yesterday(doggy).

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

NightSky_Yozora was obviously cheating, plz do something.

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

Is this contest was rated for participant whose rating < 1000 ??

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

is This contest was rated for participant with rating < 1000 ??[contest:834 div3]

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

There are still about 40 hacks stuck at "In queue" or "Unexpected verdict" state, despite the fact that the final testing has already been conducted. This is not the first time such a situation arises.

I think that such occasions should be automatically reported to contest managers and, in general, should block the final testing unless fixed.

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

It's showing unrated, does anyone got rated ?

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

Why my rating is still not updated until now?

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

how long till the tutorials are posted

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

Now it`s time for the Ultimate Question of life, universe and everything: Is it rated?

»
2 months ago, # |
  Vote: I like it -29 Vote: I do not like it

All Questions were mathematical as always. No concept used of DSA. Disappointing contest

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

    Mathforces

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

    Apart from D, I don't see how the others are mathematical (don't know about F, since I didn't solve)

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

    Well, D may be a simple math problem, but all other questions are focus on basic algorithm ability. Though I'm a newbie, I think this round is of good quality.

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

    Bruh only D was math

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

Nice problems! I love the round

I hope that I can be specialist xd

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

Why it is not showing any updated rating ? I am not seeing any rating change and even my previous contest rating is showing unrated . Even though I got rating before

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

Waiting for rating change

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

Has this contest turned unrated??? Why the ratings are not updated yet

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

    Wait. But y will get + 47 raiting for this contest

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

Please update the rating

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

Hello, 2 hours ago I got a message that tells my solution for problem C matches with some other participants. Also, this round will be unrated for me and it shows I am out of competition. My solutions are skipped also.

I checked their submissions and found some similarities in logic and I think this is normal as thousands of people are participating here. But their code writing style and solution for this problem are totally different.

Also, this happened to me for the first time. I don't know what to do! Help me if anyone can! Thanks in advance.

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

    Sorry to hear that. You may send emails to the codeforces official account and provide exact evidence to show you didn't share code with other participants. You may get the round into a rated one finally if you are resonable.

    Hope that will help you.

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

    One contest doesn't mean everything.... Try in next contest.

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

      First of all Thanks. I know that but the message says my account can be blocked. That's why I am so tense.

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

I have been skiped , i have not cheated , what i should do to prove that

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

    You have been skipped several times. Just admit it and don't cheat again.

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

      noooooo he didn't cheat of course he just keeps getting accidentally skipped /s

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

      Yes i have skiped before but not this time

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

When is editorial going to be posted?

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

    I liked this round, would enjoy to read the editorial too.

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

When will the editorial be posted?

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

I have recently received a plagiarism warning in Codeforces Round #834 (Div. 3) due to which you have dropped my rating. please review my code. I have not copied it from anywhere. I solely came up with that solution. I spent full 2 hours trying to solve these problems. please revoke this penalty. what is my fault is someone else had the same solution popping up in their mind. It's really demotivating. Please do not do this. Vladosiya

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

https://codeforces.com/contest/1759/submission/182444103 I am Getting Runtime Error in Problem F but not able to find it , It would be great if anyone can help .