### jonathanirvings's blog

By jonathanirvings, history, 4 weeks ago, ,

Hi,

We would like to invite you to participate in the live (with 30-minute delay) online mirror contest of The 2019 ICPC Asia Jakarta Regional Contest (our regional website, our regional in ICPC website, official contest portal) this weekend. The online mirror contest will start on Oct/27/2019 06:30 (Moscow time).

The contest consists of several problems and you can solve them in 5 hours.

See you on top of the leaderboard.

UPD1: Thanks for participating. The problems should be available for upsolving. The soft-copy of the problem analysis (the same as the one distributed to all contestants during the awarding ceremony) is available here.

• +217

 » 4 weeks ago, # | ← Rev. 2 →   +47 Too bad that it clashes with my FHC schedule. Anyway, I think Jakarta had the finest problems in East Asia ICPC last year. It would be a good practice opportunity.
•  » » 4 weeks ago, # ^ |   +14 Thanks for the kind testimony, and congrats once again for winning it last year! :)Ah, I just realized that FBHC finals clashes with the regional. Maybe I should be thankful that I missed it by penalties now, otherwise I would have a big dilemma.Good luck for the finals! :)
•  » » 4 weeks ago, # ^ |   0 Just curious, what do you think about problems in Vietnam regional last year? And Vietnam 2017 problems.Sorry for off-topic comment :D
•  » » » 4 weeks ago, # ^ |   +8 About 2018, I didn't like harder problems (except G). But problems in 2016/2017 was good, so I can recommend Vietnam contest :)
 » 4 weeks ago, # |   +45 The link to timeanddate.com redirects to 27th October of 2018. I guess someone is still living in 2018.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +44 Sometimes I am wondering why I can be a red coder when I still make this kind of careless mistakes. This is why we shouldn't copy-paste things (I copy-pasted the timeanddate URL from last year).Anyway, thanks for pointing it out. It is fixed now. Take my upvote!
 » 4 weeks ago, # | ← Rev. 2 →   +13 Please change the link to https://codeforces.com/contests/1252 instead of https://codeforces.com/contest/1252 . Right now it shows "contest has not started".People can directly register by visiting the first link.
 » 4 weeks ago, # |   -9 Maybe I'm a new of Codeforces ... Could you tell me if I participate as a team member , will my personal rating change after the contest ... ?
•  » » 4 weeks ago, # ^ |   +17 I think it's unrated.
 » 4 weeks ago, # |   +16 Just curious if it is rated? if rated how would the rating mechanism work for a team against individual?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 I was just considering this question and wanted to know how rating will be calculated. Obviously it should be fairer if unrated. Thank you :-).
 » 3 weeks ago, # |   -39 Is it rated?
•  » » 3 weeks ago, # ^ |   +12 no
 » 3 weeks ago, # |   -43 I hope no DDOS attack would happen
 » 3 weeks ago, # |   +26 I am getting this message please fix it "Can't read or parse problem descriptor"
 » 3 weeks ago, # |   0 Good luck for all the contestants! :)
 » 3 weeks ago, # |   0 Can we see the resolver?
 » 3 weeks ago, # | ← Rev. 3 →   0 How to solve problem E? We attempted to solve it using system of difference constraints with SPFA and got TLE. Thanks in advance.
•  » » 3 weeks ago, # ^ |   +13 Try to maintain feasible intervals backward and then get result forward based on the feasible intervals.
•  » » » 3 weeks ago, # ^ |   0 Thanks. I think I nailed it. Orz%%%
•  » » 13 days ago, # ^ |   0 Hi, could you help me find where I am going wrong in case of Question C (even Path). Here is my code: https://ideone.com/9w587e I have implemented with the same logic as in the editorial, i.e. pre-calculating the parity of the given array R and C, but I am getting TLE in test case 17 and gone through every bit of code but couldn't find where the problem is. The time complexity is also O(4N + Q) or just O(N+Q). Thanks in advance!
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone explain the solution to J? I implemented a greedy idea only to get WA on testcase 20.
•  » » 3 weeks ago, # ^ |   +5 The main complexity in J is how to place the type-3 blocks. I decided to iterate over number of type-3 blocks to place, and then for each possibility place the blocks so that we get the fewest number of odd segments of soil using a dp (because we can fill even segments with type-2s completely, they are strictly better than odd segments).After the type-3 blocks are placed you can place type-1 and type-2 greedily.
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   +1 We need at most O(number of rocks) type-1.It turns out the test cases are weak, lol.
•  » » » 3 weeks ago, # ^ | ← Rev. 6 →   0 may i look at your code? i couldn't see the other's code. it's for learning purpose since i keep stucking on test case 23 after debugging on test case 11,19 & 22
•  » » 2 weeks ago, # ^ |   0 Hi, could you help me find where I am going wrong in case of Question C (even Path). Here is my code: https://ideone.com/9w587e I have implemented with the same logic as in the editorial, i.e. pre-calculating the parity of the given array R and C, but I am getting TLE in test case 17 and gone through every bit of code but couldn't find where the problem is. The time complexity is also O(4N + Q) or just O(N+Q). Thanks in advance!
 » 3 weeks ago, # |   +6 How to solve problem K?
