Hello everyone :)
This is the editorial of the second contest of Training contests ! Here's the first training contest, And here's the second one.
Sorry for being late we were so busy these days and couldn't prepare the editorial fast :( Hope now you enjoy the editorial and please write down your opinion about the problems, Thanks :D.
If there is an even element in array there is an answer consisting of only it. Otherwise if there is at least two odd elements in array there is an answer consisting of this two elements. Otherwise array is only one odd element and there is no answer.
Write the code yourself ;)
First of all use a map to store the occurrence of numbers, then iterate over the given array and if the current number is $$$a[i]$$$ check if $$$x$$$ — $$$a[i]$$$ is represent in the array and also notice that the index of $$$a[i]$$$ and $$$x$$$ — $$$a[i]$$$ is not the same!
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
map <int, int> cnt;
int n, x;
const int maxn = 2e5 + 10;
int a[maxn];
void solve (){
cin >> n >> x;
for (int i = 0; i < n; i++){
cin >> a[i];
cnt[a[i]] ++;
}
int idx1 = -1, idx2 = -1;
for (int i = 0; i < n; i++){
if (cnt[a[i]] != 0 && cnt[x - a[i]] != 0){
for (int j = 0; j < n; j++){
if (a[j] == a[i]){
idx1 = j;
break;
}
}
for (int j = 0; j < n; j++){
if (a[j] == (x - a[i]) && j != idx1){
idx2 = j;
break;
}
}
if (idx1 != -1 && idx2 != -1) break;
}
}
if (idx1 != -1 && idx2 != -1){
cout << idx1 + 1 << ' ' << idx2 + 1;
return;
}
cout << "-1";
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Let's sort the array. Let $$$cur$$$ = 1. Then walk through the array. Let's look at current number. If it is greater or equal to $$$cur$$$, then let's increase $$$cur$$$ by 1. Answer is $$$cur$$$.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of Allah |
* ────────────── •✵•✵• ──────────────
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#define pb push_back
#define pbb pop_back
#define rev reverse
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main (){
ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
sort (a, a + n);
int ans = 1;
for (int i = 0; i < n; i++){
if (a[i] >= ans){
ans ++;
}
}
cout << ans;
return 0;
}
/* Thanks Allah */
This problem can be solved easily with dynamic programming.
The answer would always be the count of non-positive numbers in the segment $$$arr[k + 1, n]$$$ + count of the non-negative numbers in the segment $$$arr[1, k]$$$ where $$$1$$$ <= $$$k$$$ < $$$n$$$. All we have to do is to keep track of the occurrences of negative and positive integers till i'th index.
Let's denote the count of negative numbers by $$$neg[1...n]$$$ and $$$pos[1...n]$$$ for positive numbers count. So, the count of non-negative numbers in the segment $$$arr[1, i]$$$ = $$$i$$$ — $$$neg[i]$$$. Similarly, the count of non-positive numbers in the segment $$$arr[i + 1, n]$$$ = $$$n$$$ — $$$i$$$ — $$$pos[n]$$$ + $$$pos[i]$$$.
At last the answer would be min($$$n$$$ — $$$neg[i]$$$ — $$$pos[n]$$$ + $$$pos[i]$$$) for $$$1$$$ <= $$$i$$$ < $$$n$$$.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 1e5 + 10;
int dp[maxn], pos[maxn], neg[maxn];
int n, t[maxn];
void solve (){
cin >> n;
for (int i = 1; i <= n; i ++){
cin >> t[i];
}
pos[0] = 0, neg[0] = 0;
for (int i = 1; i <= n; i ++){
if (t[i] > 0){
pos[i] = pos[i - 1] + 1;
neg[i] = neg[i - 1];
}
else if (t[i] < 0){
pos[i] = pos[i - 1];
neg[i] = neg[i - 1] + 1;
}
else {
pos[i] = pos[i - 1];
neg[i] = neg[i - 1];
}
}
int ans = INT_MAX;
for (int i = 1; i < n; i ++){
ans = min(ans, (n - neg[i] - pos[n] + pos[i]));
}
cout << ans;
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Let's first think about what $$$S$$$ < $$$T$$$ can tell us: suppose $$$S$$$ $$$=$$$ $$$abcxyz$$$ and $$$T$$$ = $$$abcuv$$$. Then we know that $$$S$$$ < $$$T$$$ if and only if $$$x$$$ < $$$u$$$ by the definition.
So we can transform the conditions $$$name1$$$ < $$$name2$$$, $$$name2$$$ < $$$name3$$$ ... into the order of letters.
Then the question become: do we have a permutation that satisfy those conditions. It is actually the classic topological order question.
One trick in this task is that, if we have something like $$$xy$$$ < $$$x$$$ then there is no solution :).
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 1e6 + 10;
int cnt[maxn];
string s[maxn];
vector <int> alphabet, adj[maxn];
bool mark[maxn];
bool check(bool f, int a, int b){
return (f == 0 && a > b);
}
bool check2(){
for (int i = 0; i < 26; i ++){
if (!mark[i]){
return 0;
}
}
return 1;
}
void dfs(){
for (int i = 0; i < 26; i ++){
for (int j = 0; j < 26; j ++){
if (!mark[j] && !cnt[j]){
mark[j] = 1, alphabet.pb(j);
for (auto x : adj[j]){
cnt[x] --;
}
}
}
}
}
void solve (){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> s[i];
}
for (int i = 0; i < n - 1; i++){
bool tom = 0;
for (int j = 0; j < min(si(s[i]), si(s[i + 1])); j++){
if (s[i + 1][j] != s[i][j]){
int u, v;
u = s[i][j] - 'a', v = s[i + 1][j] - 'a';
adj[u].pb(v), cnt[v] ++, tom = 1;
break;
}
}
if (check(tom, si(s[i]), si(s[i + 1]))){
cout << "Impossible";
return;
}
}
dfs();
if (!check2()){
cerr << ":| ";
cout << "Impossible";
return;
}
for (auto x : alphabet){
cout << char('a' + x);
}
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
F.AHF and Number of Palindromes :
Note: Strings and arrays are considered 0-based in the following solution.
Let $$$isPal[i][j]$$$ be 1 if $$$s[i...j]$$$ is palindrome, otherwise, set it 0. Let's define $$$dp[i][j]$$$ to be number of palindrome substrings of $$$s[i...j]$$$. Let's calculate $$$isPal[i][j]$$$ and $$$dp[i][j]$$$ in $$$O(|S|^{2})$$$. First, initialize $$$isPal[i][i]$$$ = 1 and $$$dp[i][i]$$$ = 1. After that, loop over $$$len$$$ which states length of substring and for each specific $$$len$$$, loop over start which states starting position of substring. $isPal$[start][start + len - 1] can be easily calculated by the following formula:
$$$isPal[start][start+len-1]$$$ = $$$isPal[start+1][start+len-2]$$$ & $$$(s[start] == s[start+len-1])$$$ After that, $$$dp[start][start + len - 1]$$$ can be calculated by the following formula which is derived from Inc-Exc Principle.
$$$dp[start][start+len-1]$$$ = $$$dp[start][start+len-2]$$$ + $$$dp[start+1][start+len-1]$$$ — $$$dp[start+1][start+len-2]$$$ + $$$isPal[start][start+len-1]$$$ After preprocessing, we get queries $$$li$$$ and $$$ri$$$ and output $$$dp[li - 1][ri - 1]$$$. Overall complexity is $$$O(|S|^{2})$$$.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 5e3 + 10;
string s;
bool IsPal[maxn][maxn];
int Query[maxn][maxn], n, q;
void Build (){
for (int i = 0; i < n; i ++){
IsPal[i][i] = 1;
}
for (int i = n - 1; i >= 0; i --){
for (int j = i + 1; j < n; j ++){
IsPal[i][j] = ((s[i] == s[j]) && (j == i + 1 || IsPal[i + 1][j - 1]));
}
}
}
void solve (){
cin >> s;
n = si(s);
Build();
for (int i = 0; i < n; i ++){
Query[i][i] = 1;
}
for (int i = n - 1; i >= 0; i --){
for (int j = i + 1; j < n; j ++){
Query[i][j] = Query[i + 1][j] + Query[i][j - 1] - Query[i + 1][j - 1] + IsPal[i][j];
}
}
cin >> q;
for (int i = 0; i < q; i ++){
int l, r;
cin >> l >> r;
cout << Query[l - 1][r - 1] << '\n';
}
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Since $$${1, 1 ..., 1}$$$ is a pairwise coprime sequence, the maximum element of bi can never greater then $$$2mx$$$ - $$$1$$$. Here mx is the maximum elements in $$$a[i]$$$. So what we need consider is the first a few prime factors. It is not hard to use $$$bitmask-dp$$$ to solve this:
for (int i = 1 ; i <= n ; i ++) {
for (int k = 1 ; k < 60 ; k ++) {
int x = (~fact[k]) & ((1 << 17) - 1);
for (int s = x ; ; s = (s - 1) & x) {
if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
}
if (s == 0) break;
}
}
}
Here $$$dp[i][s]$$$: means the first $$$i$$$ items of the sequence, and the prime factor have already existed. And $$$fact[k]$$$ ： means the prime factor set of number $$$k$$$.
Here's a complete editorial for this problem.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 1e2 + 10;
int Primes[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int Fmask[60], dp[maxn][1 << 16], a[maxn], b[maxn][1 << 16];
void Generate_Sets () {
for (int i = 1; i <= 58; i ++) {
Fmask[i] = 0;
for (int j = 0; j < 16; j ++) {
if (i % Primes[j] == 0) {
Fmask[i] |= (1 << j);
}
}
}
}
void solve () {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
Generate_Sets();
int Max = (1 << 16) - 1;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j < (1 << 16); j ++) {
dp[i][j] = INT_MAX;
for (int z = 1; z <= 58; z ++) {
if ((j & (Fmask[z])) == Fmask[z]) {
int kom = dp[i - 1][(j ^ Fmask[z])] + abs(a[i] - z);
if (kom < dp[i][j]) {
b[i][j] = z;
dp[i][j] = kom;
}
}
}
}
}
vector <int> B;
int mask = Max;
for (int i = n; i >= 1; i --) {
B.pb(b[i][mask]);
mask ^= Fmask[b[i][mask]];
}
for (int i = n - 1; i >= 0; i --) {
cout << B[i] << ' ';
}
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Let's reformulate the solution to the form of dynamic programming.
$$$dp[n]$$$ — the number of ways to split the gems so that the total amount of space taken is n.
Then there are obvious transitions of either splitting the last gem or not. $$$dp[n]$$$ $$$=$$$ $$$dp[n − m]$$$ + $$$dp[n − 1]$$$.
And that can be easily rewritten in such a way that matrix exponentiation becomes the solution.
Overall complexity: $$$O(m^{3}⋅ logn)$$$.
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define bolt ios::sync_with_stdio(0)
#define light cin.tie(0);cout.tie(0)
#define forr(i,p,n) for(ll i=p;i<n;i++)
#define MAXN 1000003
typedef long long ll;
using namespace std;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
ll bin[103][103];
void mult_mat(ll m, ll ans[][100], ll bin[][100]){
ll mult[m][m];
forr(i,0,m){
forr(j,0,m){
mult[i][j]=0;
forr(k,0,m){
mult[i][j]+=ans[i][k]*bin[k][j];
if(mult[i][j]>=MOD){
mult[i][j]%=MOD;
}
}
}
}
forr(i,0,m){
forr(j,0,m){
ans[i][j]=mult[i][j];
}
}
}
void pow_mat(ll n, ll fin[][100], ll m){
ll ans[m][100];
ll b[m][100];
forr(i,0,m){
forr(j,0,m){
ans[i][j]=bin[i][j];
b[i][j]=bin[i][j];
}
}
n--;
while(n>0){
if(n%2==1){
mult_mat(m,ans,b);
n--;
}else{
n=n/2;
mult_mat(m,b,b);
}
}
forr(i,0,m){
forr(j,0,m){
fin[i][j]=ans[i][j];
}
}
}
int main(){
bolt;
ll n,m;
cin>>n>>m;
bin[0][0]=1;
bin[0][m-1]=1;
for(ll i=1;i<m;i++){
bin[i][i-1]=1;
}
if(n<m){
cout<<1<<"\n";
}else{
ll fin[m+1][100];
pow_mat(n-m+1,fin,m);
ll ans=0;
forr(i,0,m){
ans+=fin[0][i];
if(ans>=MOD){
ans-=MOD;
}
}
cout<<ans<<"\n";
}
}
