Blog entries - Codeforces

Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

→ Pay attention

Before contest
Codeforces Round 941 (Div. 1)
3 days
Register now »

*has extra registration

Before contest
Codeforces Round 941 (Div. 2)
3 days
Register now »

*has extra registration

→ Streams

CodeChef Starters 131 Solution Discussion

By aryanc403

Before stream 09:45:43

View all →

→ Top rated

#	User	Rating
1	jiangly	3640
2	Benq	3593
3	tourist	3572
4	orzdevinwang	3561
5	cnnfls_csy	3539
6	ecnerwala	3534
7	Radewoosh	3532
8	gyh20	3447
9	Rebelz	3409
10	Geothermal	3408

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

YocyCraft's blog

First time becoming red

By YocyCraft, history, 12 months ago, In English

In English

In yesterday's contest Codeforces Round 865 (Div. 1) I've got the achievement which I could not imagine just half a year ago — reach 2400 rating and become GM.

The first time I learned about CF was on 2022.2, that time I registered this account and took my first contest. But my first submission 146390589 on contest got TLE, and I solved 0 problem in this contest. (At that time I didn't know that's because the efficiency of java.util.Scanner is extremely low) And because I needed to deal with graduation thesis, I didn't use CF until the end of last year, when I restarted CF contest.

At 4th and 5th contests I solved div2D problems to reach blue. In my 9th contest, I first time solved div2E problem in contest, and I became purple in my 12th contest. In my 14th and 15th contest, I solved div2E problems twice and became orange. In the next weeks, I started to hit the upper limit of my skill, and dropped from orange twice.

In order to improve my skill of competive programming, I practiced problems in CF problemset everyday, and when practicing I tried to solve every problem with 2000-2500 difficulty by the reverse order in the problemset. I took part in every rated CF contest (except Codeforces Round 856 (Div. 2) which was timed at 01:35 UTC+8), and learned many new techniques from problems I could not solve in contests. I also used other CP platfroms like atcoder, where I've reached rating 2233.

It seems that practice was pretty effective for me. I got well performance in last 3 contests rated for div1, and first time became red yesterday. Although there's still a large promotion space for me, it's an important meaningful moment in my life of competitive programming. Hope that I will be more active to face the challange in the future.

Thank for MikeMirzayanov and every contributors of CodeForces community for bring me into the world of competitive programming and helping me find the meaning of my life.

Full text and comments »

+471

YocyCraft
12 months ago
41

There's mistake in editorial of 1661F?

By YocyCraft, history, 14 months ago, In English

In English

See my comment: There's inconsistency in tutorial and solution code of 1661F.

Full text and comments »

+36

YocyCraft
14 months ago
12

Can someone hack my submission for 1796E?

By YocyCraft, history, 14 months ago, In English

In English

Problem link: 1796E - Красивые подграфы

When solving this problem I only know how to solve for a fixed root, and it's better to let a leaf node with smaller distance to the nearest node with degree>=3 to be the root, but I don't know how to choose it. So I sort all leaves by there distance, and try first 40 of them to be the root. I've thought it could fail on some large tests but unexpectedly it got AC. Can someone hack this solution or prove it's correctness?

My submission:195462544

Update: My submission has been hacked

Full text and comments »

+4

YocyCraft
14 months ago
2

Solution of 1796F by hard-coding

By YocyCraft, history, 14 months ago, In English

In English

Problem link: 1796F - Strange Triples

Let $$$p =$$$ number of digits of $$$n$$$, $$$q =$$$ number of digits of $$$b$$$, we have $$$n=\frac{a \cdot b \cdot (10^{p}-1)}{a \cdot 10^{q}-b}$$$, by checking every pair of possible $$$(a, b, p)$$$ we have a $$$O(A \cdot B \cdot log(N))$$$ solution, but it will get TLE.

We can modify this solution slightly: let $$$c=gcd(a, b)$$$, $$$k=\frac{a}{c}$$$, we have $$$n=\frac{k \cdot b \cdot (10^{p}-1)}{k \cdot 10^{q}-(b/c)}$$$, because $$$gcd(k, k \cdot 10^{q}-(b/c))=gcd(k, b/c)=gcd(a/c, b/c)=gcd(a, b)/c=1$$$, we have $$$k \cdot 10^{q}-(b/c)$$$ is divisor of $$$b \cdot (10^{p}-1)$$$, therefore, by pre-calculate factors for numbers in range $$$[1, 100000]$$$ and in $$${999999, 9999999, 99999999, 999999999}$$$, we can check answer for $$$b$$$ in $$$O(\sigma(b) \cdot 185)$$$, where $$$\sigma(b)$$$ is the number of divisors of $$$b$$$, and $$$185=\sum_{p=1}^{9}\sigma(10^{p}-1)$$$, and we can solve the problem in $$$O(B \cdot log(B) \cdot 185)$$$, but this solution still get TLE due to large constant factor of division and modular operations.