•  » » 3 weeks ago, # ^ |   +4 For a subsequence $[l,r]$, you can count how many $A$ and $B$ in first element and second element of $f(l,r,A,B)$. Let them be $x_1,y_1$ and $x_2,y_2$. For example, with substring $ABA$, $x_1=2,y_1=3,x_2=1,y_2=2$.For query type $2$, use segment tree to calculate $x_i$ and $y_i$ of subsequence $[l,r]$. To build the tree, we need to combine $x_i$ and $y_i$ of two segment, which could be figured out by draft.For query type $1$, use lazy update on segment tree. When we flip a segment odd number of times, simply $swap(x_1, y_2)$ and $swap(x_2, y_1)$.
•  » » » 3 weeks ago, # ^ |   0 Can I see your code ? Thank you very much!
•  » » » » 3 weeks ago, # ^ |   +4 Yes#include using namespace std; const int N = 1e5 + 8; typedef long long ll; ll MOD = 1e9 + 7; struct node { ll x1, y1, x2, y2; bool lazy; node(ll x1 = 1, ll y1 = 0, ll x2 = 0, ll y2 = 1) { this->x1 = x1; this->y1 = y1; this->x2 = x2; this->y2 = y2; lazy = false; } }; node t[N << 2]; char s[N]; int n, q; void apply(node &a, node b, node c) { a.x1 = (b.x1 * c.x1 + b.y1 * c.x2) % MOD; a.y1 = (b.x1 * c.y1 + b.y1 * c.y2) % MOD; a.x2 = (b.x2 * c.x1 + b.y2 * c.x2) % MOD; a.y2 = (b.x2 * c.y1 + b.y2 * c.y2) % MOD; } void build(int k, int l, int r){ if (l == r) { if (s[l] == 'A') { t[k].x1 = t[k].y1 = t[k].y2 = 1; t[k].x2 = 0; } else { t[k].x1 = t[k].x2 = t[k].y2 = 1; t[k].y1 = 0; } return; } int m = (l + r) >> 1; build(k << 1, l, m); build(k << 1 ^ 1, m + 1, r); apply(t[k], t[k << 1 ^ 1], t[k << 1]); } void lazy(int k, int l, int r) { if (t[k].lazy) { swap(t[k].x1, t[k].y2); swap(t[k].x2, t[k].y1); if (l < r) { t[k << 1].lazy ^= 1; t[k << 1 ^ 1].lazy ^= 1; } t[k].lazy = false; } } void update(int k, int l, int r, int x, int y) { lazy(k, l, r); if (l > y || r < x) return; if (l >= x && r <= y) { t[k].lazy ^= 1; lazy(k, l, r); return; } int m = (l + r) >> 1; update(k << 1, l, m, x, y); update(k << 1 ^ 1, m + 1, r, x, y); apply(t[k], t[k << 1 ^ 1], t[k << 1]); } node get(int k, int l, int r, int x, int y) { lazy(k, l, r); if (l > y || r < x) return node(); if (l >= x && r <= y) return t[k]; int m = (l + r) >> 1; node t1 = get(k << 1, l, m, x, y); node t2 = get(k << 1 ^ 1, m + 1, r, x, y); node t0; apply(t0, t2, t1); return t0; } int main() { ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen(".inp", "r", stdin); freopen(".out", "w", stdout); #endif cin >> n >> q; cin >> s + 1; build(1, 1, n); while (q--) { int id, l, r; cin >> id >> l >> r; if (id == 1) { update(1, 1, n, l, r); } else { ll a, b; cin >> a >> b; node t0 = get(1, 1, n, l, r); ll A = (t0.x1 * a + t0.y1 * b) % MOD; ll B = (t0.x2 * a + t0.y2 * b) % MOD; cout << A << " " << B << endl; } } } 
•  » » » » » 3 weeks ago, # ^ |   0 Can you explain the x1 y1 x2 y2 in detail? Thanks in advance!
•  » » » » » » 3 weeks ago, # ^ |   0 Look at the function in the statement. The return value is $(A,B)$. $x_1,y_1$ are number of original $A$ and $B$ in $A$ returned, $x_2,y_2$ are number of original $A$ and $B$ in $B$ returned.
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Thank you ！The x1 y1 x2 y2 is like a 2 x 2 matrix . I try to use the segment tree to maintain the multiplication of the matrix,but I don't know how to change the matrix when the we flip a segment odd number of times. Now , I know it. If we flip a segment odd number of times , actually it's the transpose of this matrix. Thank you.
•  » » » » » » » 3 weeks ago, # ^ |   0 ok but i can't understand the transition or combinations of nodes in Segment Tree.ej why ( a.x1 = (b.x1 * c.x1 + b.y1 * c.x2) % MOD; )
•  » » » » » » » » 3 weeks ago, # ^ |   +3 For a segment $[l,r]$, $f(l,r,A,B)=(x_1\times A+y1\times b, x_2\times A + y_2\times B)=(A',B')$When combine segment $[l_2,r_2]$ next to $[l_1,r_1]$ and , $A'$ and $B'$ of the first segment become $A$ and $B$ of input of $f(l_2,r_2,A,B)$. You can make some drafts to figure out the equations.
•  » » 3 weeks ago, # ^ |   +3 use sqrt decomposition!
•  » » » 12 days ago, # ^ |   0 Hi I try to use sqrt decomposition to Solve this problem，but I have some problems about 1 L R operation. if a full segment toggled,I try to change the coefficient of A B but if we don't change the full segment,we will fail on later query. For example：a3 a4 a5 as a full toggled segment,but if we meet a query a4 a5 a6 a7 a8 we will get WA because we don't update a4 a5 By the way i try to use naive method but WA on Test2,can you help me?,thanks in advance. Code/* * Author: Hemengjie * Time: 2019-11-06 15:23:30 **/ #include using namespace std; #define ll long long #define pii pair const int MOD = 1e9 + 7; const int N = 1e5 + 50; char str[N]; pii outa[N], outb[N]; int seg[N], L[N], R[N]; void change(int segnum) { outa[segnum] = {1, 0}, outb[segnum] = {0, 1}; for (int i = L[segnum]; i <= R[segnum]; i++) { if (str[i] == 'A') { outa[segnum].first += outb[segnum].first; outa[segnum].second += outb[segnum].second; } else { outb[segnum].first += outa[segnum].first; outb[segnum].second += outa[segnum].second; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, Q; scanf("%d%d", &n, &Q); scanf("%s", str); int seg_cnt = sqrt(n); int len = n / seg_cnt; for (int i = 0; i < seg_cnt; i++) { outa[i] = {1, 0}, outb[i] = {0, 1}; L[i] = i * len, R[i] = (i + 1) * len - 1; for (int j = i * len; j < (i + 1) * len; j++) { seg[j] = i; if (str[j] == 'A') { outa[i].first += outb[i].first; outa[i].second += outb[i].second; } else { outb[i].first += outa[i].first; outb[i].second += outa[i].second; } } } if (!seg[n]) { outa[seg_cnt] = {1, 0}, outb[seg_cnt] = {0, 1}; L[seg_cnt] = seg_cnt * len, R[seg_cnt] = n - 1; for (int i = seg_cnt * len; i < n; i++) { seg[i] = seg_cnt; if (str[i] == 'A') { outa[seg_cnt].first += outb[seg_cnt].first; outa[seg_cnt].second += outb[seg_cnt].second; } else { outb[seg_cnt].first += outa[seg_cnt].first; outb[seg_cnt].second += outa[seg_cnt].second; } } seg_cnt++; } while (Q--) { int casenum, l, r; scanf("%d%d%d", &casenum, &l, &r); l--, r--; if (casenum == 1) { for (int i = l; i <= R[seg[l]]; i++) { if (str[i] == 'A') str[i] = 'B'; else str[i] = 'A'; } change(seg[l]); for (int i = seg[l] + 1; i <= seg[r] - 1; i++) { pii temp = outa[i]; outa[i].first = outb[i].second, outa[i].second = outb[i].first; outb[i].first = temp.second, outb[i].second = temp.first; for (int j = L[i]; j <= R[i]; j++) { if (str[j] == 'A') str[j] = 'B'; else str[j] = 'A'; } } for (int i = L[seg[r]]; i <= r; i++) { if (str[i] == 'A') str[i] = 'B'; else str[i] = 'A'; } change(seg[r]); } else { ll a, b, temp; scanf("%lld%lld", &a, &b); for (int i = l; i <= R[seg[l]]; i++) { if (str[i] == 'A') a = (a + b) % MOD; else b = (b + a) % MOD; } for (int i = seg[l] + 1; i <= seg[r] - 1; i++) { temp = a; a = (outa[i].first * a + outa[i].second * b) % MOD; b = (outb[i].first * temp + outb[i].second * b) % MOD; } for (int i = L[seg[r]]; i <= r; i++) { if (str[i] == 'A') a = (a + b) % MOD; else b = (b + a) % MOD; } cout << a << " " << b << endl; } } //system("pause"); return 0; } 
•  » » » » 11 days ago, # ^ |   0 Update: I solve the problem in sqrt decomposition. 64368399 but 2948ms.....
•  » » 13 days ago, # ^ |   -8 Hi, could you help me find where I am going wrong in case of Question C (even Path). Here is my code: https://ideone.com/9w587e I have implemented with the same logic as in the editorial, i.e. pre-calculating the parity of the given array R and C, but I am getting TLE in test case 17 and gone through every bit of code but couldn't find where the problem is. The time complexity is also O(4N + Q) or just O(N+Q). Thanks in advance!
 » 3 weeks ago, # |   0 how and where to submit the solutions if we want to upsolve???
 » 3 weeks ago, # | ← Rev. 2 →   0 Could someone give me advice on how to solve problem G ?EDIT: Solved using segment tree
