Here are the editorials for all the problems. Hope you enjoyed them and found them interesting!
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int N = 1000;
char bus[N][5];
void printbus(int n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 5; j++)
{
cout << bus[i][j];
}
cout << '\n';
}
}
void yes()
{
cout << "YES" << '\n';
}
void no()
{
cout << "NO" << '\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 5; j++)
{
cin >> bus[i][j];
}
}
bool possible = false;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 2; j++)
{
if(bus[i][j*3] == 'O' && bus[i][j*3+1] == 'O')
{
bus[i][j*3] = '+';
bus[i][j*3+1] = '+';
possible = true;
break;
}
}
if(possible) break;
}
if(!possible)
{
no();
return 0;
}
else
{
yes();
printbus(n);
return 0;
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LG = 20;
ll a[1001][1001];
ll r[1001]; //row sum
ll c[1001]; //column sum
int n;
void no()
{
cout << -1 << '\n';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
int x, y; ll diagonal1 = 0; ll diagonal2 = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> a[i][j];
if(a[i][j] == 0)
{
x = i; y = j;
}
else
{
r[i] += a[i][j];
c[j] += a[i][j];
if(i == j)
{
diagonal1 += a[i][j];
}
if(i + j == n - 1)
{
diagonal2 += a[i][j];
}
}
}
}
if(n == 1)
{
cout << 1 << '\n';
return 0;
}
ll commonsum = r[0];
if(x == 0) commonsum = r[1];
//cout << commonsum << '\n';
ll rowsum = -1; ll colsum = -1; ll d1sum = -1; ll d2sum = -1;
for(int i = 0; i < n; i++)
{
if(i != x)
{
if(r[i] != commonsum)
{
no();
return 0;
}
}
else
{
rowsum = r[i];
}
}
for(int i = 0; i < n; i++)
{
if(i != y)
{
if(c[i] != commonsum)
{
no(); return 0;
}
}
else
{
colsum = c[i];
}
}
bool isdiagonal1 = false; bool isdiagonal2 = false;
if(x == y) isdiagonal1 = true;
if(x + y == n - 1) isdiagonal2 = true;
if(!isdiagonal1)
{
if(diagonal1 != commonsum)
{
no();
return 0;
}
}
else
{
d1sum = diagonal1;
}
if(!isdiagonal2)
{
if(diagonal2 != commonsum)
{
no();
return 0;
}
}
else
{
d2sum = diagonal2;
}
if(rowsum == colsum)
{
if(isdiagonal1 && d1sum != rowsum)
{
no();
return 0;
}
if(isdiagonal2 && d2sum != rowsum)
{
no();
return 0;
}
ll value = commonsum - rowsum;
if(value > 0)
{
cout << value << '\n';
return 0;
}
else
{
no();
return 0;
}
}
else
{
no();
return 0;
}
}
Tutorial is loading...
Code (O(nkm^2))
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int N = 101;
const int MOD = 1e9 + 7;
const ll INF = ll(1e18);
ll dp[N][N][N];
int c[N];
ll cost[N][N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
{
cin >> c[i];
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= k; j++)
{
for(int a = 0; a <= m; a++)
{
dp[i][j][a] = INF;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> cost[i][j];
}
}
if(c[1] == 0)
{
for(int i = 1; i <= m; i++)
{
dp[1][1][i] = cost[1][i];
}
}
else
{
dp[1][1][c[1]] = 0;
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
if(c[i] == 0)
{
for(int a = 1; a <= m; a++)
{
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
for(int b = 1; b <= m; b++)
{
if(b != a) dp[i][j][a] = min(dp[i][j][a], dp[i-1][j-1][b] + cost[i][a]);
}
}
}
else
{
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
for(int b = 1; b <= m; b++)
{
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
}
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
}
}
}
ll ans = INF;
for(int i = 1; i <= m; i++)
{
ans = min(ans, dp[n][k][i]);
}
if(ans >= INF) ans = -1;
cout << ans;
}
Code (O(nkm))
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int N = 101;
const int MOD = 1e9 + 7;
const ll INF = ll(1e18);
ll dp[N][N][N];
int c[N];
ll cost[N][N];
ll idx[N][N];
ll m1[N][N];
ll m2[N][N];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
{
cin >> c[i];
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= k; j++)
{
m1[i][j] = INF; m2[i][j] = INF; idx[i][j] = -1;
for(int a = 0; a <= m; a++)
{
dp[i][j][a] = INF;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> cost[i][j];
}
}
if(c[1] == 0)
{
for(int i = 1; i <= m; i++)
{
dp[1][1][i] = cost[1][i];
if(dp[1][1][i] <= m1[1][1])
{
if(dp[1][1][i] == m1[1][1])
{
idx[1][1] = -2;
}
else
{
idx[1][1] = i;
}
m2[1][1] = m1[1][1];
m1[1][1] = dp[1][1][i];
}
else if(dp[1][1][i] <= m2[1][1])
{
m2[1][1] = dp[1][1][i];
}
}
}
else
{
dp[1][1][c[1]] = 0;
m1[1][1] = 0; idx[1][1] = c[1];
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
if(c[i] == 0)
{
for(int a = 1; a <= m; a++)
{
dp[i][j][a] = min(dp[i][j][a], dp[i-1][j][a] + cost[i][a]);
ll tmp = INF;
if(a == idx[i-1][j-1])
{
tmp = m2[i-1][j-1];
}
else
{
tmp = m1[i-1][j-1];
}
dp[i][j][a] = min(dp[i][j][a], tmp + cost[i][a]);
}
}
else
{
dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j][c[i]]);
for(int b = 1; b <= m; b++)
{
if(b != c[i]) dp[i][j][c[i]] = min(dp[i][j][c[i]], dp[i-1][j-1][b]);
}
//cout << i << ' ' << j << ' ' << c[i] << ' ' << dp[i][j][c[i]] << '\n';
}
for(int a = 1; a <= m; a++)
{
if(dp[i][j][a] <= m1[i][j])
{
if(dp[i][j][a] == m1[i][j])
{
idx[i][j] = -2;
}
else
{
idx[i][j] = a;
}
m2[i][j] = m1[i][j];
m1[i][j] = dp[i][j][a];
}
else if(dp[i][j][a] <= m2[i][j])
{
m2[i][j] = dp[i][j][a];
}
}
}
}
ll ans = INF;
for(int i = 1; i <= m; i++)
{
ans = min(ans, dp[n][k][i]);
}
if(ans >= INF) ans = -1;
cout << ans;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int N = 1e6 + 3;
int a[N];
int visited[N];
ll ans;
vector<int> cycles;
ll dp[N];
int cyclecnt;
void dfs2(int u)
{
cycles[cyclecnt]++;
visited[u] = 3;
if(visited[a[u]] == 3) return ;
dfs2(a[u]);
}
void dfs(int u)
{
visited[u] = 2;
if(visited[a[u]] == 0)
{
dfs(a[u]);
}
else if(visited[a[u]] == 1)
{
visited[u] = 1;
return ;
}
else
{
cycles.pb(0);
dfs2(u);
cyclecnt++;
}
visited[u] = 1;
}
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0);
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
dp[i] = (dp[i-1]*2LL)%MOD;
}
ans = 1;
memset(visited, 0, sizeof(visited));
for(int i = 1; i <= n; i++)
{
if(visited[i] == 0)
{
dfs(i);
}
}
ll cnt = n;
for(int i = 0; i < cycles.size(); i++)
{
cnt -= cycles[i];
ans = (ans*(dp[cycles[i]]-2+MOD))%MOD;
}
ans = (ans*dp[cnt])%MOD;
if(ans < 0) ans += MOD;
int ans2 = ans;
printf("%d\n", ans2);
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MOD = 1e6 + 3;
ll power(ll base, ll exp)
{
ll ans = 1;
while(exp)
{
if(exp&1) ans = (ans*base)%MOD;
base = (base*base)%MOD;
exp>>=1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
ll n, k;
cin >> n >> k;
if(n <= 63 && k > (1LL<<n))
{
cout << 1 << " " << 1;
return 0;
}
ll v2 = 0;
int digits = __builtin_popcountll(k - 1);
v2 = k - 1 - digits;
ll ntmp = n % (MOD - 1);
if(ntmp < 0) ntmp += (MOD - 1);
ll ktmp = k % (MOD - 1);
if(ktmp < 0) ktmp += (MOD - 1);
ll v2tmp = v2 % (MOD - 1);
if(v2tmp < 0) v2tmp += (MOD - 1);
ll exponent = ntmp*(ktmp - 1) - v2tmp;
exponent %= (MOD - 1);
if(exponent < 0) exponent += MOD - 1;
ll denom = power(2, exponent);
ll numpart = 0;
if(k - 1 >= MOD)
{
numpart = 0;
}
else
{
ll prod = 1;
ll ntmp2 = power(2, ntmp);
prod = power(2, v2tmp);
prod = power(prod, MOD - 2);
if(prod < 0) prod += MOD;
for(ll y = 1; y <= k - 1; y++)
{
prod = (prod * (ntmp2 - y))%MOD;
}
numpart = prod;
}
ll num = (denom - numpart)%MOD;
num %= MOD; denom %= MOD;
if(num < 0) num += MOD;
if(denom < 0) denom += MOD;
cout << num << " " << denom;
return 0;
}