If we let $$$A, B, N$$$ be their maximum value, we can see there are only $$$172104$$$ possible valid tuples can be the answer, so we could solve the problem by hard-coding-- however, each pair of $$$(a, b)$$$ will add about $$$10 \sim 20$$$ bytes to the size of code, and we need $$$2 \sim 3MB$$$ to store all pairs, which exceed the limit of $$$64KB$$$. By printing all valid tuples, we can see that for almost all pairs of $$$(a, b)$$$, the value of $$$a/b$$$ is some integer power of $$$10$$$, and for other pairs, there are only $$$6143$$$ different possible values of $$$b$$$. Therefore, we can hardcode these values (for $$$34KB$$$), and for $$$b$$$ which is not hardcoded, we can only check for $$$a=10^{t} \cdot b$$$ (for every pair of $$$(b, p)$$$ there are only $$$5$$$ possible values of $$$a$$$), then we can solve the problem in $$$2000ms$$$.

My submission: 195426974

Code for generating values of b

#include <bits/stdc++.h>

using namespace std;

char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;

#define tp3(T) tuple<T,T,T>
#define tp4(T) tuple<T,T,T,T>

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define outrange(x,min,max) ((x)<(min) || (x)>(max))

ll _start_time;
#define nano (chrono::system_clock::now().time_since_epoch().count())
#define reset_timer _start_time=nano
#define chime cout<<((nano-_start_time)/1e9)<<endl
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))

#ifndef ONLINE_JUDGE
#define debug(x) (cout<<(#x)<<':'<<(x)<<'\n')
#else
#define debug(x)
#endif

void yesno(bool a) {
	cout << (a ? "Yes\n" : "No\n");
}

