Day 37 | Up-Solving 822 Div 2 A B C | C++

We are back up solving the Codeforces contest after learning about graphs recently.

Today we will be solving the First 3 problems of the contest. Discussed Sieve of Eratosthenes in 3rd Problem (Removing Smallest Multiples).

Select Three Sticks

Input

4
3
1 2 3
4
7 3 7 3
5
3 4 2 1 1
8
3 1 4 1 5 9 2 6

Output

2
4
1
1

Let's say there are 3 integers a, b, and c (in increasing order). We want to change values to make them equal.

If we are targeting making all values be x

Then change sum will be

change = (c - x) + (x - a) + abs(x-b);

Note - x will be somewhere in range [a,c] because it does not make sense to go out of range

If we expand the equation

change = (c - a) + abs(x-b);

Now, c-a is constant for given c and a but the minimum value of abs(x-b) depends on x

Thus best x will be equal to b

Therefore change -> c-a

Now to minimize c-a, just sort the array and find min(a[i+2] - a[i])

#include<bits/stdc++.h>
using namespace std;

int arr[310];

void solve(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    int ans = INT_MAX;
    for(int i = 2; i < n; i++){
        int a = arr[i-2];
        int b = arr[i-1];
        int c = arr[i];
        ans = min(ans, c - a);
    }
    cout << ans << "\n";
}

int main(){
    int t;
    cin >> t;
    while(t--)
        solve();
}

Bright, Nice, Brilliant

Input

3
1
2
3

Output

1 
1 
1 1 
1 
1 1 
1 0 1 

I will tell the truth, I was a little bit confused about how to try it until I tried to understand how Test cases did it. And looking at TC 3, gave me the idea.

Let's have a look at TC 3 -

I thought of keeping it same and drawing one more row, we get something like this

It is quite obvious here that if I light up First and Last, we will be okay as per the condition in the problem.

Now, Let's add one more row and check -

We see the same pattern here again

Similarly, If you draw more patterns, it seems like the to itsarethe the itsfirst and last torch needs to be lit

which you can implement like this

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cout << (j == 1 || j == i) << " ";
        }
        cout << "\n";
    }
}

int main(){
    int t;
    cin >> t;
    while(t--)
        solve();  
}

Removing Smallest Multiples

Input

6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

Output

0
11
4
4
17
60

Before attempting this problem, let's try to understand one algorithm called Sieve of Eratosthenes

Learning Moment​

Sieve of Eratosthenes

This algorithm is used find the prime numbers up to N in O(Nlog(N)).

How?

We simply eliminate multiples of all prime numbers.

We do this-

1. List Down Numbers from 1 to N

2. Cut 1 because it is not prime by default

3. Take 2 and from it's next multiple cut all the multiples that is 4, 6, 8, ..., N

4. Take next non-cut number and do same for it's multiple keep doing this

A working example where N = 20

In the end, all the primes are remaining.

We code Sieve (we call it that because naming it whole every time is an inconvenience)

int notPrimes[N+1] = {};
notPrimes[0] = 1;
notPrimes[1] = 1;
for(int i = 2; i <= N; i++){
    if(notPrimes[i] == 1){
        continue;
    }
    for(int multiple = i*2; multiple <= N; multiple += i){
        notPrimes[multiple] = true;
    }
}

PS: Btw I know my naming convention is not good here, I just used this convention to explain code.

Time Complexity - O(NlogN) - We will talk about it's proof sometime later

Now, you don't need to find prime numbers, but it is beneficial to know that you can traverse multiple its numbers in this way and still have the complexity of O(Nlog(N))

Observation-

If we are deleting some number X and its cost is Y.

If Y != X,

1. Then we would have deleted Y from the set before X Because choosing Y we will delete its smallest multiple that is Y right now only

2. Y may be deleted by another number If we want to delete 3, 6, 12, 24 3 can delete 3,6 (not anything more as it will next delete 9) 6 can delete 12 (not anything more as it will next delete 18) 12 can delete 24

We do this

1. Iterate over all numbers 1 to N

2. If the number is to be deleted

   1. We iterate over multiple of numbers and keep deleting

   2. We stop if a multiple is not to be deleted or multiple over N

Please like and share my posts if they are helpful.