•  » » 3 weeks ago, # ^ | ← Rev. 7 →   0 i keep getting WA on test case 2. could you please help me to find my mistake? i couldn't find my bug.EDIT: Solved, i did a silly mistake, i thought that Ai would be in decreasing order, i didn't read the problem carefully
 » 3 weeks ago, # |   +4 Could someone provide insights on problem H? I got stuck on test case 5 with my solution: https://ideone.com/at2GS0 .
•  » » 3 weeks ago, # ^ |   +4 I think it is the accuracy problem of floating point numbers.
•  » » » 3 weeks ago, # ^ |   0 can you review this.. Stuck on test case 5 Code
•  » » » » 3 weeks ago, # ^ |   +4 I think you made the same mistake as I: relying on a floating point value instead of sticking with integers, which led to some rounding error. This is a diff of my AC code and a previous version of it which also got WA on test case 5: https://www.diffchecker.com/sckBvjUO .
•  » » 3 weeks ago, # ^ |   +1 you need long double
•  » » » 3 weeks ago, # ^ |   0 Can you tell why we needed to use long double instead of double?
•  » » » » 3 weeks ago, # ^ |   +4 this test data: 1 999999999 999999999 if you use double,your answer will lose 0.5
 » 3 weeks ago, # |   0 can anyone give me one small test case for k? I use square root decomposition .here my solution
