### awoo's blog

By awoo, history, 2 years ago, translation,

1036A - Function Height

Tutorial
Solution (Vovuh)
n, k = map(int, input().split())
print((k + n - 1) // n)


1036B - Diagonal Walking v.2

Tutorial
Solution (Vovuh)
q = int(input())

for i in range(q):
n, m, k = map(int, input().split())
if (n < m): n, m = m, n
if (n % 2 != m % 2):
k -= 1
n -= 1
elif (n % 2 != k % 2):
k -= 2
n -= 1
m -= 1
print(-1 if k < n else k)


1036C - Classy Numbers

Tutorial
Solution with combinatorics (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

long long C[20][20];
long long pw[4];

long long cnk(int n, int k){
if (k < 0 || k > n) return 0;
return C[n][k];
}

long long get(int n, int lft){
long long tot = 0;
forn(i, lft + 1)
tot += cnk(n, i) * pw[i];
}

long long calc(long long x){
string s = to_string(x);

long long res = 0;
int cur = 3;
int n = s.size();

forn(i, n){
if (s[i] == '0') continue;
res += get(n - i - 1, cur);
--cur;
if (cur == -1) break;
res += get(n - i - 1, cur) * (s[i] - '1');
}

return res;
}

int main() {
forn(i, 20){
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729;
int T;
scanf("%d", &T);
forn(i, T){
long long L, R;
scanf("%lld%lld", &L, &R);
printf("%lld\n", calc(R + 1) - calc(L));
}
return 0;
}

Solution with precalc (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

vector<long long> res;

void brute(int pos, int cnt, long long cur){
if (pos == 18){
res.push_back(cur);
return;
}

brute(pos + 1, cnt, cur * 10);

if (cnt < 3)
for (int i = 1; i <= 9; ++i)
brute(pos + 1, cnt + 1, cur * 10 + i);
}

int main() {
brute(0, 0, 0);
res.push_back(1000000000000000000);

int T;
scanf("%d", &T);
forn(i, T){
long long L, R;
scanf("%lld%lld", &L, &R);
printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L)));
}
return 0;
}


1036D - Vasya and Arrays

Tutorial
Solution (Ajosteen)
#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;

int n, m;
int a[N], b[N];

int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", a + i);
scanf("%d", &m);
for(int i = 0; i < m; ++i) scanf("%d", b + i);

long long sum = 0;
for(int i = 0; i < n; ++i) sum += a[i];
for(int i = 0; i < m; ++i) sum -= b[i];
if(sum != 0){
puts("-1");
return 0;
}

int posa = 0, posb = 0;
int res = 0;
while(posa < n){
++res;
long long suma = a[posa++], sumb = b[posb++];

while(suma != sumb){
if(suma < sumb) suma += a[posa++];
else sumb += b[posb++];
}
}

printf("%d\n", res);
return 0;
}


1036E - Covered Points

Tutorial
Solution (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 1000 + 7;

struct seg{
int x1, y1, x2, y2;
seg(){};
};

struct line{
long long A, B, C;
line(){};
line(seg a){
A = a.y1 - a.y2;
B = a.x2 - a.x1;
C = -A * a.x1 - B * a.y1;
};
};

int n;
seg a[N];

int get(seg a){
int dx = a.x1 - a.x2;
int dy = a.y1 - a.y2;
return __gcd(abs(dx), abs(dy)) + 1;
}

long long det(long long a, long long b, long long c, long long d){
return a * d - b * c;
}

bool in(int x, int l, int r){
if (l > r) swap(l, r);
return (l <= x && x <= r);
}

bool inter(seg a, seg b, int& x, int& y){
line l1(a), l2(b);
long long dx = det(l1.C, l1.B, l2.C, l2.B);
long long dy = det(l1.A, l1.C, l2.A, l2.C);
long long d = det(l1.A, l1.B, l2.A, l2.B);
if (d == 0)
return false;
if (dx % d != 0 || dy % d != 0)
return false;
x = -dx / d;
y = -dy / d;
if (!in(x, a.x1, a.x2) || !in(y, a.y1, a.y2))
return false;
if (!in(x, b.x1, b.x2) || !in(y, b.y1, b.y2))
return false;
return true;
}

int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);