template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template<typename T1, typename T2, typename T3>
ostream& operator<<(ostream& out, const tuple<T1, T2, T3>& tp) {
	auto [t1, t2, t3] = tp;
	out << '(' << t1 << ',' << t2 << ',' << t3 << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const unordered_set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

using u64 = unsigned long long;

u64 pow_10[]={1, 10, 100, 1000, 10000, 100'000, 1'000'000,
	10'000'000, 100'000'000, 1'000'000'000};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	u64 A,B,N;
//	cin>>A>>B>>N;
	A=pow_10[5];
	B=pow_10[5];
	N=pow_10[9];
	vector<vector<u64>> b_factors(100001,vector<u64>());
	vector<vector<u64>> factors(10,vector<u64>());
	
	for(int i=1;i<=100000;i++){
		for(int j=i;j<=100000;j+=i){
			b_factors[j].push_back(i);
		}
	}
	
	for(int digit_n=1;digit_n<=9;digit_n++){
		int t=pow_10[digit_n]-1;
		for(int i=1;i*i<=t;i++){
			int j=t/i;
			if(i*j!=t) continue;
			factors[digit_n].push_back(i);
			if(i!=j) factors[digit_n].push_back(j);
		}
	}
	u64 ans=0;
	
	unordered_set<u64> checked;
	vector<tp3(int)> v;
	for(int digit_b=1;digit_b<=5;digit_b++){
		u64 pow10_b=pow_10[digit_b];
		for(u64 b=pow10_b/10;b<min(B,pow10_b);b++){

			//The whole process could cost over 30 seconds, so we need to 
			//know how many values of b we've processed.
			if(b%100==0) cout<<b<<endl;
			
			for(int digit_n=1;digit_n<=9;digit_n++){
				checked.clear();
				for(u64 d1:b_factors[b]){
					for(u64 d2:factors[digit_n]){
						u64 d=d1*d2;
						if(d<pow10_b-b) continue;
						if(checked.count(d)) {
							continue;
						}
						
						checked.insert(d);
						
						u64 r=pow10_b-d%pow10_b;
						if(b%r!=0) continue;
						u64 c=b/r;
						u64 k=(d+r)/pow10_b;
						u64 a=k*c;
						if(a>=A || c!=gcd(a,b)) continue;
						u64 n=k*b*(pow_10[digit_n]-1)/(pow10_b*k-r);
						if(pow_10[digit_n-1]<=n && n<N && n<pow_10[digit_n]) {
							ans++;
							v.emplace_back(a,b,n);
						}
					}
				}
			}
		}
	}
	cout<<ans<<nl;
	
	// Output special values of b.
	ofstream ofs;
	ofs.open("D:\\PandaCpp\\Codeforces\\my_out.txt");
	sort(all(v));
	set<u64> s;
	int t=0;
	for(auto [a,b,n]:v){
		if(b==a || b==10*a || b==100*a || b==1000*a || b==10000*a) continue;
		if(a==b || a==10*b || a==100*b || a==1000*b || a==10000*b) continue;
		if(s.count(b)) continue;
		ofs<<b<<',';
		t++;
		if(t%20==0) ofs<<nl;
		s.insert(b);
	}
}

Full text and comments »

+84

YocyCraft
14 months ago
4

Solution of 1785D/1786F (a typical FFT problem)

By YocyCraft, history, 15 months ago, In English

In English

Problem link:1785D - Wooden Spoon

First, WLOG we can assume we arrange the tournament in such way: In every matches, the left player wins. We can achieve this by doing the following operation to the binary tree of the tournament: for each non-leaf node of the binary tree, if the winner of this node is its right child, we "flip" this node by swapping its left subtree and right subtree. Since fliping doesn't change the winner of each match, this will not change the "wooden spoon", and after this operation, the "wooden spoon" is the right-most node. Since there are $$$2^{n}-1$$$ nodes in the binary tree, we can merge $$$2^{2^n-1}$$$ situations into one by this operation.

For example, we can do operation to this tree:

_________1

_____3_______1

-__5___3___1___2

__7_5_3_6_1_8_4_2

-->

_________1

_____1_______3

-__1___2___3___5

__1_8_2_4_3_6_5_7

Where $$$1$$$ (the left-most node) is the champion, and $$$7$$$ (the right-most node) is the "wooden spoon".

Then we assume the right-most node is k, and there's $$$dp[n][k]$$$ different arrangements (after operation). If $$$k$$$ is the $$$j$$$-th smallest element in the right half of the tree, then we have $$$\sum_{i=1}^{2^{n-1}}dp[n-1][i]$$$ ways to arrange the left half, and $$$dp[n-1][j]$$$ ways to arrange the right half (since $$$k$$$ is also the right-most node in the right-subtree). But in how many ways we can distribute $$$2^{n}$$$ elements into $$$2$$$ halves? Well, since $$$1$$$ is the left-most element, there are $$$k-2$$$ elements we could put in the right part (which are in the range $$$[2, k-1]$$$), and there are actually $$$j-1$$$ elements of them in the right part, so we have $$$\binom{k-2}{j-1}$$$ ways to choose them. Similarly, we have $$$\binom{2^{n}-k}{2^{n-1}-j}$$$ ways to choose elements from $$$[k+1, 2^k]$$$. Therefore, we can get such formula:

$$$dp[n][k]=\displaystyle \sum_{j=1}^{2^{n-1}}(\displaystyle \sum_{i=1}^{2^{n-1}}dp[n-1][i]) \cdot dp[n-1][j] \cdot \binom{k-2}{j-1} \cdot \binom{2^{n}-k}{2^{n-1}-j}$$$

Then we can calculate them by FFT. The answer is $$$2^{2^{n}-1} \cdot dp[n][k]$$$.

Code example

#include <bits/stdc++.h>

using namespace std;

char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;

#define tp3(T) tuple<T,T,T
#define tp4(T) tuple<T,T,T,T>;

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define outrange(x,min,max) ((x)<(min) || (x)>(max))

#define nano (chrono::system_clock::now().time_since_epoch().count())
#define second_since_start ((nano-start)/1e9)
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))

void yesno(bool a) {
	cout << (a ? "YES\n" : "NO\n");
}

template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, unordered_set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, unordered_map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

namespace NTT{
	ll mod=998244353;
	ll w[]= {1, 998244352, 911660635, 
		372528824, 929031873, 452798380, 922799308, 781712469,
		476477967, 166035806, 258648936, 584193783, 63912897,
		350007156, 666702199, 968855178, 629671588, 24514907, 
		996173970, 363395222, 565042129, 733596141, 267099868,
		15311432};
	ll pow2Inv[]={1, 499122177, 748683265, 
		873463809, 935854081, 967049217, 982646785, 990445569, 
		994344961, 996294657, 997269505, 997756929, 998000641, 
		998122497, 998183425, 998213889, 998229121, 998236737, 
		998240545, 998242449, 998243401, 998243877, 998244115, 
		998244234};
	
