AlphaScorpii's blog

By AlphaScorpii, 6 weeks ago, In English

B. Make it Divisible by 25

Codeforces Round 748 (Div. 3)

Divisibility by 25 only depends on the last two numbers. 00, 25, 50, and 75 are the only allowed possibilities. A number can look like this in it's most general form

$$$\rule{1cm}{0.15mm}0\rule{1cm}{0.15mm}0\rule{1cm}{0.15mm}$$$
$$$\rule{1cm}{0.15mm}2\rule{1cm}{0.15mm}5\rule{1cm}{0.15mm}$$$
$$$\rule{1cm}{0.15mm}5\rule{1cm}{0.15mm}0\rule{1cm}{0.15mm}$$$
$$$\rule{1cm}{0.15mm}7\rule{1cm}{0.15mm}5\rule{1cm}{0.15mm}$$$

and our job is to remove the numbers in the last blank and the middle blank.

My initial idea was quite bad. I stored the input in a long long int and checked if the number was divisible by 25. That solves the base case. In case the number was divisible by 5, it means that the last blank in our above representation was already removed. To remove the middle blank, I just searched for the second required digit.

if (s[s.size() - 1] == '0')
    for (int i = s.size() - 2; i >= 0; i--)
        if (s[i] == '5' || s[i] == '0')
            break;
        else
            ans++;
else
    for (int i = s.size() - 2; i >= 0; i--)
        if (s[i] == '2' || s[i] == '7')
            break;
        else
            ans++;

But the problem with this method is when you have test cases like 50555, where the number is divisible by 5 but there is no 2 or 7 to search for. The code returns an answer of 4, because it went through all the digits and never found a 2 or a 7. If the test case was 5055, I would have been staring at a WA !!

A better way to solve this is to keep in mind all the numbers you have to retain rather than the ones you have to remove. From our general representation,

$$$\rule{1cm}{0.15mm}x\rule{1cm}{0.15mm}y\rule{1cm}{0.15mm},$$$

all the digits to the left of $$$x$$$ need to be retained. Along with them, $$$x$$$ and $$$y$$$ themselves have to be retained. So, if we find a suitable $$$x$$$ and $$$y,$$$ we only need to add 2 to the number of digits before $$$x$$$, and subtract this number from the total number of digits.

Submission

1094. Increasing Array

CSES Introductory Problems

Easy enough question, but I made two mistakes

  1. Each move increments the value of an element by 1. So if $$$x_i$$$ is larger than $$$x_{i+1},$$$ we need a total of $$$x_{i+1}-x_i$$$ moves. I added the number of moves to the final answer but did not increment the value of $$$x_i.$$$

  2. Used int when it was plain obvious that long long was needed.

Submission

1072. Two Knights

CSES Introductory Problems

Math question, the only thing you need to know here is that two knights that attack each other have to inhabit a $$$3\times2$$$ or a $$$2\times3$$$ rectangle on the chess board. The number of ways you can choose a $$$3\times2$$$ rectangle on a board with size length $$$k$$$ is $$$(k-3+1)(k-2+1)$$$ and the number of ways you can choose a $$$2\times3$$$ rectangle on a board with size length $$$k$$$ is $$$(k-2+1)(k-3+1).$$$ After getting the rectangles, we can place the two knights in 2 ways. So the total number of ways two knights attack each other is

$$$2\cdot2\cdot(k-1)(k-2).$$$

The total number of ways we can place two knights in $k^2$ squares is $$$\displaystyle{k^2\choose 2}.$$$ The answer, therefore, is

$$$\frac{k^2(k^2-1)}{2}-4\cdot(k-1)(k-2).$$$

Submissions


 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it