Live online mirror of The 2019 ICPC Asia Jakarta Regional Contest

5 years 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! :)

→ Reply

I_love_Hoang_Yen

5 years ago, # ^ |

Just curious, what do you think about problems in Vietnam regional last year? And Vietnam 2017 problems.

Sorry for off-topic comment :D

→ Reply

ko_osaga

5 years ago, # ^ |

About 2018, I didn't like harder problems (except G). But problems in 2016/2017 was good, so I can recommend Vietnam contest :)

→ Reply

Tanzir5

5 years ago, # |

+45

The link to timeanddate.com redirects to 27th October of 2018. I guess someone is still living in 2018.

→ Reply

5 years 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!

→ Reply

aryanc403

5 years ago, # |

← Rev. 2 →

+13

Please change the link to https://codeforces.net/contests/1252 instead of https://codeforces.net/contest/1252 . Right now it shows "contest has not started".
People can directly register by visiting the first link.

→ Reply

Nanjo_Qi

5 years 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 ... ?

→ Reply

ouuan

5 years ago, # ^ |

+17

I think it's unrated.

→ Reply

huzaifa242

5 years ago, # |

+16

Just curious if it is rated? if rated how would the rating mechanism work for a team against individual?

→ Reply

Nanjo_Qi

5 years ago, # ^ |

← Rev. 2 →

I was just considering this question and wanted to know how rating will be calculated. Obviously it should be fairer if unrated. Thank you :-).

→ Reply

deleted2

5 years ago, # |

-39

Is it rated?

→ Reply

Mahdivelayatipour

5 years ago, # ^ |

+12

→ Reply

VivaanGupta

5 years ago, # |

+26

I am getting this message please fix it "Can't read or parse problem descriptor"

→ Reply

SorahISA

5 years ago, # |

Can we see the resolver?

→ Reply

codgician

5 years ago, # |

← Rev. 3 →

How to solve problem E? We attempted to solve it using system of difference constraints with SPFA and got TLE. Thanks in advance.

→ Reply

-14

5 years ago, # ^ |

+13

Try to maintain feasible intervals backward and then get result forward based on the feasible intervals.

→ Reply

codgician

5 years ago, # ^ |

Thanks. I think I nailed it. Orz%%%

→ Reply

kurzgesagt

5 years ago, # ^ |

← Rev. 2 →

[deleted]

→ Reply

TheOneYouWant

5 years ago, # |

← Rev. 2 →

Can anyone explain the solution to J? I implemented a greedy idea only to get WA on testcase 20.

→ Reply

ffao

5 years ago, # ^ |

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.

→ Reply

squarepants

5 years ago, # ^ |

I have another idea. Consider all parts of consecutive cells not containing rocks. There are exactly $$$r + 1$$$ parts. Let $$$dp[i][j][1]$$$ be the maximum number of ghosts that can be repelled using at most $$$j$$$ blocks of type $$$1$$$ and last cell of this part covered by a block of type $$$3$$$. Similarly $$$dp[i][j][0]$$$ be the maximum number of ghosts that can be repelled using at most $$$j$$$ blocks of type $$$1$$$ and last cell of this part not covered by a block of type $$$3$$$. Then the dp transitions are given by

$$$ dp[p][k][0] = \max_{j}\big(dp[p - 1][k - j][0] + jg_1 + \Bigl\lfloor \frac{a_i - j}{2} \Bigr\rfloor g_2, dp[p - 1][k - j][1] + j g_1 + \Bigl\lfloor \frac{a_i - j}{2} \Bigr\rfloor g_2 + g_3 \big)$$$

Similarly, we can come up with dp transitions for $$$dp[i][j][1]$$$. Computing these dp values would give time complexity $$$\mathcal{O}(rk^2)$$$. But key observation is that, if we separate $$$j$$$ term and $$$k$$$ term and convert it into a range max query. So, the run time becomes $$$\mathcal{O}(rk)$$$.

My code

→ Reply

chemthan

5 years ago, # ^ |

← Rev. 4 →

We need at most O(number of rocks) type-1.

It turns out the test cases are weak, lol.

→ Reply

BenW

5 years ago, # ^ |

← Rev. 6 →

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

→ Reply

kurzgesagt

5 years ago, # ^ |

← Rev. 2 →

[deleted]

→ Reply

FLEA

5 years ago, # |

How to solve problem K?

→ Reply

5 years ago, # ^ |

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)$$$.

→ Reply

5 years ago, # ^ |

Can I see your code ? Thank you very much!

→ Reply

5 years ago, # ^ |

Yes

#include <bits/stdc++.h>
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;
        }
    }
}

→ Reply

5 years ago, # ^ |

Can you explain the x1 y1 x2 y2 in detail? Thanks in advance!

→ Reply

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

KhozmoS

5 years ago, # ^ |

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; )

→ Reply

5 years ago, # ^ |

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.

→ Reply

dtc03012

5 years ago, # ^ |

use sqrt decomposition!

