We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments.
1777A - Everybody Likes Good Arrays!
Idea: ShivanshJ
Preparation: ShivanshJ
Editorialist: ShivanshJ
Try to make the problem simpler.
Parity?
Try replacing even numbers with $$$0$$$ and odd numbers with $$$1$$$ in other words consider all numbers modulo $$$2$$$.
Think harder! It works!
/* Enjoying CP as always!*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--) {
//Take input
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) {
cin>>a[i];
}
//initialize answer..
int ans=0;
for(int i=0;i+1<n;i++) {
ans+=(!((a[i]^a[i+1])&1));
/*XOR the two numbers and check 0th bit in the resultant, if it is 1
then, numbers are of different parity, otherwise both are of same parity*/
}
cout<<ans<<"\n";
}
return 0;
}
def main():
T = int(input())
while T > 0:
T = T - 1
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(1, n):
ans += 1 - ((a[i] + a[i - 1]) & 1)
print(ans)
if __name__ == '__main__':
main()
Idea: TimeWarp101 quantau
Preparation: TimeWarp101
Editorialist: TimeWarp101
Will the answer differ for different permutations?
If you only look at 2 elements, how much will they contribute to the answer?
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
vector<int> fact(N);
fact[0] = 1;
for(int i = 1; i < N; i++)
{
fact[i] = fact[i - 1] * i;
fact[i] %= mod;
}
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int ans = n * (n - 1);
ans %= mod;
ans = (ans * fact[n]) % mod;
cout << ans << endl;
}
return 0;
}
t = int(input())
for _ in range(t):
n = int(input())
nf = 1
mod = int(1e9 + 7)
for i in range(n):
nf = nf * (i + 1)
nf %= mod
ans = n * (n - 1) * nf
ans %= mod
print(ans)
Idea: quantau
Preparation: TimeWarp101 quantau
Editorialist: TimeWarp101
Would sorting the array help?
Would iterating over the factors help?
If the optimal team has students with maximum smartness $$$M$$$ and minimum smartness $$$m$$$, would having students with smartness $$$X$$$ such that $$$m \le X \le M$$$ the answer will not change.
Two pointers?
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define var(x, y, z) cout << x << " " << y << " " << z << endl;
#define ll long long int
#define pii pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define FASTIO \
ios ::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const ll inf = 1e17;
const ll MAXM = 1e5;
vector<ll> factors[MAXM + 5];
void init()
{
for (ll i = 1; i <= MAXM; i++)
{
for (ll j = i; j <= MAXM; j += i)
{
factors[j].pb(i);
}
}
}
void solve()
{
ll n, m;
cin >> n >> m;
vector<pii> vec;
for (ll i = 0; i < n; i++)
{
ll value;
cin >> value;
vec.pb({value, i});
}
sort(all(vec));
vector<ll> frequency(m + 5, 0);
ll curr_count = 0;
ll j = 0;
ll global_ans = inf;
for (ll i = 0; i < n; i++)
{
for (auto x : factors[vec[i].ff])
{
if (x > m)
break;
if (!frequency[x]++)
{
curr_count++;
}
}
while (curr_count == m)
{
ll curr_ans = vec[i].ff - vec[j].ff;
if (curr_ans < global_ans)
{
global_ans = curr_ans;
}
for (auto x : factors[vec[j].ff])
{
if (x > m)
break;
if (--frequency[x] == 0)
{
curr_count--;
}
}
j++;
}
}
cout << (global_ans >= inf ? -1 : global_ans) << "\n";
}
int main()
{
FASTIO
init();
ll t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Idea: AwakeAnay
Preparation: mayankfrost ShivanshJ
Editorialist: AwakeAnay
What would be the value of a node at time $$$t$$$?
The value of a node $$$u$$$ after time $$$t$$$ would be the xor of the initial values of all nodes in the subtree of $$$u$$$ which are at a distance $$$t$$$ from $$$u$$$.
What is the expected value of xor of $$$k$$$ boolean values?
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
long long power(long long a, int b)
{
long long ans = 1;
while (b)
{
if (b & 1)
{
ans *= a;
ans %= MOD;
}
a *= a;
a %= MOD;
b >>= 1;
}
return ans;
}
int DFS(int v, vector<int> edges[], int p, int dep, int ped[])
{
int mdep = dep;
for (auto it : edges[v])
if (it != p)
mdep = max(DFS(it, edges, v, dep + 1, ped), mdep);
ped[v] = mdep - dep + 1;
return mdep;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T, i, j, n, u, v;
cin >> T;
while (T--)
{
cin >> n;
vector<int> edges[n];
for (i = 0; i < n - 1; i++)
{
cin >> u >> v;
u--, v--;
edges[u].push_back(v);
edges[v].push_back(u);
}
int ped[n];
DFS(0, edges, 0, 0, ped);
long long p = power(2, n - 1), ans = 0;
for (i = 0; i < n; i++)
{
ans += p * ped[i] % MOD;
ans %= MOD;
}
cout << ans << "\n";
}
}
Idea: Crocuta
Preparation: mayankfrost
Editorialist: mayankfrost
If the cost is c, all edges with weight less than or equal to c are reversible.
If an edge can be reversed, can it be treated as bidirectional?
Let there exist a set of possible starting nodes. If this set is non empty, the highest node h in the topological ordering of nodes will always be present in the set. Think why.
#include <bits/stdc++.h>
using namespace std;
// Using Kosa Raju, we guarantee the topmost element (indicated by root) of stack is from the root SCC
void DFS(int v, bool visited[], int &root, vector<int> edges[])
{
visited[v] = true;
for (auto it : edges[v])
if (!visited[it])
DFS(it, visited, root, edges);
root = v;
}
int cnt(int v, bool visited[], vector<int> edges[])
{
int ans = 1;
visited[v] = true;
for (auto it : edges[v])
if (!visited[it])
ans += cnt(it, visited, edges);
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while (T--)
{
int i, j, n, m, u, v, w;
cin >> n >> m;
vector<pair<int, int>> og_edges[n];
for (i = 0; i < m; i++)
{
cin >> u >> v >> w;
u--, v--;
og_edges[u].push_back({v, w});
}
int l = -1, r = 1e9 + 1, mid;
while (r - l > 1)
{
mid = l + (r - l) / 2;
vector<int> edges[n];
for (i = 0; i < n; i++)
{
for (auto it : og_edges[i])
{
edges[i].push_back(it.first);
if (it.second <= mid)
edges[it.first].push_back(i);
}
}
bool visited[n] = {};
int root;
for (i = 0; i < n; i++)
{
if (!visited[i])
DFS(i, visited, root, edges);
}
memset(visited, false, sizeof(visited));
if (cnt(root, visited, edges) == n)
r = mid;
else
l = mid;
}
if (r == 1e9 + 1)
r = -1;
cout << r << '\n';
}
return 0;
}
Idea: Crocuta
Preparation: TimeWarp101
Editorialist: Crocuta
Can we somehow fix the maximum element ?
To calculate the answer over all subarrays with the same maximum element, can we use the trie trick for calculating the maximum xor.
#include <bits/stdc++.h>
using namespace std;
struct Trie{
struct Trie *child[2]={0};
};
typedef struct Trie trie;
void insert(trie *dic, int x)
{
trie *temp = dic;
for(int i=30;i>=0;i--)
{
int curr = x>>i&1;
if(temp->child[curr])
temp = temp->child[curr];
else
{
temp->child[curr] = new trie;
temp = temp->child[curr];
}
}
}
int find_greatest(trie *dic, int x) {
int res = 0;
trie *temp = dic;
for(int i=30;i>=0;i--) {
int curr = x>>i&1;
if(temp->child[curr^1]) {
res ^= 1<<i;
temp = temp->child[curr^1];
}
else {
temp = temp->child[curr];
}
}
return res;
}
int main() {
int test_cases;
cin >> test_cases;
while(test_cases--)
{
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) {
cin>>a[i];
}
trie *t[n+2];
int prexor[n+1];
prexor[0] = 0;
for(int i=1;i<=n;i++) {
t[i] = new trie;
insert(t[i], prexor[i-1]);
prexor[i] = prexor[i-1]^a[i];
}
t[n+1] = new trie;
insert(t[n+1], prexor[n]);
pair<int,int> asc[n+1];
for(int i=1;i<=n;i++) {
asc[i] = make_pair(a[i],i);
}
sort(asc+1,asc+n+1);
int left[n+1], right[n+1];
stack<int> s;
for(int i=1;i<=n;i++) {
while(!s.empty() && a[i]>=a[s.top()])
s.pop();
if(s.empty())
left[i] = 0;
else
left[i] = s.top();
s.push(i);
}
while(!s.empty())
s.pop();
for(int i=n;i>0;i--) {
while(!s.empty() && a[i]>a[s.top()])
s.pop();
if(s.empty())
right[i] = n+1;
else
right[i] = s.top();
s.push(i);
}
int ans = 0;
for(int i=1;i<=n;i++) {
int x = asc[i].second;
int r = right[x]-1;
int l = left[x]+1;
if(x-l < r-x) {
for(int j=l-1;j<x;j++) {
ans = max(ans, find_greatest(t[x+1], prexor[j]^a[x]));
}
t[l] = t[x+1];
for(int j=l-1;j<x;j++) {
insert(t[l], prexor[j]);
}
}
else {
for(int j=x;j<=r;j++) {
ans = max(ans, find_greatest(t[l], prexor[j]^a[x]));
}
for(int j=x;j<=r;j++) {
insert(t[l], prexor[j]);
}
}
}
cout<<ans << endl;
}
}