int ans = 0;
int x, y;
forn(i, n){
ans += get(a[i]);
set<pair<int, int>> pts;
forn(j, i)
if (inter(a[i], a[j], x, y))
pts.insert({x, y});
ans -= pts.size();
}

printf("%d\n", ans);
return 0;
}


1036F - Relatively Prime Powers

Tutorial
Solution (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int K = 100;
const int N = 100 * 1000 + 13;
const long long INF64 = 3e18;

int mu[K];

void precalc(){
static bool prime[K];
static int lst[K];

memset(prime, false, sizeof(prime));
forn(i, K) lst[i] = i;

for (int i = 2; i < K; ++i){
if (lst[i] == i) mu[i] = 1;
for (int j = 2 * i; j < K; j += i){
lst[j] = min(lst[j], lst[i]);
if (lst[j] == lst[i])
mu[j] = 0;
else
mu[j] = -mu[i];
}
}
}

int mx[K];

long long binpow(long long a, int b){
long long res = 1;
while (b){
if (b & 1){
if (res < INF64 / a) res *= a;
else return INF64;
}
if (b > 1){
if (a < INF64 / a) a *= a;
else return INF64;
}
b >>= 1;
}
return res;
}

long long calc(long long n){
int pw = 63 - __builtin_clzll(n);
for (int i = 3; i <= pw; ++i){
if (mu[i] == 0) continue;
while (binpow(mx[i], i) > n)
--mx[i];
}

long long res = n - 1;
for (int i = 2; i <= pw; ++i)
res -= mu[i] * (mx[i] - 1);

return res;
}

int get_sqrt(long long n){
int l = 1, r = 1000000000;
while (l < r - 1){
int m = (l + r) / 2;
if (m * 1ll * m <= n)
l = m;
else
r = m;
}
return (r * 1ll * r <= n ? r : l);
}

long long ans[N];

int main() {
precalc();
int T;
scanf("%d", &T);
vector<pair<long long, int>> q;

forn(i, T){
long long n;
scanf("%lld", &n);
q.push_back({n, i});
}

sort(q.begin(), q.end(), greater<pair<long long, int>>());
mx[3] = 1000000;
mx[4] = 31622;
mx[5] = 3981;
for (int i = 6; i < K; ++i)
mx[i] = 1000;

forn(z, T){
long long n = q[z].first;
mx[2] = get_sqrt(n);
ans[q[z].second] = calc(n);
}

forn(i, T)
printf("%lld\n", ans[i]);
return 0;
}


1036G - Sources and Sinks

Tutorial
Solution (BledDest)
#include <bits/stdc++.h>

using namespace std;

const int N = 1000043;

vector<int> g[N];
vector<int> gt[N];
vector<int> src;
vector<int> snk;
int reach[20];
int used[N];

void dfs(int x)
{
if(used[x]) return;
used[x] = 1;
for(auto y : g[x]) dfs(y);
}

int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 0; i < n; i++)
{
if(g[i].empty())
snk.push_back(i);
if(gt[i].empty())
src.push_back(i);
}
int cnt = src.size();
for(int i = 0; i < cnt; i++)
{
memset(used, 0, sizeof used);
dfs(src[i]);
for(int j = 0; j < cnt; j++)
if(used[snk[j]])
reach[i] ^= (1 << j);
}
bool ok = true;
{
int res = 0;
for(int j = 0; j < cnt; j++)
res |= reach[j];
int cnt2 = __builtin_popcount(res);
if(cnt2 < cnt1 || (cnt2 == cnt1 && cnt1 != 0 && cnt1 != cnt))
ok = false;
}
if(!ok)
puts("NO");
else
puts("YES");
}