→ Reply

bkdn23.ILoveUhiuhiu

15 months ago, # ^ |

Can I see your code ? Thank you very much!

→ Reply

kurzgesagt

5 years ago, # ^ |

← Rev. 2 →

-8

[deleted]

→ Reply

katana_handler

5 years ago, # |

how and where to submit the solutions if we want to upsolve???

→ Reply

hieplpvip

5 years ago, # |

← Rev. 2 →

Could someone give me advice on how to solve problem G ?

EDIT: Solved using segment tree

→ Reply

BenW

5 years ago, # ^ |

← Rev. 7 →

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

→ Reply

docardoso

5 years ago, # |

Could someone provide insights on problem H? I got stuck on test case 5 with my solution: https://ideone.com/at2GS0 .

→ Reply

5 years ago, # ^ |

I think it is the accuracy problem of floating point numbers.

→ Reply

sabertooth

5 years ago, # ^ |

can you review this.. Stuck on test case 5 Code

→ Reply

docardoso

5 years ago, # ^ |

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 .

→ Reply

5 years ago, # ^ |

you need long double

→ Reply

deermen001

5 years ago, # ^ |

Can you tell why we needed to use long double instead of double?

→ Reply

5 years ago, # ^ |

this test data: 1 999999999 999999999 if you use double,your answer will lose 0.5

→ Reply

Priyansh31dec

4 years ago, # ^ |

Thanks a lot for this example test case. Can you give some insights about knowing when to use normal double and when to use long double and is it good if we start using only long double from now on? I am really curious about this precision thing here. The double value can have a precision of up to 10^(-11) but still, it is going wrong for a single decimal, any reason why?

→ Reply

steinum

5 years ago, # |

can anyone give me one small test case for k? I use square root decomposition .

here my solution

→ Reply

5 years ago, # ^ |

This test case ,your output is different with mine.

Click me

→ Reply

soloSquad1999

5 years ago, # |

← Rev. 3 →

Sorry if I misunderstood something. But this contest was not in gym, right? So why I could not see another team 's code?

→ Reply

https://github.com/jonathanirvings/icpc-jakarta-2019/blob/master/problem_analysis.pdf

5 years ago, # |

where can I find the solution

→ Reply

21August

5 years ago, # |

+23

Will the submissions be visible?

→ Reply

25shubham

5 years ago, # |

pls someone write editorial blog, it will help in upsolve the problem..

→ Reply

nirvana

5 years ago, # ^ |

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.

→ Reply

lamnhh

5 years ago, # |

How to solve problem I?

→ Reply

chemthan

5 years ago, # ^ |

← Rev. 3 →

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,...

→ Reply

tfg

5 years ago, # ^ |

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.

→ Reply

NeiH

5 years ago, # |

explain me solve problem H?? please

→ Reply

NeiH

5 years ago, # ^ |

← Rev. 2 →

sorry. I'm not use long double type so WA test 5

→ Reply

5 years ago, # ^ |

← Rev. 2 →

in fact,before i found the problem，i had WA 5 times

→ Reply

5 years ago, # |

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).

→ Reply

its_aks_ulure

5 years ago, # |

Please make the test cases visible.

→ Reply

anonymous_Bunny

5 years ago, # |

Please make testcases and other's solutions available

→ Reply

21August

5 years ago, # |

Can you please make all sources visible?

→ Reply

YU1

5 years ago, # |

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.

→ Reply

crazeann

5 years ago, # |

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?!!

→ Reply

flashmt

5 years ago, # ^ |

Line 64, why do you compare with only the last one?

→ Reply

toxic_hack

5 years ago, # |

Why are the test cases and solutions still not visible!?

→ Reply

IsmailToukhy

5 years ago, # |

← Rev. 2 →

why TLE? problem K

is that because of using vectors in representing the matrices or what?

Code

#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ff      first
#define ss      second
#define all(v)  (v.begin(), v.end())

#define row         vector<long long>
#define matrix      vector<row>
#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;
}

→ Reply

andrewtheodore

5 years ago, # ^ |

← Rev. 2 →

+21

→ Reply

mrtempo

5 years ago, # |

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.

→ Reply

AmanGupta_

5 years ago, # |

What's wrong with this code. It fails on test-5 of Even Path. https://codeforces.net/contest/1252/submission/64762718

→ Reply

vivace_jr

5 years ago, # |

jonathanirvings Test cases or other's solutions are not visible, please fix

→ Reply

vivace_jr

5 years ago, # ^ |

MikeMirzayanov Please fix

→ Reply

5 years ago, # ^ |

Hi, sorry for late reply.

I am not sure how to fix this, since I am not seeing a button in the contest admin panel to enable/disable viewing testcases or others' solutions. Please advice if you know how to do it.

Meanwhile, as suggested in UPD2, the full problem repository of this contest has been published. You can refer to it to see the testcases. The uploaded testcases in the problem repository and in Codeforces is exactly the same (including the order).

→ Reply