•  » » 3 weeks ago, # ^ |   0 This test case ,your output is different with mine.Click me
 » 3 weeks ago, # | ← Rev. 3 →   +4 Sorry if I misunderstood something. But this contest was not in gym, right? So why I could not see another team 's code?
 » 3 weeks ago, # |   0 Can someone share the code for problem J The Prade ... Thanks in advance
 » 3 weeks ago, # |   0 Can someone explain me question no B...
 » 3 weeks ago, # |   +4 where can I find the solution
 » 3 weeks ago, # |   +23 Will the submissions be visible?
 » 3 weeks ago, # |   +5 pls someone write editorial blog, it will help in upsolve the problem..
•  » » 3 weeks ago, # ^ |   0 The judge has shared problem analysis of the contest in their github. The link is already added below the Contest Material tab when you open a problem from the contest.https://github.com/jonathanirvings/icpc-jakarta-2019/blob/master/problem_analysis.pdf
•  » » » 3 weeks ago, # ^ |   0 thanks..
 » 3 weeks ago, # |   +5 How to solve problem I?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +5 The annoying problem, no innovative idea. The obvious thing we notice is just find the way to reach the border. Other thing I can see is that to go through two touching circles we need to follow their tangent. So we can draw lines between each pairs of circle then get some intersections,...
•  » » » 3 weeks ago, # ^ |   +8 You can draw something like voronoi diagram (but not really) by defining a half-plane using a separator between two circles (for example, a line that's exactly between two circles). By using this you can find some point from this graph you can get to and then traverse it until you can get to the end point.
 » 3 weeks ago, # |   0 explain me solve problem H?? please
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 sorry. I'm not use long double type so WA test 5
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 in fact,before i found the problem，i had WA 5 times
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).
 » 3 weeks ago, # |   +7 Please make the test cases visible.
 » 3 weeks ago, # |   0 Please make testcases and other's solutions available
 » 3 weeks ago, # |   0 Can you please make all sources visible?
 » 3 weeks ago, # |   -10 please anyone provide the code for problem C.. Thanks in advance.
 » 3 weeks ago, # |   0 I try a different DP way to solve problem B but it cant pass the test 5. Can anyone make the test cases visible QAQ.
 » 2 weeks ago, # |   0 I need help on problem H, got WA on test 40. Here is my code. I have tried on my own test case with 8000 numbers of N, but did not spot any mistake. what do i miss?!!