• +44

 » 2 years ago, # | ← Rev. 2 →   +16 I found a strange thing in F. Two ACs codes output different result. Detail in https://codeforces.com/blog/entry/61728. Can anyone help me?
 » 2 years ago, # |   0 Can someone prove the author's solution for B?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 i thought about this problem lot after the contest.what i came up with is that there is 8 cases for m,n,k: odd/odd/odd, odd/odd/even....even/even/even. all cases reduce down to the odd/odd/odd case or the even/even/even case. we can see that it is possible to solve the odd/odd/odd or even/even/even case using all diagonal moves as long as m,n is reachable in k moves.for an example of "reduction", the even/odd/odd case reduces to the even/even/even case because you can "spend" one non-diagonal move in the n-direction. [1]the author's solution is basically "reducing" down all cases to o/o/o or e/e/e cases with mod. see my coded sol here: 42690270[1] in fact, the o/o/o case reduces down to the e/e/e case by spending 1 diagonal move
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 We can change the problem to this: you should use 1/-1/0 k times totally to get m and n respectively.(remember that m and n are nothing to do with) And according to the problem and greedy algorithm the num of 1/-1 should be as much as possible.for m we should at least use 1 m times and if km then we can add the combination of (1 and -1), then the left (m-k)%2(1 or none) should be 0. for n we do the same.so now for m and n, the num of 0 should be at least (m-k)%2 and (n-k)%2 respectively. And for the 0 in m, we must use a 1/-1 in n to construct a valid move (0,1) or (0,-1), the same for n. at last there are (m-k)%2+(n-k)%2 moves not diagonal, so the answer is k-(m-k)%2-(n-k)%2.
 » 2 years ago, # |   +26 Randomized solution for problem G: here
•  » » 2 years ago, # ^ |   0 cool.
•  » » 2 years ago, # ^ |   0 cool
 » 2 years ago, # |   0 Wasted 1 hour trying to solve a harder version of Problem C. I thought classy numbers were those number which had the number of distinct non zero digits <= 3. And when TC 2 and 3 were not passing, I tried so hard debugging.After successfully wasting 1 hour, read the question again and BAM!!
•  » » 2 years ago, # ^ |   0 what it mean prefix in the tutorial for C??
 » 2 years ago, # |   0 The data for G maybe too weak? I can easily hack my code.
 » 2 years ago, # |   +18 The problem A is so easy, but I solved it late because of my poor English and my poor wi-fi.
 » 2 years ago, # |   0 In problem E, Can anyone please give proof of why exactly GCD + 1 value will give integer co-ordinates?
•  » » 2 years ago, # ^ |   +3
•  » » » 2 years ago, # ^ |   0 Thanks ^_^
 » 2 years ago, # | ← Rev. 2 →   0 [Deleted]
 » 2 years ago, # | ← Rev. 4 →   0 http://codeforces.com/contest/1036/submission/42706346 can someone pls point out the mistake i am making. upd :: got it
 » 2 years ago, # |   0 In Problem G, it is possible to find for every sources all achievable sinks in a linear time. For this it is necessary to store in each visited vertex an integer (the set of bits of achievable sinks).
•  » » 2 years ago, # ^ |   0 Can you explain the approach behind recursion in problem C?
 » 2 years ago, # |   0 Can problem F be solved with some precalculations (generations of correct numbers), simular to problem C?
 » 2 years ago, # |   0 can anyone explain classy numbers editorial ??
 » 2 years ago, # |   0 there is a easy way to solve problem C with DP :) 42742195
