Codeworks 5 questions per day (1700 average) - day 7

Multicolored Cars

Topic translation

【 Title Description 】

Definition $cn{t}_x(i)$ To $i$ moment $x$ The number of occurrences .

Now give $n$ Number $a_1,a_2\dots \dots a_n$,$a_i$ It means the moment $i$ Number of occurrences .$Alice$ Selected a number $m$, Please help $Bob$ Choose a number $k$, Make for any moment $i$, There are $cn{t}_k(i)>=cn{t}_m(i)$. If there is no such $k$ Please export $-1$.

【 Input format 】

The first line has two integers $n$,$m$, Express $n$ Number ,$Alice$ Number selected $m$.

The second line $n$ It's an integer $a_1,a_2\dots \dots a_n$,$a_i$ It means the moment $i$ Number of occurrences .

【 Output format 】

There is such $k$ Please output any feasible solution , If there is no such $k$ Please export $-1$.

【 Data range 】

No more than $10^6$

Title Description

Alice and Bob got very bored during a long car trip so they decided to play a game.

From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this.

Firstly Alice chooses some color $A$ , then Bob chooses some color $B$ ( $A\ne B$ ).

After each car they update the number of cars of their chosen color that have run past them.

Let’s define this numbers after $i$ -th car $cn{t}_A(i)$ and $cn{t}_B(i)$ .

• If KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{A}(i)&̲gt;cnt_{B}(i) for every $i$ then the winner is Alice.
• If $cn{t}_B(i)>=cn{t}_A(i)$ for every $i$ then the winner is Bob.
• Otherwise it’s a draw.

Bob knows all the colors of cars that they will encounter and order of their appearance.

Alice have already chosen her color $A$ and Bob now wants to choose such color $B$ that he will win the game (draw is not a win).

Help him find this color.

If there are multiple solutions, print any of them.

If there is no such color then print -1.

Input format

The first line contains two integer numbers $n$ and $A$ ( $1<=n<=10^5,1<=A<=10^6$ ) – number of cars and the color chosen by Alice.

The second line contains $n$ integer numbers $c_1,c_2,...,c_n$ ( $1<=c_i<=10^6$ ) — colors of the cars that Alice and Bob will encounter in the order of their appearance.

Output format

Output such color $B$ ( $1<=B<=10^6$ ) that if Bob chooses it then he will win the game.

If there are multiple solutions, print any of them.

If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with ( $1<=B<=10^6$ ).

Examples #1

The sample input #1

4 1
2 1 4 2

Sample output #1

2

Examples #2

The sample input #2

5 2
2 2 4 5 3

Sample output #2

-1

Examples #3

The sample input #3

3 10
1 2 3

Sample output #3

4

Tips

Let’s consider availability of colors in the first example:

• $cn{t}_2(i)>=cn{t}_1(i)$ for every $i$ , and color $2$ can be the answer.
• KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{4}(2)&̲lt;cnt_{1}(2) , so color $4$ isn’t the winning one for Bob.
• All the other colors also have KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{j}(2)&̲lt;cnt_{1}(2) , thus they are not available.

In the third example every color is acceptable except for $10$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
int n,m,k,a[1000005],mmax,signm=0;
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&k);
		mmax=max(mmax,k);
		if(k==m){
    
			signm++;
		}
		else if(a[k]>=signm){
    
			a[k]++;
		}
	}
	for(int i=1;i<=mmax;i++){
    
		if(a[i]>=signm&&m!=i){
    
			cout<<i;
			return 0;
		}
	}
	puts("-1");
	return 0;
}

Remove Extra One

Topic translation

Give a length of n Permutation p, Find an element , So that the elements are arranged after taking this element out of the arrangement “records” most .
One "record" Is an element $a_i$ Satisfy ： For each positive integer $1\le j<i$ , $a_i>a_j$.

Title Description

