### Motarack's blog

By Motarack, history, 21 month(s) ago,

Hello,

The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.

Code
Code
Code
Code
Code
Code
Code
Code
Code
Code
Code
Spoiler!
Code

• +32

 » 21 month(s) ago, # |   0 omg I didn't notice that the input in problem B (primes) is always a prime number , I solved it by building sieve array :D :D .still waiting for F editorial .very nice problems , thank you so much .
•  » » 21 month(s) ago, # ^ |   +3 I also did the same:)
 » 21 month(s) ago, # |   +3 Need help in I Can we do this by using stack? 56522390
•  » » 21 month(s) ago, # ^ |   0 yes, you can. I did the same but using vector instead of stack. but you have the same mistake I had done. when you see like this bracket "(" you push the next element, this is wrong. imagine 3(10(15)) so you push 1 instead of 10 and again 1 instead of 15. so you need to get the whole number. my solution if you want to check how I solve this problem 56524350
•  » » » 21 month(s) ago, # ^ |   0 Ohk, I got it nowThanks for the help
 » 21 month(s) ago, # |   +3 Can anyone help me in understanding the concept behind the O(N) solution of problem K. I know it is a fairly common problem but I cannot seem to grasp the idea behind it. Can anyone please help me? It will really help me out in solving other problems like this.
•  » » 21 month(s) ago, # ^ |   0 Well, the idea is pretty straightforward, we just ignore the numbers in the array which have their 'i' th bit as zero, because 0 ^ 0 = 0. And we subtract the subsets formed by these numbers from the total subset possible, and hence the formula.
 » 21 month(s) ago, # |   0 Can we do J using matrix exponential? There is a trick which calculates number of walks of length k in a graph by raising the power of adjacency matrix to k.
•  » » 21 month(s) ago, # ^ |   +1 Yes we can by taking the sub-graph that we're only allowed to walk on from the original graph, but it has worse complexity, $O(m^3 \log{k}$).
•  » » » 21 month(s) ago, # ^ |   +8 Actually, this solution, even if the limits are made smaller, will be wrong because we want the sum of matrix[0][0] for all powers from 2 to min(m,k). so using matrix exponentiation has a complexity of $O(m^3min(m,k))$
•  » » » » 21 month(s) ago, # ^ |   +4 we can add another row and column to the adjacency matrix and let one of the new cells be responsible for the sum of cell (0,0).
•  » » » » » 21 month(s) ago, # ^ |   0 yea sure that works.
 » 21 month(s) ago, # |   0 For Question F, we can also find the answer by applying dfs and taking the post order traversal of graph, right?
 » 20 months ago, # |   0 I'm new here but wouldn't ... int main() { long a, b; cin >> a >> b; double x = log(a)/log(b); long xi = x+1; cout << xi << endl; return 0; } ... be an easier way to solve C (Dolls)?
•  » » 20 months ago, # ^ |   0 That's another way to solve it, the intended solution is for people that don't know much about the log function.
 » 6 weeks ago, # | ← Rev. 7 →   +10 In problem F, we wrote this code Code#include using namespace std; #define int int64_t #define ar array #define pii pair #define pb push_back #define vt vector #define For(i, n) for (int i = 0; i < n; i++) #define Rev(i, n) for (int i = n - 1; i >= 0; i--) #define FOR(i, n) for (int i = 1; i <= n; i++) #define REV(i, n) for (int i = n; i >= 1; i--) #define Rep(i, a, b) for (int i = a; i <= b; i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define msb(x) (int) (31 - __builtin_clz(x)) template using mxpq = priority_queue; template using mnpq = priority_queue, greater>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int a, int b) { return uniform_int_distribution(a, b)(rng); } const int mod = 1e9 + 7; const int INF = 1e18L + 5; const int N = 2e5 + 5; const long double eps = 1e-9; #define pdd pair struct ray { long double X, Y; long double cross(ray other) { return X * other.Y - Y * other.X; } }; void solve() { int n; cin >> n; const long double pi = acos(-1); vt> a(n); for (auto &p : a) { cin >> p[0] >> p[1]; int an, r; cin >> an >> r; int p2 = an - r, p3 = an + r; p2 = (p2 + 360) % 360; p3 = (p3 + 360) % 360; if (p2 > p3) { swap(p2, p3); } p[2] = p2 * pi / 180, p[3] = p3 * pi / 180; } vt> g(n); vt indeg(n, 0); queue q; for (int i = 0; i < n; i++) { auto& [x, y, l, r] = a[i]; ray r1, r2; r1.X = cos(l), r1.Y = sin(l); r2.X = cos(r), r2.Y = sin(r); for (int j = 0; j < n; j++) { if (i == j) { continue; } ray r3; r3.X = a[j][0] - x, r3.Y = a[j][1] - y; long double v1 = r1.cross(r3), v2 = r2.cross(r3); if ((v1 + eps > 0 && v2 - eps < 0)) { g[i].pb(j); indeg[j]++; } } } for (int i = 0; i < n; i++) { if (indeg[i] == 0) { q.emplace(i); } } vt print; while (!q.empty()) { int u = q.front(); q.pop(); print.pb(u + 1); for (int v : g[u]) { indeg[v]--; if (indeg[v] == 0) { q.emplace(v); } } } if (sz(print) < n) { cout << -1 << '\n'; return; } for (auto& it : print) { cout << it << ' '; } } signed main() { #ifdef LOCAL freopen("in", "r", stdin); freopen("out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); int t = 1; FOR(tt, t) solve(); return 0; } We are getting WA on test case 128, and we are unable to see if we have done a error in logic or if there is an error in handling precision.We have written a very neat code so that you won't have trouble in understanding and debugging it. Someone please have a look at the code and help us out.
