Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy!
Is it rated?
Tutorial is loading...
Code
n = int(input())
results = []
for i in range(n):
results.append(list(map(int, input().split())))
for r in results:
if r[0] != r[1]:
print("rated")
exit()
for i in range(n):
for j in range(i):
if results[i][0] > results[j][0]:
print("unrated")
exit()
print("maybe")
T-Shirt Hunt
Tutorial is loading...
More efficient code
#include <bits/stdc++.h>
using namespace std;
int main() {
int p, x, y;
cin >> p >> x >> y;
for (int s = y; ; s++) {
if (s % 50 != x % 50) {
continue;
}
bool me = false;
int i = s / 50 % 475;
for (int j = 0; j < 25; j++) {
i = (i * 96 + 42) % 475;
if (i + 26 == p) {
me = true;
break;
}
}
if (me) {
printf("%d\n", (max(0, s - x) + 50) / 100);
break;
}
}
return 0;
}
Less efficient code
p, x, y = map(int, input().split())
def check(s):
i = (s // 50) % 475
for t in range(25):
i = (i * 96 + 42) % 475
if 26 + i == p:
return True
return False
for up in range(500):
for down in range(500):
if x + 100 * up - 50 * down >= y and check(x + 100 * up - 50 * down):
print(up)
exit()
assert(False)
Success Rate
Tutorial is loading...
Binary search solution code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll x, ll y, ll p, ll q, ll t) {
return p * t >= x && q * t - p * t >= y - x;
}
void solve() {
ll x, y, p, q;
scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
ll l = -1;
ll r = (ll) 1e9;
if (!check(x, y, p, q, r)) {
printf("-1\n");
return;
}
while (r - l > 1) {
ll m = (l + r) / 2;
if (check(x, y, p, q, m)) {
r = m;
} else {
l = m;
}
}
printf("%lld\n", r * q - y);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
Formula solution code
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int x, y, p, q;
cin >> x >> y >> p >> q;
if (p == 0) {
cout << (x == 0 ? 0 : -1) << endl;
continue;
}
if (p == q) {
cout << (x == y ? 0 : -1) << endl;
continue;
}
int t1 = (x + p - 1) / p;
int t2 = ((y - x) + (q - p) - 1) / (q - p);
cout << (q * 1LL * max(t1, t2) - y) << endl;
}
return 0;
}
Dynamic Problem Scoring
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 123456;
const int m = 5;
const int k = 6;
int a[N][m];
int score[N];
int cost[m];
int solved[m];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", a[i] + j);
if (a[i][j] != -1) {
solved[j]++;
}
}
}
for (int bots = 0; bots <= ((1 << (k - 1)) - 1) * n; bots++) {
for (int j = 0; j < m; j++) {
int total = n + bots;
int cur = solved[j];
if (a[0][j] != -1 && a[1][j] != -1 && a[0][j] > a[1][j]) {
cur += bots;
}
cost[j] = 500;
while (cost[j] < 500 * k && 2 * cur <= total) {
cur *= 2;
cost[j] += 500;
}
}
for (int i = 0; i < 2; i++) {
score[i] = 0;
for (int j = 0; j < m; j++) {
if (a[i][j] != -1) {
score[i] += cost[j] / 250 * (250 - a[i][j]);
}
}
}
if (score[0] > score[1]) {
printf("%d\n", bots);
return 0;
}
}
printf("%d\n", -1);
return 0;
}
Prairie Partition
Tutorial is loading...
Code with the second optimization
n = int(input())
a = sorted(list(map(int, input().split())))
maxe = max(a)
cnt = []
cur = 1
k = 0
i = 0
while i < n:
cnt.append(0)
while i < n and a[i] < cur:
cnt[2 * k] += 1
i += 1
cnt.append(0)
while i < n and a[i] == cur:
cnt[2 * k + 1] += 1
i += 1
k += 1
cur *= 2
cnt.append(0)
cnt.append(0)
maxe = len(cnt) - 1
maxk = cnt[1]
was = False
for l in range(maxk):
cur = 1
while cnt[cur] > 0:
cnt[cur] -= 1
cur += 2
cnt[cur] -= 1
cursum = 0
ok = True
for t in range(maxe, 0, -1):
cursum += cnt[t]
if cursum > 0:
ok = False
break
if ok:
print(l + 1, end=" ")
was = True
if not was:
print(-1)
Code with both optimizations
#include <bits/stdc++.h>
using namespace std;
const int MAX = 66;
int power[MAX + 10];
int between[MAX + 10];
int extra[MAX + 10];
int ende[MAX + 10];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
long long foo;
cin >> foo;
int cc = 0;
bool good = true;
while (foo > 1) {
if (foo & 1) {
good = false;
}
cc++;
foo >>= 1;
}
if (good) {
power[cc]++;
} else {
between[cc]++;
}
}
int low = 1, high = power[0] + 1;
while (low < high) {
int mid = (low + high) >> 1;
int cur = mid;
for (int i = 0; i < MAX; i++) {
extra[i] = power[i] - cur;
int new_cur = min(cur, power[i + 1]);
ende[i] = cur - new_cur;
cur = new_cur;
}
bool fail = false;
int open = 0;
for (int i = MAX - 1; i >= 0; i--) {
open += ende[i];
open -= between[i];
open -= extra[i + 1];
if (open < 0) {
fail = true;
break;
}
}
open -= extra[0];
if (open < 0) {
fail = true;
}
if (fail) {
low = mid + 1;
} else {
high = mid;
}
}
if (low > power[0]) {
cout << -1 << endl;
return 0;
}
for (int i = low; i <= power[0]; i++) {
cout << i << " ";
}
cout << endl;
return 0;
}
Perishable Roads
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18;
const int N = 2010;
int a[N][N];
long long d[N];
bool used[N];
int main() {
// reading input data
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
a[i][i] = 0;
for (int j = i + 1; j < n; j++) {
scanf("%d", a[i] + j);
a[j][i] = a[i][j];
}
}
// finding minimum edge weight
int min_edge = a[0][1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
min_edge = min(min_edge, a[i][j]);
}
}
}
// subtracting minimum edge weight from all edge weights
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
a[i][j] -= min_edge;
}
}
}
// initializing distance array
for (int i = 0; i < n; i++) {
d[i] = inf;
for (int j = 0; j < n; j++) {
if (i != j) {
d[i] = min(d[i], 2LL * a[i][j]);
}
}
used[i] = false;
}
// running Dijkstra
for (int it = 0; it < n; it++) {
long long min_d = inf;
int ver = -1;
for (int i = 0; i < n; i++) {
if (!used[i] && d[i] < min_d) {
min_d = d[i];
ver = i;
}
}
used[ver] = true;
for (int i = 0; i < n; i++) {
d[i] = min(d[i], d[ver] + a[ver][i]);
}
}
// printing result
for (int i = 0; i < n; i++) {
cout << (d[i] + (long long) min_edge * (n - 1)) << endl;
}
return 0;
}
Blog Post Rating
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
inline int signum(int x) {
return (x < 0 ? -1 : (x > 0 ? 1 : 0));
}
const int inf = (int) 1e9;
const int N = 500010;
pair <int, int> a[N];
int pos[N];
pair <int, int> mn[4 * N];
int add[4 * N];
void push(int x) {
add[x + x] += add[x];
mn[x + x].first += add[x];
add[x + x + 1] += add[x];
mn[x + x + 1].first += add[x];
add[x] = 0;
}
void pull(int x) {
mn[x] = min(mn[x + x], mn[x + x + 1]);
}
void build(int x, int l, int r) {
add[x] = 0;
if (l == r) {
mn[x] = make_pair(a[l].first, l);
return;
}
int y = (l + r) >> 1;
build(x + x, l, y);
build(x + x + 1, y + 1, r);
pull(x);
}
void modify(int x, int l, int r, int ll, int rr, int v) {
if (ll <= l && r <= rr) {
add[x] -= v;
mn[x].first -= v;
return;
}
push(x);
int y = (l + r) >> 1;
if (ll <= y) {
modify(x + x, l, y, ll, rr, v);
}
if (rr > y) {
modify(x + x + 1, y + 1, r, ll, rr, v);
}
pull(x);
}
pair <int, int> find_min(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return mn[x];
}
push(x);
int y = (l + r) >> 1;
pair <int, int> res = make_pair(inf, -1);
if (ll <= y) {
res = min(res, find_min(x + x, l, y, ll, rr));
}
if (rr > y) {
res = min(res, find_min(x + x + 1, y + 1, r, ll, rr));
}
pull(x);
return res;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].first);
a[i].second = i;
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
pos[a[i].second] = i;
}
build(1, 0, n - 1);
set <int> minus, zero, plus;
for (int id = 0; id < n; id++) {
int i = pos[id];
auto p = find_min(1, 0, n - 1, i, i);
int vote = signum(p.first);
if (vote == 0) {
zero.insert(i);
} else {
if (vote == -1) {
minus.insert(i);
modify(1, 0, n - 1, i, n - 1, -1);
int last_minus = *(--minus.end());
if (a[last_minus].first == 1 - (int) minus.size()) {
minus.erase(last_minus);
modify(1, 0, n - 1, last_minus, n - 1, 1);
zero.insert(last_minus);
} else {
if (!zero.empty()) {
int first_zero = *(zero.begin());
zero.erase(first_zero);
plus.insert(first_zero);
modify(1, 0, n - 1, first_zero, n - 1, 1);
}
}
} else {
plus.insert(i);
modify(1, 0, n - 1, i, n - 1, 1);
auto q = find_min(1, 0, n - 1, i, n - 1);
if (q.first == -1) {
int pos = q.second;
plus.erase(pos);
modify(1, 0, n - 1, pos, n - 1, -1);
zero.insert(pos);
}
}
}
printf("%d\n", (int) plus.size() - (int) minus.size());
}
return 0;
}
Test Data Generation
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
const long double pi = acos((ld)-1.0);
const int maxn = 1 << 16;
typedef complex<double> comp;
comp oddc[maxn], evenc[maxn], tmp[maxn];
comp w[maxn], invw[maxn];
ll odd[maxn], even[maxn];
int oldodd[maxn], oldeven[maxn];
int btr[maxn];
int n, A, mod;
int st2;
int answer;
inline int bitrev(int x)
{
return btr[x];
}
void fft(comp *a, int n, comp *w, comp *res)
{
for (int i = 0; i < n; i++) res[bitrev(i)] = a[i];
for (int len = 2; len <= n; len *= 2)
{
int step = n / len;
for (int i = 0; i < n; i += len)
{
int curw = 0;
for (int j = 0; j < len / 2; j++)
{
comp x = res[i + j];
comp y = res[i + len / 2 + j] * w[curw];
res[i + j] = x + y;
res[i + len / 2 + j] = x - y;
curw += step;
}
}
}
}
void preparefft(int n)
{
for (int i = 0; i < n; i++)
{
int cur = i;
for (int j = 0; (1 << j) < n; j++)
{
btr[i] = (btr[i] << 1) | (cur & 1);
cur >>= 1;
}
}
for (int i = 0; i < n; i++)
{
w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i));
invw[i] = w[i];
}
reverse(invw + 1, invw + n);
}
void conv(ll *from, comp *to)
{
for (int i = n + 1; i < st2; i++) tmp[i] = 0;
for (int i = 0; i <= n; i++) tmp[i] = from[i];
fft(tmp, st2, w, to);
}
void convback(comp *from, ll *to)
{
fft(from, st2, invw, tmp);
for (int i = 0; i < st2; i++) tmp[i] /= st2;
for (int i = 0; i <= n; i++)
{
to[i] = (ll)(tmp[i].real() + 0.5);
assert(abs(tmp[i].imag()) < 0.1);
}
}
void addans()
{
for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod;
}
void go(int A)
{
if (A == 1)
{
even[0] = 1;
odd[0] = 0;
odd[1] = 1;
addans();
return;
}
go(A / 2);
for (int i = 0; i <= n; i++) oldodd[i] = odd[i];
for (int i = 0; i <= n; i++) oldeven[i] = even[i];
conv(even, evenc);
conv(odd, oddc);
for (int i = 0; i < st2; i++)
{
if ((A / 2) % 2 == 0)
{
tie(oddc[i], evenc[i]) = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
} else
{
tie(evenc[i], oddc[i]) = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1));
}
}
convback(oddc, odd);
convback(evenc, even);
for (int i = n + 1; i <= 2 * n; i++)
{
odd[i] = 0;
even[i] = 0;
}
for (int i = 0; i <= n; i++)
{
odd[i] = (odd[i] + oldodd[i]) % mod;
even[i] = (even[i] + oldeven[i]) % mod;
}
if (A % 2 == 1)
{
for (int i = n; i >= 1; i--)
{
odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod;
}
}
addans();
}
int main()
{
cin >> n >> A >> mod;
if (A == 1)
{
cout << 0 << endl;
return 0;
}
st2 = 0;
while ((1 << st2) <= n) st2++;
st2++;
st2 = 1 << st2;
preparefft(st2);
go(A / 2);
cout << answer << endl;
return 0;
}
O(1) solution for DIV2C. Code
A bit simpler O(1) solution is described as the second solution in the tutorial.
I guess it is O(T) to be presize.)
I think I misunderstood DIV2 D. I thought Vasya could submit a wrong solution to a problem through the bots even if he has solved that problem correctly himself ? Is that wrong ?
That's correct, Vasya can submit wrong solutions to problems he has solved. In fact, though, submitting wrong solutions can be useful for just one thing — making a new account count as a round participant without solving any problems.
But wouldn't that help Vasya(in the case when he solves the problem before Petya) by lowering the solvers fraction and thereby increasing the maximum points he could gain from that problem ?
Well, yes, if Vasya solves the problem before Petya, he shouldn't submit correct solutions to it. He can submit either wrong solutions or just nothing.
How to solve Div2C this way? We have (x+c)/(y+c+d)=p/q; So (qx+qc) = py+pc+pd=> (qx-py)=p(c+d) — qc where (qx-py)= S. So we have linear Diophantine equation S=p(c+d) — qc with unknowns (c+d) and c. So is it possible to solve this problem this way and if yes, how would it be implemented?
UPD: Sorry for duplicate
I tried to do that. Here is my attempt 26939775
It needs to be debugged a little, but general idea is correct. I've lost motivation to finish it once I knew that there is a much cleaner way :)
for (int bots = 0; bots <= ((1 << k) — 1) * n; bots++) {In the code of 806B — Dynamic Problem Scoring, the '+' is gone as "&mdash"
Presumably it's a
-(a dash), not a+.Yes, it was meant to be a minus, not a plus :) Not sure why it transformed into "—". Fixed.
Why the editorial is not appearing in contest page or announcement page? Please add link.
Thank you, added the link to the announcement page. It will appear on the contest page shortly.
In problem Div2 D the point calculation says ->
2000*(1 - 40 / 250) = 1680Where 40 is the time of solve and 2000 is max point. So what happens if he solve a problem at 0 min from the start of contest? This case is valid as it is used in test case 3.Thanks in advance.
Naturally, he will get 2000·(1 - 0 / 250) = 2000 points.
Sorry my bad.
For div2/C why do we have to put while(r-l>1)
Binary search, google it.
Binary search says while(l<r) <=> while(r-l>0) not while(r-l>1)
I wanted to ask the same question. Could anyone tell what's the difference between
while (l < r)andwhile (r - l > 1)?At first glance it seems like the second variant somehow helps to avoid an infinite loop, but I am not sure.
Consider that during the execution of binary search we have at some instant, r=l+1. Most implementations have mid=(l+r)/2 . Thus, mid=l. Now, if the check condition for the binary search evaluates to false for mid=l and if we are looking for the upper bound, the update would then be l=mid. This would lead to an infinite loop.
I believe it could be avoided if the update step is l=mid+1.
What's wrong with Div1E and Div1F editorials?
For Div1F it shows
Tutorial is not available, just code.For Div1E there is an explanation why users should rate the blog post in non-decreasing order, it ends with
Now, supposeand then code is provided. It seems incomplete.Thank you, fixed.
Question about Div1E
How can we set up a sorted collection of users that supports insertion (or deletion instead) and final blog-post rating calculation in O(log(N)) time or less?
UPD: Now solution described in editorial is clear for me.
Funny solution for DIV2B, O(1) (??) (binary search on array of 25 elements + some O(1) operations) : 26939967
Lol..! It can be done but actually you don't get time during competition to make such a matrix or say table.
Can anyone help with this statement related to Div.2 problem C ? Why does t have to be less than or equal to y here ?
"It can be proved that one "very large" value of t is t = y — that is, if the inequalities are not satisfied for t = y, then they cannot be satisfied for any value of t."
That was the only bug in my code during the contest. I took t up to 1e18. What I can see is q>=p and increasing t will anyhow increase the difference between numerator and denominator. Please help.
Same :(
Here the inequality is t(q-p)>=y-x. If t==y then y(q-p) is clearly greater than y-x when p!=q and x!=y. if x==y and p==q then it will be y(q-p)=y-x=0.
We are trying to make the following hold:
if
t=y, then both of the conditions above will hold.Since we are trying to find the smallest possible value for t, then we can use y as an upper bound on t.
excuse me ! i was just wondering if Div 2 C problem can be solved by Extended Euclid Algorithm ? what i am doing is following let a be the number of Successful hacks and b the number of unsuccessful ones now if hack is successful i will increase the numerator by a it would be x+a,,and denominator would be increased also by y+a
if hack is unsuccessful denominator only will be increased by b then it would become y+a+b
true: x+a/y+a+b=p/q then -->(q*x)+(q*a)=(y*p)+(a*p)+(b*p) make it as linear equation and solve it by Extended Euclid Algorithm i don't know if is it right or wrong ? what is your opinion i have some problem with Extended Euclid Algorithm so i can't implement clearly but mathematically i think it's right
Yes, we can solve div2C with this approach.
Here is my code: 26955095
For Div1 C (prairie partition ) question. I tried to first satisfy all non 2 power k forms with requirements.And later tried to check if m was satisfiable or not greedily. I think I cannot describe it properly in words. So here is the code. Can someone provide a simple counter case for this approach.
In problem DIV2B, in each iteration for s, we can increment it by 50, rather than 1.
Can you explain for me the sentence is bolded ? Consider an optimal solution, and let k be the smallest index with wk = 0. Let's prove that for all i ≤ k - 3 we have wi > wi + 1. Indeed, assume that for some i ≤ k - 3 we have wi ≤ wi + 1. Then, since the graph is complete, we can replace the i + 1-th edge with an edge directing to an endpoint of any 0-perishability road, and the i + 2-th edge with this 0-perishability road. In this case, the minimized sum will become smaller, which is a contradiction to our solution being optimal.
I don't understand it.
Regardless of the weight of w(i+1), the perishability of the route from the museum to (i+1)th cities will not be affected (because w(i)<w(i+1)). Therefore it is legit to change the (i+1)th. From the (i+2)th cities, the perishability is always zero. Therefore, we jump to a not worse solution (just in case w(i+1)>=w(i)).
Consider an example. Suppose our optimal solution is:
Here, M is the museum city. In this case, we have w = (23, 11, 4, 7, 3, 1, 0, ...). Note that we don't care about what comes after 0, since route perishabilities for all cities starting with G will be 0. The sought sum will be equal to 23 + 11 + 4 + 4 + 3 + 1 = 46.
Now, observe that k = 7, so we know that F-G is a 0-perishability road, but w3 = 4 ≤ 7 = w4. Then I claim that our solution can't be optimal, because the following solution will be better:
That is, we replace the 4-th road with a road directing to F, and F is an endpoint of a 0-perishability road, then we replace the 5-th road with this 0-perishability road itself.
Note that we don't know road C-F perishability, but we know that this road exists, which is enough. The sought sum will be 23 + 11 + 4 + min(4, x) ≤ 42.
hi, can u pls explain the 2nd case of this para:
Then, we have two options: either Wk - 2 > Wk - 1 or Wk - 2 ≤ Wk - 1.In 1st case i got that ans will be sum of peris' till before kth road. pls verifyThank you. I understood !
For Div2D. I copied the solution but it does not pass on a test. Here it is: 26977808. Can you please tell me where is the mistake?
You are 1-indexing your arrays of size m. The out of bounds access causes undefined behaviour.
I modified that and it still gives me wrong answer on test 15.
In your line
replace
<with<=. The bound of 31n new accounts is tight.Why would I get RUNTIME_ERROR on test 7 after replacing
<with<=? 26994891Because you've also replaced
N = 120withN = 12.Next time, you can use the "Compare" feature to figure out what changed in between submissions.
Excuse me, I had to ask:
Div2A states that No two participants have the same number of points, but the test cases include otherwise. Have I missed something?
I guess it's a bit ambiguous, but this statement is about the round points, not about the rating points. It implies that no two participants took the same place in the round.
Thank you
DIV2 D using binary search on multiple intervals. CODE.
Can anyone give the proof for the t=y fact given in Div2C/Div1A editorial?
Let 's' be the number of successful submissions and 'u' be the number of unsuccessful submissions that you added. So, s + x = pt => s = pt — x and y + s + u = qt => u = qt — s — y = qt — (pt — x) — y = t(q-p) — (y-x). So we get s = pt — x and u = t(q-p) — (y-x) clearly s>=0 is impossible when (p==0) and (x!=0). And u>=0 is impossible when (p==q) and (y!=x). So we weed out those possibilities. From the first equation we need t to satisfy pt>=x. In this case, the minimum possible t is the highest when p = 1. Thus the highest minimum possible t is x. From the second equation we need t to satisfy t(q-p)>=(y-x). In this case, the minimum possible t is highest when q-p=1. Thus the highest minimum possible t is y-x.From the above two facts we can say that t never goes higher than max(x,y-x). Since, y>=max(x,y-x) we can say that t never goes above y. I have implemented this idea in my submission — 62595664
Hey tourist, I have basically brute-forced div1-D and I am not quite sure what its actual time complexity is : Link
I am basically running dijkstras from each source, and I just stop the loop whenever the distance till the current node becomes greater than the answer (till that node), and I also restrict the relaxations by firstly sorting the adjacency list of each node in increasing order of weight and ensuring that all the paths are monotonically decreasing in terms of edge weight.
It should be $$$O(N^3.\log{N})$$$, but I ran some stress tests too, and it always seems to stop really early.