	int prev_n=-1;
	int* rev_bit;
	ll __b[1<<21];
	
	void but(ll &_a,ll &_b, ll _w){
		ll mul=_w*_b%mod;
		_b=_a+mod-mul;
		if(_b>=mod) _b-=mod;
		_a+=mul;
		if(_a>=mod) _a-=mod;
		//		cout<<_a<<":"<<_b<<":"<<_w<<endl;
	}
	
	void intt(ll *a,int n){
		int pow2=1<<n;
		if(n!=prev_n){
			rev_bit=new int[pow2];
			for(int i=0;i<pow2;i++){
				int rev=0;
				int j=i;
				for(int k=0;k<n;k++){
					rev<<=1;
					rev|=(j&1);
					j>>=1;
				}
				rev_bit[i]=rev;
			}
		}
		for(int i=0;i<pow2;i++) __b[i]=a[rev_bit[i]];
		for(int L=n;L>0;L--){
			
			//			for(int i=0;i<8;i++) cout<<b[i]<<' '<<endl;
			
			int d=1<<(n-L);
			int d2=2*d;
			ll w1=1;
			int w0=w[n-L+1];
			for(int i=0;i<d;i++){
				for(int j=i;j<pow2;j+=d2){
					//					cout<<j<<":"<<j+d<<":"<<w1<<endl;
					but(__b[j],__b[j+d],w1);
				}
				w1=(w1*w0%mod);
			}
		}
		ll lenInv=pow2Inv[n];
		a[0]=(__b[0]*lenInv)%mod;
		for(int i=1;i<pow2;i++) a[i]=(__b[pow2-i]*lenInv)%mod;
		prev_n=n;
	}
	
	void ntt(ll *a,int n){
		int pow2=1<<n;
		if(n!=prev_n){
			rev_bit=new int[pow2];
			for(int i=0;i<pow2;i++){
				int rev=0;
				int j=i;
				for(int k=0;k<n;k++){
					rev<<=1;
					rev|=(j&1);
					j>>=1;
				}
				rev_bit[i]=rev;
			}
		}
		for(int i=0;i<pow2;i++) __b[i]=a[rev_bit[i]];
		for(int L=n;L>0;L--){
			int d=1<<(n-L);
			int d2=2*d;
			ll w1=1;
			int w0=w[n-L+1];
			for(int i=0;i<d;i++){
				for(int j=i;j<pow2;j+=d2){
					but(__b[j],__b[j+d],w1);
				}
				w1=(w1*w0%mod);
			}
		}
		for(int i=0;i<pow2;i++) a[i]=__b[i];
		prev_n=n;
	}
	
	ll* convolution(ll *a,ll *b,int n) {
		int len=1<<n;
		ll *c=new ll[len];
		ntt(a,n);
		ntt(b,n);
		for(int i=0;i<len;i++) {
			c[i]=(a[i]*b[i])%mod;
		}
		intt(c,n);
		return c;
	}
	
	ll *selfConvolution(ll *a,int n) {
		int len=1<<n;
		ntt(a,n);
		for(int i=0;i<len;i++) {
			a[i]=(a[i]*a[i])%mod;
		}
		intt(a,n);
		return a;
	}
}
using namespace NTT;

ll *factorial;//[upperBound];
ll *factorial_inv;

ll modInv(ll n) {
	ll pow=mod-2;
	ll result=1;
	while(pow>0) {
		if((pow&1)==1) result=(result*n)%mod;
		n=(n*n)%mod;
		pow>>=1;
	}
	return result;
}

ll modPow(ll n,ll pow) {
	ll result=1;
	while(pow>0) {
		if((pow&1)==1) result=(result*n)%mod;
		n=(n*n)%mod;
		pow>>=1;
	}
	return result;
}

void prepareFactorialAndInv(int max) {
	factorial=new ll[max+1];
	factorial_inv=new ll[max+1];
	factorial[0]=1;
	for(int i=1;i<=max;i++) {
		factorial[i]=factorial[i-1]*i%mod;
	}
	factorial_inv[max]=modInv(factorial[max]);
	for(int i=max-1;i>=0;i--) {
		factorial_inv[i]=factorial_inv[i+1]*(i+1)%mod;
	}
}