•  » » 6 weeks ago, # ^ |   +13 Are you sure this is correct: if (p2 > p3) { swap(p2, p3); } won't that give you the opposite of what you want?
•  » » » 6 weeks ago, # ^ | ← Rev. 4 →   +7 Yes we have realised that we were doing just the opposite. Now we have corrected our code but still we are getting WA on test case 133. What else do you think could be wrong? Code #include using namespace std; #define int int64_t #define ar array #define pii pair #define pb push_back #define vt vector #define For(i, n) for (int i = 0; i < n; i++) #define Rev(i, n) for (int i = n - 1; i >= 0; i--) #define FOR(i, n) for (int i = 1; i <= n; i++) #define REV(i, n) for (int i = n; i >= 1; i--) #define Rep(i, a, b) for (int i = a; i <= b; i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define msb(x) (int) (31 - __builtin_clz(x)) template using mxpq = priority_queue; template using mnpq = priority_queue, greater>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int a, int b) { return uniform_int_distribution(a, b)(rng); } const int mod = 1e9 + 7; const int INF = 1e18L + 5; const int N = 2e5 + 5; const long double eps = 1e-13; #define pdd pair struct ray { long double X, Y; long double cross(ray other) { return X * other.Y - Y * other.X; } }; void solve() { int n; cin >> n; const long double pi = acos(-1); vt> a(n); for (auto &p : a) { cin >> p[0] >> p[1]; int an, r; cin >> an >> r; int p2 = an - r, p3 = an + r; p[2] = p2 * pi / 180, p[3] = p3 * pi / 180; } vt> g(n); vt indeg(n, 0); queue q; for (int i = 0; i < n; i++) { auto& [x, y, l, r] = a[i]; assert(r - l < 180); ray r1, r2; r1.X = cos(l), r1.Y = sin(l); r2.X = cos(r), r2.Y = sin(r); for (int j = 0; j < n; j++) { if (i == j) { continue; } ray r3; r3.X = a[j][0] - x, r3.Y = a[j][1] - y; long double v1 = r1.cross(r3), v2 = r2.cross(r3); if (v1 + eps > 0 && v2 - eps < 0) { g[i].pb(j); indeg[j]++; } } } for (int i = 0; i < n; i++) { if (indeg[i] == 0) { q.emplace(i); } } vt print; while (!q.empty()) { int u = q.front(); q.pop(); print.pb(u + 1); for (int v : g[u]) { indeg[v]--; if (indeg[v] == 0) { q.emplace(v); } } } if (sz(print) < n) { cout << -1 << '\n'; return; } for (auto& it : print) { cout << it << ' '; } } signed main() { #ifdef LOCAL freopen("in", "r", stdin); freopen("out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; FOR(tt, t) solve(); return 0; }
•  » » » » 6 weeks ago, # ^ |   +4 try this: 2 0 0 0 0 1 0 0 0
•  » » » » » 6 weeks ago, # ^ |   0 Okay Thanks we understood where we are going wrong. Thank you very much for helping us out.