You are given a permutation $p$ of length $n$ .

Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers $a_1,a_2,...,a_k$ the element $a_i$ is a record if for every integer $j$ ( KaTeX parse error: Expected 'EOF', got '&' at position 5: 1<=j&̲lt;i ) the following holds: KaTeX parse error: Expected 'EOF', got '&' at position 6: a_{j}&̲lt;a_{i} .

Input format

The first line contains the only integer $n$ ( $1<=n<=10^5$ ) — the length of the permutation.

The second line contains $n$ integers $p_1,p_2,...,p_n$ ( $1<=p_i<=n$ ) — the permutation.

All the integers are distinct.

Output format

Print the only integer — the element that should be removed to make the number of records the maximum possible.

If there are multiple such elements, print the smallest one.

Examples #1

The sample input #1

1
1

Sample output #1

1

Examples #2

The sample input #2

5
5 1 2 3 4

Sample output #2

5

Tips

In the first example the only element can be removed.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,a[N],sign[N],x=0,y=0,k;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		if(a[i]>a[y]){
    
			x=y;
			y=i;
			sign[i]--;
		}
		else if(a[i]>a[x]){
    
			x=i;
			sign[y]++;
		}
	}
	k=1;
	for(int i=2;i<=n;i++){
    
		if(sign[i]>sign[k]||(sign[i]==sign[k]&&a[i]<a[k])){
    
			k=i;
		}
	}
	cout<<a[k]<<endl;
	return 0;
}

The Meaningless Game

Topic translation

Slastyona And her loyal dog pushk are playing a meaningless but interesting game . The game includes multiple rounds .

Its rules are very simple ： First choose a natural number k. then , Who says （ Or bark ） If you are faster than the other one, you will win a game .

The winner's score will be multiplied by k The square of , The score of the loser can only be multiplied by k. At the beginning of the game ,Slastyona and PurSok Have an initial score .

Unfortunately ,Slastyona I lost my notepad , There is a record of what they have played N History of games .

She managed to recall the final result of each match , But the memory is very vague .

help Slastyona Verify their correctness , perhaps , let me put it another way , For each pair of given scores , Determine whether the game can achieve such a result .

Title Description

Slastyona and her loyal dog Pushok are playing a meaningless game that is indeed very interesting.

The game consists of multiple rounds.

Its rules are very simple: in each round, a natural number $k$ is chosen.

Then, the one who says (or barks) it faster than the other wins the round.

After that, the winner’s score is multiplied by $k^2$ , and the loser’s score is multiplied by $k$ .

In the beginning of the game, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of all $n$ games was recorded.

She managed to recall the final results for each games, though, but all of her memories of them are vague.

Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.

Input format

In the first string, the number of games $n$$(1<=n<=350000)$ is given.

Each game is represented by a pair of scores $a$ , $b$$(1<=a,b<=10^9)$ – the results of Slastyona and Pushok, correspondingly.

Output format

For each pair of scores, answer “Yes” if it’s possible for a game to finish with given score, and “No” otherwise.

You can output each letter in arbitrary case (upper or lower).

Examples #1

The sample input #1

6
2 4
75 45
8 8
16 16
247 994
1000000000 1000000

Sample output #1

Yes
Yes
Yes
No
No
Yes

Tips

First game might have been consisted of one round, in which the number $2$ would have been chosen and Pushok would have won.

The second game needs exactly two rounds to finish with such result: in the first one, Slastyona would have said the number $5$ , and in the second one, Pushok would have barked the number $3$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,a,b,c;
int main(){
    
	cin>>n;
	while(n--){
    
		scanf("%lld %lld",&a,&b);
		ll s=a*b;
		c=round(pow(1.0*s,1.0/3));
		if(c*c*c==s&&a%c==0&&b%c==0){
    
			puts("Yes");
		}
		else puts("No");
	}
	return 0;
}

Posterized

Topic translation

Give a set of numbers , Divide this group of numbers into consecutive groups , The number of each group shall not exceed k, All numbers in each group are assigned to the smallest number in the Group , Find the case where this group of numbers has the smallest canonical order

Title Description

Professor Ibrahim has prepared the final homework for his algorithm’s class.

