Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
x = 0
c = 1
while -n <= x <= n:
if c % 2 == 1:
x -= 2 * c - 1
else:
x += 2 * c - 1
c += 1
if c % 2 == 0:
print("Sakurako")
else:
print("Kosuke")
for tc in range(int(input())):
solve()
Idea: FBI
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
mn = dict()
for i in range(n):
a = [int(x) for x in input().split()]
for j in range(n):
mn[i - j] = min(a[j], mn.get(i - j, 0))
ans = 0
for value in mn.values():
ans -= value
print(ans)
t = int(input())
for _ in range(t):
solve()
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n/2-1;i>=1;i--){
if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){
swap(a[i],a[n-i+1]);
}
}
int re=0;
for(int i=1;i<n;i++){
re+=(a[i]==a[i+1]);
}
cout<<re<<endl;
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
map<int,int>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int p_su[n+1];
p_su[0]=0;
int lst[n+1];
mp[0]=0;
for(int i=1;i<=n;i++){
p_su[i]=p_su[i-1]+a[i];
if(mp.find(p_su[i])==mp.end()){
lst[i]=-1;
}
else{
lst[i]=mp[p_su[i]];
}
mp[p_su[i]]=i;
}
int dp[n+1];
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++){
dp[i]=max(dp[i],dp[i-1]);
if(lst[i]!=-1){
dp[i]=max(dp[i],dp[lst[i]]+1);
}
}
cout<<*max_element(dp,dp+n+1)<<endl;
}
}
2033E - Sakurako, Kosuke, and the Permutation
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
cin>>t;
while(t--){
int n;
cin>>n;
int p[n+1];
for(int i=1;i<=n;i++){
cin>>p[i];
}
bool us[n+1];
memset(us,0,sizeof us);
int re=0;
for(int i=1;i<=n;i++){
if(!us[i]){
int cu=i;
int le=0;
while(us[cu]==0){
le++;
us[cu]=1;
cu=p[cu];
}
re+=(le-1)/2;
}
}
cout<<re<<'\n';
}
}
Idea: FBI
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define ssize(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const LL MOD = 1e9 + 7;
int bp(int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 0)
return bp(1LL * a * a % MOD, n / 2);
else
return 1LL * bp(a, n - 1) * a % MOD;
}
int inv(int a) {
return bp(a, MOD - 2);
}
void solve() {
LL n, k;
cin >> n >> k;
n %= MOD;
if (k == 1) {
cout << n << "\n";
return;
}
vector<int> fib(3);
fib[0] = fib[1] = 1;
int cnt = 0;
for (int i = 2; i <= 10 * k; i++) {
fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k;
if (fib[i % 3] == 0)
cnt++;
if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) {
cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n";
return;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){
maxd[v] = {0, 0};
if (v != p) h[v] = h[p] + 1;
for(int u: sl[v]){
if (u == p) continue;
precalc(u, v, sl, maxd, h);
if (maxd[v].y < maxd[u].x + 1) {
maxd[v].y = maxd[u].x + 1;
}
if (maxd[v].y > maxd[v].x) {
swap(maxd[v].x, maxd[v].y);
}
}
}
void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
binup[v][0] = {maxd[p].x, p};
if (maxd[p].x == maxd[v].x + 1) {
binup[v][0].x = maxd[p].y;
}
binup[v][0].x -= h[p];
for(int i = 1; i < 20; ++i){
binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y;
binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x);
}
for(int u: sl[v]){
if (u == p) continue;
calc_binups(u, v, sl, binup, maxd, h);
}
}
int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
k = min(k, h[v]);
int res = maxd[v].x - h[v];
int ini = h[v];
for(int i = 19; i >= 0; --i){
if ((1 << i) <= k) {
res = max(res, binup[v][i].x);
v = binup[v][i].y;
k -= (1 << i);
}
}
return res + ini;
}
void solve(int tc){
int n;
cin >> n;
vector<vector<int>> sl(n);
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
vector<pair<int, int>> maxd(n);
vector<int> h(n);
precalc(0, 0, sl, maxd, h);
vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20));
calc_binups(0, 0, sl, binup, maxd, h);
int q;
cin >> q;
for(int _ = 0; _ < q; ++_){
int v, k;
cin >> v >> k;
cout << get_ans(v - 1, k, binup, maxd, h) << " ";
}
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
awesome contest!
Bro I sent F two seconds before the end of the round and it got Compilation Error in C++17 but when I sent it with C++20 1 minute after the end of the round it got OK. I'm literally unluckiest participant of this round.
my rating change is showing up as 0 wtf? is this possible?
Yeah, this is possible. This just means that:
1) your performance wasnt' good enough for your rating to increase!
2) your performance wasnt' bad enough for your rating to decrease!
I noticed that except D, all problems that involve "Kosuke" refer to "Kosuke" as "Kosuke" but D refers to "Kosuke" as "Ko'U'suke".
This means nothing of course, just a funny observation.
upper bound for the first appearance of $$$0$$$ on problem F is actually bounded by 2 * k.
https://jonkagstrom.com/articles/upper_bound_of_fibonacci_entry_points.pdf
I feel like proving that we don't miss any numbers divisible by k would be a nice touch. Proof: Let Fi be the first number divisible by k. Fm exists such that m>i, and m!=ni, n in the set of integers. Let us prove that it is not divisible by k. gcd(Fi,Fm) = F(gcd(i,m)). The gcd must be <= i since, i is less than m. Also, the gcd is not equal to i since m is not divisible by i. Thus, F(gcd(i,m)) is an element of the set of Fz, 0<=z<i. By premise, these numbers are not divisible by k, thus since the gcd of Fm and Fi is less than k, and Fi is divisible by k, Fm is not divisible by k. QED.
p.s: idk latex but someone can make this into latex and i will edit if anyone feels like it
Implementation for problem F...
There are some things that I have discussed and discovered after the contest for understanding F. The following points are in context of a fibonacci sequence mod $$$k$$$, where $$$k \geq 2$$$. Pisano period refers to the period of such a sequence.
The period is bounded by $$$6k$$$.
The zeros of fibonacci mod $$$k$$$ are evenly spaced as proved here thanks to Dominater069 and observed to first occur no later than $$$2k$$$ as mentioned here.
The Pisano period is either 1, 2 or 4 times the period of its zero. It is mentioned in wikipedia that "The number of occurrences of 0 per cycle is 1, 2, or 4." and since we have established that the all the zeros are evenly spaced, it implies that the Pisano period is either 1, 2 or 4 times the period of the zeros.
4th question can also be done by using map.
storing the prefix sum in map and making a counter variable . if current element sum matches map then increment the counter and delete the map. do this iteration for whole array.
at the end cout counter.