•  » » 2 weeks ago, # ^ |   0 Line 64, why do you compare with only the last one?
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 line 64 is the only one left out from "solve" function, the other have been compared in line 32.Never mind about my question. Anyway, finally got it solved. Thanks for your attention. :)
 » 2 weeks ago, # |   0 For Problem L,Can someone explain the solution in Tutorial?Alternatively, the easier method is to run the maximum cardinality bipartite matching on set B ﬁrst,before running it on set A. Initially, we have 3 m1 and 3 m2,If at matching on Set B we use at least 2 m2,then we can't use the left m1 and m2 to match on Set A.Is it right?
 » 10 days ago, # |   +5 Why are the test cases and solutions still not visible!?
 » 9 days ago, # | ← Rev. 2 →   0 why TLE? problem Kis that because of using vectors in representing the matrices or what? Code#pragma GCC optimize ("unroll-loops") #include using namespace std; #define ff first #define ss second #define all(v) (v.begin(), v.end()) #define row vector #define matrix vector #define ROWS(v) (v).size() #define COLS(v) (v)[0].size() #define DBG1(x) cerr<<#x<<":"<<(x)<<'\n'; #define DBG2(x, y) cerr<<#x<<":"<<(x)<<" "<<#y<<":"<<(y)<<'\n'; #define DBG3(x,y,z) cerr<<#x<<":"<<(x)<<" "<<#y<<":"<<(y)<<" "<<#z<<":"<<(z)<<'\n'; typedef long long lld; const int N = 1e5 + 9, OO = 0x3f3f3f3f, MOD = 1e9 + 7; int n, q; char s[N]; matrix TR[N<<2], arr[2]; bool lazy[N<<2]; matrix ans(2, row(2, 0)), c(2, row(2, 0)); matrix identity = {{1, 0}, {0, 1}}; matrix mul(const matrix& a, const matrix& b){ c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD; c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD; c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD; c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD; return c; } inline void edit(int p){ swap(TR[p][0][0], TR[p][1][1]); swap(TR[p][0][1], TR[p][1][0]); } inline void push(int p){ lazy[p] = 0; edit(p*2); lazy[p*2] ^= 1; edit(p*2+1); lazy[p*2+1] ^= 1; } matrix build(int l = 0, int r = n-1, int p = 1){ if(l == r) return TR[p] = arr[s[l]-'A']; int m = (l + r) >> 1; return TR[p] = mul(build(l, m, p*2), build(m+1, r, p*2+1)); } matrix update(int l, int r, int ql, int qr, int p = 1){ if(r < ql || l > qr) return TR[p]; if(l >= ql && r <= qr){ edit(p); lazy[p] ^= 1; return TR[p]; } if(lazy[p]) push(p); int m = (l + r) >> 1; return TR[p] = mul(update(l, m, ql, qr, p*2), update(m+1, r, ql, qr, p*2+1)); } matrix get(int l, int r, int ql, int qr, int p = 1){ if(r < ql || l > qr) return identity; if(l >= ql && r <= qr) return TR[p]; if(lazy[p]) push(p); int m = (l + r) >> 1; return mul(get(l, m, ql, qr, p*2), get(m+1, r, ql, qr, p*2+1)); } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); //fastin; scanf("%d %d", &n, &q); scanf("%s", s); arr[0] = {{1, 0}, {1, 1}}; arr[1] = {{1, 1}, {0, 1}}; build(); while(q--){ int t, l, r; scanf("%d %d %d", &t, &l, &r); --l, --r; if(t == 1) update(0, n-1, l, r); else{ lld a, b; scanf("%lld %lld", &a, &b); ans[0][0] = a; ans[0][1] = b; ans = mul(ans, get(0, n-1, l, r)); printf("%lld %lld\n", ans[0][0], ans[0][1]); } } return 0; } 
•  » » 9 days ago, # ^ | ← Rev. 2 →   +21 j
 » 5 days ago, # |   0 Test cases for problem F cannot be more broken. You don't need to consider subtrees isomorphism in any way. Basically, if you're a tree centroid, then you're okay. Just maximize with its number of children, and you'll pass.
 » 5 days ago, # |   0 What's wrong with this code. It fails on test-5 of Even Path. https://codeforces.com/contest/1252/submission/64762718