Codeforces 452 Div2

Chong Wang Lv6
  2017-12-21 10:47:55 2017-12-21 10:47:55 Created   2026-10-09 09:07:16 2026-10-09 09:07:16 Updated  

I have really forgotten my original intention; my writing keeps getting worse.

Let me write a recap. How can I be this weak?

I got Problem B wrong because of a single ! in the condition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

vector<int>ans;
bool check(int x)
{
	if(x%400==0)return true;
	if((x%4==0)&&(x%100!=0))
		return false;
	if(x%4==0)
		return true;
	return false;
}


void solve()
{
	repp(i,1,5000)
	{
		if(!check(i))
		{
			ans.push_back(31);
			ans.push_back(28);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);

			ans.push_back(30);
			ans.push_back(31);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);
		}
		else
		{
			ans.push_back(31);
			ans.push_back(29);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);

			ans.push_back(30);
			ans.push_back(31);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);
			ans.push_back(30);
			ans.push_back(31);
		}
	}

	int n;
	sa(n);
	vector<int>v;
	rep(i,0,n)
	{
		int x;
		sa(x);
		v.push_back(x);
	}
	rep(i,0,ans.size())
	{
		if(ans[i]==v[0])
		{
			int flag = 1;
			for(int k=0;k<v.size();k++)
			{
				if(i+k>=ans.size())
				{
					flag=0;
					break;
				}
				if(ans[i+k]!=v[k])
				{
					flag=0;
					break;
				}
			}
			if(flag)
			{
				puts("YES");
				return;
			}
		}
	}
	puts("NO");
	return;
}

I spent most of the time stuck on Problem D and had only half an hour left when I wrote it. I will later see what was wrong with my approach.

My approach was to find a pattern: first locate nodes such as 5, 50, 500, and 5000, then observe that the number of added pairs grows like 1 + 2 + 3. The special case is numbers ending in 9, which can then be subtracted. It still feels overcomplicated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
ll v5[20];

ll cal(ll x,ll y,ll m)// Count values of y less than or equal to x.
{
	ll h = x/m;
	h += (x%m==y?1:0);
	return h;
}

void solve()
{
	ll x = 5;
	repp(i,1,10)
	{
		v5[i]=x;
		x*=10;
	}
	ll k;
	slla(k);
	if(k==1)
	{
		puts("0");
		return;
	}
	if(k==2)
	{
		puts("1");
		return;
	}
	if(k==3)
	{
		puts("3");
		return;
	}
	if(k==4)
	{
		puts("6");
		return;
	}
	int pos = upper_bound(v5+1,v5+10+1,k)-v5;
	pos--;
	ll d = 10;
	rep(i,1,pos)
	{
		d*=10;
	}
	ll cnt = (k-v5[pos]+1)/d;
	ll final = v5[pos]+cnt*d-1;
	ll ans = (1+cnt)*cnt/2*d;
	ans+=(k-final)*(cnt+1);
	ll p = 9;
	ll m = 10;
	rep(i,1,pos)
	{
		p=p*10+9;
		m=m*10;
	}
	ans-=cal(k,p,m);
	cout<<ans<<endl;
}

I had previously solved 51nod’s Maximum M Subarray Sum V2, yet I still could not debug Problem E before the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
ll n, m;
ll v[maxn], val[maxn], le[maxn], ri[maxn];
ll pos_val[maxn];
set< pair<ll, int> >heap;

void del(int x)
{
	int Le = le[x], Ri = ri[x];
	if (Le)
		ri[Le] = Ri;
	if (Ri)
		le[Ri] = Le;
}

void solve()
{
	slla(n);
	repp(i, 1, n)
	{
		slla(v[i]);
	}
	v[0] = -1;

	int cnt = 1;
	int len = 1;

	repp(i, 2, n)
	{
		if (v[i] != v[i - 1])
		{
			val[cnt] = len;
			pos_val[cnt] = v[i - 1];
			heap.insert(make_pair(-len, cnt));
			cnt++;
			len = 1;
		}
		else
		{
			len++;
		}
	}
	pos_val[cnt] = v[n];
	val[cnt] = len;
	heap.insert(make_pair(-len, cnt));
	for (int i = 1; i <= cnt; i++)
	{
		le[i] = i - 1, ri[i] = (i == cnt ? 0 : i + 1);
	}
	int ans = 0;
	int k, j;
	while (true)
	{
		ans++;
		if (heap.size() == 1)
		{
			break;
		}
		k = heap.begin()->second, j = heap.begin()->first, heap.erase(heap.begin());
		if (pos_val[le[k]] == pos_val[ri[k]])
		{
			int sum = (val[le[k]] + val[ri[k]]);
			heap.erase(make_pair(-(val[le[k]]), le[k]));
			heap.erase(make_pair(-(val[ri[k]]), ri[k]));
			int t = le[k];
			val[ri[k]] = 0;
			del(ri[k]);
			del(k);
			val[k] = 0;
			val[t] = sum;
			heap.insert(make_pair(-(sum), t));
		}
		else
		{
			val[k] = 0;
			del(k);
		}
	}
	cout << ans << endl;
}

For Problem F, I mainly did not know how to move through the string from the front, so my reasoning stalled there.

Ah, a Fenwick tree can do this. Why did I not know that yet?

Oh—binary search works too, with one more logarithmic factor. Given a prefix sum K, find the position whose prefix sum is K; binary search gives two logarithmic factors. A Google interview once asked about a one-log approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int n, m;
int val[300];
set<int>pos[300];
char v[maxn];
ll num[maxn];
int lowbit(int x)
{
	return x&(-x);
}
ll getsum(ll x)
{
	ll ans = 0;
	while (x>0)
	{
		ans += num[x];
		x -= lowbit(x);
	}
	return ans;
}
ll add(int x, int v)
{
	int up = maxn - 1;
	while (x <= up)
	{
		num[x] += v;
		x += lowbit(x);
	}
	return x;
}

int find_p(int k)
{
	int le = 1, ri = n;
	while (le < ri)
	{
		int mid = (le + ri) / 2;
		if (getsum(mid) < k)
		{
			le = mid + 1;
		}
		else
		{
			ri = mid;
		}
	}
	return le;
}

void solve()
{
	sa(n), sa(m);
	scanf("%s", v + 1);
	repp(i, 1, n)
	{
		pos[v[i]].insert(i);
		add(i, 1);
	}
	repp(i, 1, m)
	{
		int le, ri;
		char op[5];
		scanf("%d%d%s", &le, &ri, op);
		char k = op[0];
		le = find_p(le);
		ri = find_p(ri);

		auto p = pos[k].lower_bound(le);
		while (p != pos[k].end()&&*p <= ri)
		{
			add(*p, -1);
			auto t = p;
			p++;
			pos[k].erase(t);
		}
	}
	repp(i, 1, n)
	{
		if (getsum(i) - getsum(i - 1))
		{
			printf("%c", v[i]);
		}
	}
}

On this page
Codeforces 452 Div2