He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$ -th integer represents the color of the $i$ -th pixel in the image.

The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key.

In order to preserve image details, the size of a group must not be greater than $k$ , and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right.

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.

Input format

The first line of input contains two integers $n$ and $k$ ( $1\le n\le 10^5$ , $1\le k\le 256$ ), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ( $0\le p_i\le 255$ ), where $p_i$ is the color of the $i$ -th pixel.

Output format

Print $n$ space-separated integers;

the lexicographically smallest possible array that represents the image after applying the Posterization filter.

Examples #1

The sample input #1

4 3
2 14 3 4

Sample output #1

0 12 3 3

Examples #2

The sample input #2

5 2
0 2 1 255 254

Sample output #2

0 1 1 254 254

Tips

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$ , with group key $0$ .

Color $14$ belongs to the group $[12,14]$ , with group key $12$ .

Colors $3$ and $4$ belong to group $[3,5]$ , with group key $3$ .

Other groups won’t affect the result so they are not listed here.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
int n,k,a[N],sign[N];
int main(){
    
	cin>>n>>k;
	memset(sign,-1,sizeof(sign));
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		if(sign[a[i]]==-1){
    
			int p=a[i]-k+1;
			if(p<0) p=0;
			while(sign[p]!=-1&&sign[p]!=p) p++;
			for(int j=p;j<=a[i];j++) sign[j]=p;
		}
	}
	for(int i=1;i<=n;i++){
    
		printf("%d ",sign[a[i]]);
	}
	return 0;
}

Covered Points Count

Topic translation

The main idea of the topic ：

Here you are. n Intervals , Find the number of layers covered by these intervals as $k(k<=n)$ The number of points

Input format ：

The first line is an integer ,$n$,$n<=2\ast 10^5$

following $n$ That's ok , Each line has two integers , That is, the left and right endpoints of this interval $l,r(0<=l<=r<=10^{18})$

Output format ：

$n$ It's an integer , That is, the number of points corresponding to the number of each covered layer

Title Description

You are given $n$ segments on a coordinate line; each endpoint of every segment has integer coordinates.

Some segments can degenerate to points.

Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every $k\in [1..n]$ , calculate the number of points with integer coordinates such that the number of segments that cover these points equals $k$ .

A segment with endpoints $l_i$ and $r_i$ covers point $x$ if and only if $l_i\le x\le r_i$ .

Input format

The first line of the input contains one integer $n$ ( $1\le n\le 2\cdot 10^5$ ) — the number of segments.

The next $n$ lines contain segments.

The $i$ -th line contains a pair of integers $l_i,r_i$ ( $0\le l_i\le r_i\le 10^{18}$ ) — the endpoints of the $i$ -th segment.

Output format

Print $n$ space separated integers $cn{t}_1,cn{t}_2,\dots ,cn{t}_n$ , where $cn{t}_i$ is equal to the number of points such that the number of segments that cover these points equals to $i$ .

Examples #1

The sample input #1

3
0 3
1 3
3 8

Sample output #1

6 2 1

Examples #2

The sample input #2

3
1 3
2 4
5 7

Sample output #2

5 2 0

Tips

The picture describing the first example:

Points with coordinates $[0,4,5,6,7,8]$ are covered by one segment, points $[1,2]$ are covered by two segments and point $[3]$ is covered by three segments.

The picture describing the second example:

Points $[1,4,5,6,7]$ are covered by one segment, points $[2,3]$ are covered by two segments and there are no points covered by three segments.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,k,l,r,s[N];
map<ll,ll> a;
map<ll,ll>::iterator it;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%lld %lld",&l,&r);
		a[l]++;
		a[r+1]--;
	}
	it=a.begin();
	ll x=it->first;
	ll y=it->second;
	it++;
	for(;it!=a.end();it++){
    
		s[y]+=it->first-x;
		x=it->first;
		y+=it->second;
	}
	for(int i=1;i<=n;i++){
    
		cout<<s[i]<<" ";
	}
	return 0;
}