Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each ...
Codeforces Round 745 Div 2 Editorial Solutions A-C
CQXYM Count Permutations
CQXYM is counting permutations length of
A permutation is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation ( appears twice in the array) and is also not a permutation ( but there is in the array).
A permutation (length of ) will be counted only if the number of satisfying is no less than . For example:
- Permutation will count, because the number of such that equals (, , ).
- Permutation won't count, because the number of such that equals ().
CQXYM wants you to help him to count the number of such permutations modulo ().
In addition, modulo operation is to get the remainder. For example:
- , because ,
- , because .
Program Code
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--){
int n;
cin>>n;
ll p=n,ans=1;
n=n*2;
for(int i=1;i<n;i++){
ans=(i*ans)%mod;
}
cout<<(p*ans)%mod<<'\n';
}
return 0;
}
Diameter of Graph
CQXYM wants to create a connected undirected graph with nodes and edges, and the diameter of the graph must be strictly less than . Also, CQXYM doesn't want a graph that contains self-loops or multiple edges (i.e. each edge connects two different vertices and between each pair of vertices there is at most one edge).
The diameter of a graph is the maximum distance between any two nodes.
The distance between two nodes is the minimum number of the edges on the path which endpoints are the two nodes.
CQXYM wonders whether it is possible to create such a graph.
Input
The input consists of multiple test cases.
The first line contains an integer — the number of test cases. The description of the test cases follows.
Only one line of each test case contains three integers , ,
Output
For each test case, print YES if it is possible to create the graph, or print NO if it is impossible. You can print each letter in any case (upper or lower).
Example
input
Copy
5 1 0 3 4 5 3 4 6 3 5 4 1 2 1 1
output
Copy
YES NO YES NO NO
Program Code
#include <iostream>
using namespace std;
long long t, n, m, k, a, b, c;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> t; while (t--) {
cin >> n >> m >> k;
if (n == 1) {
if (!m && k > 1) cout << "YES\n";
else cout << "NO\n";
continue;
}
a = n - 1; b = n * (n - 1) / 2;
if (a > m) {
cout << "NO\n";
}
else if (b > m) {
if (k < 4) cout << "NO\n";
else cout << "YES\n";
}
else if (b == m) {
if (k < 3)cout << "NO\n";
else cout << "YES\n";
}
else cout << "NO\n";
}
}
Portal
CQXYM found a rectangle of size There are rows and columns of blocks. Each block of the rectangle is an obsidian block or empty. CQXYM can change an obsidian block to an empty block or an empty block to an obsidian block in one operation.
A rectangle size of is called a portal if and only if it satisfies the following conditions:
- .
- For all , blocks and are obsidian blocks.
- For all , blocks and are obsidian blocks.
- For all , block is an empty block.
- can be any type.
Note that corners can be any type
CQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.
Input
The first line contains an integer (), which is the number of test cases.
For each test case, the first line contains two integers and ( .
Then lines follow, each line contains characters or . If the -th character of -th line is , block is an empty block. Otherwise, block is an obsidian block.
It is guaranteed that the sum of over all test cases does not exceed .
It is guaranteed that the sum of over all test cases does not exceed .
Output
Output answers, and each answer in a line.
Examples
input
Copy
1 5 4 1000 0000 0110 0000 0001
output
Copy
12
input
Copy
1 9 9 001010001 101110100 000010011 100000001 101010101 110001111 000001111 111100000 000110000
output
Copy
5
Program Code
#include <bits/stdc++.h>
using namespace std;
const int MAX = 405;
int a[MAX][MAX], sum[MAX][MAX], n, m;
int calc(int i, int j, int ii, int jj) {
return sum[ii][jj] - sum[ii][j - 1] - sum[i - 1][jj] + sum[i - 1][j - 1];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= m; j++) {
a[i][j] = s[j - 1] - '0';
sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
int ans = 18;
for (int i = 1; i + 5 - 1 <= n; i++) {
for (int j = 1; j + 4 - 1 <= m; j++) {
for (int ii = i + 5 - 1; ii <= n; ii++) {
bool flag = true;
for (int jj = j + 4 - 1; jj <= m && flag; jj++) {
int w = jj - j + 1;
int h = ii - i + 1;
int cnt1 = w - 2 - calc(i, j + 1, i, jj - 1);
int cnt2 = h - 2 - calc(i + 1, j, ii - 1, j);
int cnt3 = calc(i + 1, j + 1, ii - 1, jj - 1);
int cnt4 = w - 2 - calc(ii, j + 1, ii, jj - 1);
int cnt5 = h - 2 - calc(i + 1, jj, ii - 1, jj);
if (ans > cnt1 + cnt2 + cnt3 + cnt4 + cnt5) {
ans = cnt1 + cnt2 + cnt3 + cnt4 + cnt5;
} else if (ans < cnt1 + cnt2 + cnt3 + cnt4) {
flag = false;
}
}
}
}
}
cout << ans << "\n";
}
return 0;
}
More about Codeforces Round 745 Div 2
Codeforces organizes many contests out of which one is this Codeforces rounds to improve coding skills and get a higher coding knowledge. Codeforces Round 745 Div 2 was too a great round to test our coding skills. This round was held on Thursday, September 30, 2021 at 15:45UTC+5.5. This round will be rated for coders with rating upto 2100. A total of 6 problems are given which needs to be solved in 2 hours 15 minutes.
The first problem that is CQXYM Count Permutations was cakewalk it was so simple that in 5 minutes we had more that four thousand successful submissions. Problem B was too a great deal of simplicity but it took a bit of time to understand what to do in the problem. Problem C was medium level and was a good question of logic for the average coders and for best coders it was just too simple. Problem D was good to go but the question was quite difficult to guess what algorithm would be required. Problem E1 was quite simple and many successful submissions were made. Problem E2 and F were the testing the skills of top coders and average coders just kept guessing what algorithms to use.
The contest was a great success and every body enjoyed it truly. Just practice more questions and go ahead in building a streak of code and get better everyday. Happy coding journey ahead.
Comments
Post a Comment