const int MAX=(1<<20)+5;
ll dp[MAX];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	if(n==1){
		cout<<"0\n2";
		return 0;
	}
	prepareFactorialAndInv(1<<n);
	dp[0]=0;
	dp[1]=0;
	dp[2]=0;
	dp[3]=1;
	dp[4]=2;
	ll dp_sum=3;
	for(int m=3;m<=n;m++){
		ll* f=new ll[1<<m];
		ll* g=new ll[1<<m];
		ll pow2=1<<(m-1);
		for(ll j=0;j<pow2;j++){
			f[j]=factorial_inv[j]*factorial_inv[pow2-(j+1)]%mod;
			g[j]=f[j]*dp[j+1]%mod;
		}
		for(ll j=pow2;j<2*pow2;j++){
			f[j]=0;
			g[j]=0;
		}
		ll* conv=convolution(f,g,m);
		ll dp_sum_next=0;
		for(ll k=0;k<=m;k++) dp[k]=0;
		for(ll k=m+1;k<=(1<<m);k++){
			dp[k]=dp_sum*factorial[k-2]%mod*factorial[(1<<m)-k]%mod*conv[k-2]%mod;
			dp_sum_next+=dp[k];
			if(dp_sum_next>=mod) dp_sum_next-=mod;
		}
		dp_sum=dp_sum_next;
//		cout<<m<<":"<<dp_sum<<nl;
	}
	ll pow2=modPow(2,(1<<n)-1);
//	cout<<pow2<<nl;
	for(int k=1;k<=n;k++) cout<<"0\n";
	for(int k=n+1;k<=(1<<n);k++){
		cout<<pow2*dp[k]%mod<<nl;
	}
}

Full text and comments »

+42

YocyCraft
15 months ago
3

Update the rating of last div2 round for me plz

By YocyCraft, history, 15 months ago, In English

In English

Don't forget to update the rating of #848 for me later. I was in div1 when registered in this contest, but that's because my negative rating in TypeDB round was rolled back temporarily, and I should be counted as div2 in this contest.MikeMirzayanov

Update: This screenshot is definately contradict with the rule of codeforces rounds. If this won't be fixed, how can I explain this weird result to new users of codeforces?

Full text and comments »

+52

YocyCraft
15 months ago
11

Is it normal that a submission need to wating for over 10 minutes to be judged?

By YocyCraft, history, 15 months ago, In English

In English

I've just posted a topic complaining about slow judge, and it received 4 downvotes in just 5 minutes, so I have no choice but to delete it. So could someone tell me is it normal that a submission need to wating for over 10 minutes to be judged?

Update: Now my new submission 191736305 has got AC, but it also has waited for 6 minutes.

Update; Encounter a problem on CF ---> post a blog for asking for it ---> get downvoted by unknown reason ---> be forced to delete the blog to save contribution ---> encounter more problems. How can this vicious cycle be stopped? The greatest disadvantage of CF downvoting system: I will never know the reason I being downvoted.

Update: If you're getting annoyed by this blog, please comment something like "asking for system technical issue is not welcomed on codeforces" instead downvote.

Full text and comments »

+46

YocyCraft
15 months ago
12

JaTLEva

By YocyCraft, history, 15 months ago, In English

In English

Problem:1713D - Tournament Countdown

My submission in java:189203654 (TLE on test3)

My submission in c++:189201160 _(779ms)(Most part of them are same, expect time cost of IO)

If there are no testers of rounds using java, maybe I should give up.

Full text and comments »

Tags

java

+12

YocyCraft
15 months ago
4

What does "Registration is private" mean?

By YocyCraft, history, 15 months ago, In English

In English

Will the next div1+div2 round be open for us?

Update: Now the registration has begun.

Full text and comments »

+27

YocyCraft
15 months ago
8

Maybe it's the limitation of the programming language?

By YocyCraft, history, 15 months ago, In English

In English

Today when I upsolving 1768F - Великолепный прыжок in which the intended solution is pretty simple. But the time complexity is O(n^1.5) and n=4*10^5 the time limit is pretty strict. I implemented the intended solution in java for many times but I always got TLE. Then I copied the submission 188424856 _(483ms) which is simpler the the official solution, and implemented in java, and got AC for 3322ms (My submission:188904779). It seems that sometimes you must to optimize the solution further than intended.

Also the official judge runs java code much more slowly than on my computer. I tested for cases where a[i]=1+(i%mod), where mod was about sqrt(400000). The code ran for about 0.6s but for the similar cases of the official judge it ran for about 2.3s.

The code for testing time cost on my computer