•  » » 2 years ago, # ^ |   0 It seems to be an interesting approach, but I don't really understand it. Could you please explain it briefly?
•  » » » 2 years ago, # ^ |   0 f(i,j) means The i th bit of a number(unit's digit,ten's digit...) and already has j non-zero digits.DP uses flag to control upper bound.If it is not the upper bound,we can remember the result of f(x,y).(That's why I initialize f to -1 and update f(x,y) when flag=0).f(x,y) will be accessed multiple times, so we can speed it up by remember it .My English is poor( I use the google translate QAQ ).
•  » » 2 years ago, # ^ |   0 Thanks.I can't understand about how (!flag&&~f[x][y]) works,what's mean ?it's mean if f[x][y] has been calculated ,then return f[x][y]? to be honest i want to use pinyin.
 » 2 years ago, # |   0 Why dont we use -C instead of C? I read in internet that the formula will use -C instead of C? I mean this fragment: long long dx = det(l1.C, l1.B, l2.C, l2.B); long long dy = det(l1.A, l1.C, l2.A, l2.C);
•  » » 2 years ago, # ^ |   +3 By the properties of determinant det(-a, b, -c, d) = det(a, -b, c, -d) = -det(a, b, c, d)
•  » » » 2 years ago, # ^ |   0 Ahh it is used then when he does: x = -dx / d; y = -dy / d; right?
 » 2 years ago, # |   0 Why is Problem A tagged with FFT ? Is there a solution with FFT as well ?
•  » » 2 years ago, # ^ |   0 Nope, it means an idiot is going around and trolling.
 » 2 years ago, # |   0 very very good~ !!
 » 2 years ago, # |   -6 E has a tag "fft". Can it be done using FFT too? If yes, then how?
•  » » 2 years ago, # ^ |   0 Honestly, do you even know how to use FFT in the first place?
•  » » » 2 years ago, # ^ |   0 I do. I'm looking for more questions to practice it.
 » 2 years ago, # |   0 For problem 1036E — Covered Points , can anybody explain what's special with the test 14? I've seen some people failing this test.
 » 2 years ago, # |   0 Could someone explain how mobius function could be used in problem F. All I understood is that we are trying to remove the bad elements from the answer. Basically, could someone explain me the formula?
 » 2 years ago, # |   0 in problem G, how about a 4-vertex graph: 1->2, 3->2, 3->4 ??? It's obvious that 1 is a source but the set of sink it can reach is just {2}???
 » 2 years ago, # |   0 is there a proof for problem b ?
 » 2 years ago, # |   0 Can someone explain the brute force generation for C
•  » » 2 years ago, # ^ |   0 pos represents the number of digits,cnt represents count of non-zero digits and cur represents the value generated. first we take the generated number and multiply by 10 and increasing number of digits. if a number is classy number then its multiple of 10 will also be a classy number. then we check if the number has less than 3 non-zero digits or not.if it has less than 3 non-zero digits then we can put any number between 1 to 9 at units place and generate another classy number(multiply by 10 and adding the number). we also increase the count of non-zero digit.
•  » » » 9 months ago, # ^ |   0 I was really confused. thanks for the explanation.
 » 23 months ago, # | ← Rev. 3 →   0 please can anyone explain the formula in problem C, i dont know why it return exactly the beautiful numbers on [1,X), why cur-- like that, that means for(int cur = 3; cur>=0; cur --) , i think i'll insert s[i] in a set so that its size is cur ... A lot of things i cant understand. I've read PikMike's code and the formula for hours. Help me please.
 » 15 months ago, # |   0
 » 15 months ago, # |   +26 The solution to G reminds me of Hall's marriage theorem, and I finally figured out how to solve it in polynomial time.Take the graph of sources and reachable sinks. If no perfect matching exists, by Hall's marriage theorem, there is a nonempty proper subset of sources $X$ such that $|X|>|f(X)|$, so the answer is NO. Otherwise, we need to ensure that $|X|<|f(X)|$. This means $f(X)$ has sinks besides the ones matched to sources in $X$. Connect each sink to the source it is matched to in the perfect matching. The answer is YES if and only if the the resulting graph is strongly connected.Code: 67053099
 » 14 months ago, # |   0 Can anyone explain F with little more details ?