Vladosiya's blog

Codeforces Round #834 (Div. 3)
By Vladosiya, history, 2 years 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, senjougaharin and Vladosiya.

We would like to thank: mumumucoder, Enkognit, orloffm, TeaTime, ilyamzy, Olympia, moonveil, 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

Comments Comments (188)
| Write comment?
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Div 3 after a long time...

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

As a tester give me contribution

→ Reply
»
2 years 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:

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

Omg blue round

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

Div.3! Hope to Specialist!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Aleksamaster is the best tester , Oro najjaki

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

Among us

→ Reply
»
2 years 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 ..

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

GL

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

OMG Blue Round

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

Time to change my rating.

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

→ Reply
»
2 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG div 3 , hoping for big +ve delta

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

Never miss the rounds that written by ITMO University team

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

    True. They always have interesting problems.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where I will get the contest link

→ Reply
  • »
    »
    2 years 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

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

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

→ Reply
»
2 years 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?

→ Reply
»
2 years 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.

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

Good luck everyone :)

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

Goof luck everyone!!!

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

Hope to become an Expert.

→ Reply
»
2 years 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?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great

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

I hope to become a specialist soon

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This round seems to be a more interesting one:)

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

How to solve G?

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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?

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
    • »
      »
      »
      2 years 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.

      → Reply
  • »
    »
    2 years 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

    → Reply
  • »
    »
    2 years 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.net/contest/1759/submission/181510473

    → Reply
  • »
    »
    2 years 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.

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

      Yeah It is so easy compare to other problems:(

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the correct approach to solve problem C?

→ Reply
  • »
    »
    2 years 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

    → Reply
  • »
    »
    2 years 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.

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

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

→ Reply
  • »
    »
    2 years 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... :(

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years 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
    → Reply
»
2 years 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?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain problem c and d

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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

    → Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F?

→ Reply
  • »
    »
    2 years 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).

    → Reply
  • »
    »
    2 years 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[]$$$.

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

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

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

    coooooool!

    → Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years 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;

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

      Sorry can you elaborate ??

      → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
»
2 years 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.net/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)

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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)

→ Reply
  • »
    »
    2 years 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

    → Reply
»
2 years 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.

→ Reply
»
2 years 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.

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

    Use blue first.

    → Reply
    • »
      »
      »
      2 years 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 !

      → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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?

    → Reply
»
2 years 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.net/contest/1759/submission/181520511

→ Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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?

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

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

      → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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)

      → Reply
»
2 years 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

→ Reply
»
2 years 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)

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
»
2 years 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;
}- -
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hello！can i get some help please

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
»
2 years 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.

→ Reply
»
2 years 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

→ Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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)$$$.

    → Reply
»
2 years 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

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

Goof luck everyone

→ Reply
»
2 years 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!

→ Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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)

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
      • »
        »
        »
        »
        2 years 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..

        → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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?

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

NightSky_Yozora was obviously cheating, plz do something.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my rating is still not updated until now?

→ Reply
»
2 years 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?

→ Reply
»
2 years 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

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

    Mathforces

    → Reply
  • »
    »
    2 years 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)

    → Reply
  • »
    »
    2 years 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.

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

    Bruh only D was math

    → Reply
»
2 years 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

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please update the rating

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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.

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

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

    → Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When is editorial going to be posted?

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

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

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/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 .

→ Reply