import java.util.*;
import java.io.*;
public class Problem1768F {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws Exception {
		long start = System.nanoTime();
		
		int n =400000; //Integer.parseInt(br.readLine());
		long[] a = new long[n];
		long[] dp=new long[n];
		int mod=640;// also tested for 1000 and 320
		for (int i = 0; i < n; i++) {
			//Simulate the test case: 1 2 3 4 5 ...
			a[i] =(i%mod)+1; //readInt();
			dp[i]=2L*n*n;
		}
		dp[0]=0;
		for(int i=0;i<n;i++) {
			int lb=(int)Math.max(0,i-n/a[i]);
			for(int j=i-1;j>=lb;j--) {
				dp[i]=Math.min(dp[i], dp[j]+a[i]*(i-j)*(i-j));
				if(a[i]>=a[j]) break;
			}
			int ub=(int)Math.min(n-1, i+n/a[i]);
			for(int j=i+1;j<=ub;j++) {
				dp[j]=Math.min(dp[j], dp[i]+a[i]*(j-i)*(j-i));
				if(a[i]>=a[j]) break;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<n;i++) sb.append(dp[i]).append(' ');
		
		long end = System.nanoTime();
		
		//Tested for dozens of times. Max time cost is 0.63s
		System.out.println((end - start) / 1E9);
		
		//System.out.println(sb);
	}

	public static int readInt() {
		int input = 0;
		int c;
		int sign = 1;
		try {
			while ((c = br.read()) == '-') {
				sign = -sign;
			}
			input *= 10;
			input += (c - 48);
			while ((c = br.read()) > 32) {
				input *= 10;
				input += (c - 48);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (sign == 1) ? input : -input;
	}

	public static long readLong() {
		long input = 0;
		int c;
		int sign = 1;
		try {
			while ((c = br.read()) == '-') {
				sign = -sign;
			}
			input *= 10;
			input += (c - 48);
			while ((c = br.read()) > 32) {
				input *= 10;
				input += (c - 48);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (sign == 1) ? input : -input;
	}
}

Full text and comments »

+8

YocyCraft
15 months ago
11

There's system bug in hacking phase?

By YocyCraft, history, 15 months ago, In English

In English

In the recent educational round, there's a hacking attempt still in "waiting" situation, despite the open hacking phase has ended for 10 hours, which caused system test phase cannot start. Is there any bug of hacking system? Please fix it quickly I'm impatient to be orange

Update: Now rating is updated and finally I've become orange! excited

Full text and comments »

+15

YocyCraft
15 months ago
10

How to implement multiset in java efficiently?

By YocyCraft, history, 16 months ago, In English

In English

In 1718C - Tonya and Burenka-179 I implemented a solution with intended complexity (which was O(n*log(n)*PrimeFactorCount(n))), which need a multiset to update the possible answer between queries, and answer the max element of the multiset for each query. But since there's no multiset in java, I had to simulate a multiset by a TreeMap, which caused TLE (my submission:188008030)

I looked at other java solution for this problem and no one got AC. Is this problem unsolvable for java or there's better implementation for multiset?

Full text and comments »

+15

YocyCraft
16 months ago
6

Optimize the solution by randomization?

By YocyCraft, history, 16 months ago, In English

In English

Today I implemented the intended solution of 1767E

Which unexceptedly got TLE...

Then I tested the sample which input is small (n=10, m=40) and recorded the time consuming of each step in my first solution

I discoverd that when good mask1 of vertex set A (1-m/2) is too much (about 2^19), the preparation of dp takes very long time (about 1000ms on my computer but 1700+ms on official judge)

However, in most of test samples the time consuming is not that much beacuse of a smaller set of good mask1. So I thought about if I permute the number of colors randomly......

In 1st attempt I still got TLE, but after changed the seed of java.util.Random, I got AC in the 2nd attempt

(I know there must be better implementation but I'm lazy QwQ)

Full text and comments »

+8

YocyCraft
16 months ago
4

Does java8 performs better than java17?

By YocyCraft, history, 16 months ago, In English

In English

Today I got 1700ms after many TLEs in problem 1774F1

submission in java17

Then I submitted the same code in java8 again then got 1352ms

submission in java8

It seems that java8 performs better

Full text and comments »

+10

YocyCraft
16 months ago
2

What's wrong with CF

By YocyCraft, history, 16 months ago, In English

In English

No rating update for educational #139

No editorial for div2 #837

Waited for so looooooooooooooooooong time

What happened

Full text and comments »

-8

YocyCraft
16 months ago
5