### MarioYC's blog

By MarioYC, 8 years ago,

Hi, I wanted to try this contest at the Gym because the description says the statements are available in english, but none of the PDFs is in Enligsh. Does someone have the english statements? Thanks

• +30

By MarioYC, 8 years ago,

Hi everyone, I've been trying this problem: http://main.edu.pl/en/archive/oi/19/okr

I'm getting 67/100 using hashing, and the fact that the hash of a string of the form xxx..xx (repetead K times) can be calculated in O(lgK) once you have the hash for x.

But I don't know how to improve to get 100 points. Any hint?

• +10

By MarioYC, 8 years ago,

Hi everyone,

I'm trying to solve this problem.

I recently solved problem "2361-Areas" at ZOJ, for an explanation you could see my post here.

Now I think problem CIRUT from SPOJ could be solved in a similar way since areas covered by more than one circle are convex. I still haven't thought about how to solve it for areas covered by only one circle.

The problem is that since there area about N^2 areas if I test in O(n) how many circles cover it I would get TLE. So how could I do this faster? or is there another approach to the problem?

• 0

By MarioYC, 8 years ago,

Hi everyone, I'm trying to solve this problem however I get TLE. The problem asks for points such that gcd(x,y,z) = 1 inside of 0 <= x < L, 0 <= y < H, 0 <= z < W.

I'm using inclusion-exclusion with the mobius function to find the answer.

First I wrote a version going through all i from 1 to X: http://pastebin.com/UsShb6zF but I got TLE.

So I thought of optimizing it by going only through square free numbers, because in these numbers the value of the mobius function is different from zero, but I still get TLE.

Any idea about how to optimize it further?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 1000000

int mu[MAXN + 1],factor[MAXN + 1];
int sqfree[MAXN + 1],sz = 0;

long long visible(int X, int Y){
long long ret = 0;

for(int i = 0;i < sz && sqfree[i] <= X;++i){
int cur = sqfree[i];
ret += mu[cur] * (long long)(X / cur) * (Y / cur);
}

return ret;
}

long long visible(int X, int Y, int Z){
long long ret = 0;

for(int i = 0;i < sz && sqfree[i] <= X;++i){
int cur = sqfree[i];
ret += mu[cur] * (long long)(X / cur) * (Y / cur) * (Z / cur);
}

return ret;
}

int main(){
memset(factor,-1,sizeof factor);
mu[1] = 1;
sqfree[sz++] = 1;

for(int i = 2;i <= MAXN;++i){
if(factor[i] == -1){
mu[i] = -1;

if(i <= MAXN / i)
for(int j = i*i;j <= MAXN;j += i)
factor[j] = i;
}else{
int cont = 0,aux = i,p = factor[i];

while(aux % p == 0 && cont < 2){
aux /= p;
++cont;
}

if(cont == 2) mu[i] = 0;
else mu[i] = -mu[i / p];
}

if(mu[i] != 0) sqfree[sz++] = i;
}

int X,Y,Z;

while(scanf("%d %d %d",&X,&Y,&Z) == 3){
--X; --Y; --Z;

long long ans = visible(X,Y,Z) + visible(X,Y) + visible(Y,Z) + visible(Z,X);

if(X >= 1) ++ans;
if(Y >= 1) ++ans;
if(Z >= 1) ++ans;

printf("%lld\n",ans);
}

return 0;
}


• +8

By MarioYC, 8 years ago,

Hi everyone, I've been trying this problem, my approach was using sweep line after ordering the queries by its ending and considering only the last ocurrence of a number. However it fails for cases like:

N = 4

4 -2 3 -2

Q = 1

1 4

where the answer is 4,-2,3 which contains a -2 that isn't the last one, hence I return 7, but the correct answer is 5.

Any ideas on how to solve the problem?

My code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100000
#define MAXQ 100000

int a[MAXN],b[MAXN],pos[MAXN];
long long pref[4 * MAXN],suff[4 * MAXN],sum[4 * MAXN],best[4 * MAXN];
long long best_suff;

long long query(int node, int l, int r, int x, int y){
if(r < x || l > y) return 0;

if(x <= l && r <= y){
long long ret = max(best[node],best_suff + pref[node]);
best_suff = max(suff[node],best_suff + sum[node]);
return ret;
}else{
int mi = (l + r) >> 1;
long long ret1 = query(2 * node + 1,l,mi,x,y);
long long ret2 = query(2 * node + 2,mi + 1,r,x,y);
return max(ret1,ret2);
}
}

void update(int node, int l, int r, int x, int val){
if(r < x || l > x) return;

if(l == r){
pref[node] = suff[node] = best[node] = max(0,val);
sum[node] = val;
}else{
int mi = (l + r) >> 1;

update(2 * node + 1,l,mi,x,val);
update(2 * node + 2,mi + 1,r,x,val);

pref[node] = max(pref[2 * node + 1],sum[2 * node + 1] + pref[2 * node + 2]);
suff[node] = max(suff[2 * node + 2],sum[2 * node + 2] + suff[2 * node + 1]);
sum[node] = sum[2 * node + 1] + sum[2 * node + 2];
best[node] = max(suff[2 * node + 1] + pref[2 * node + 2],max(best[2 * node + 1],best[2 * node + 2]));
}
}

vector<int> q[MAXN],id[MAXN];
long long ans[MAXQ];

int main(){
int N;
scanf("%d",&N);

for(int i = 0;i < N;++i){
scanf("%d",&a[i]);
b[i] = a[i];
}

sort(b,b + N);
int m = unique(b,b + N) - b;
memset(pos,-1,sizeof pos);

int Q;
scanf("%d",&Q);

for(int i = 0,l,r;i < Q;++i){
scanf("%d %d",&l,&r);
q[r - 1].push_back(l - 1);
id[r - 1].push_back(i);
}

for(int i = 0;i < N;++i){
update(0,0,N - 1,i,a[i]);

int ind = lower_bound(b,b + m,a[i]) - b;

if(pos[ind] != -1)
update(0,0,N - 1,pos[ind],0);

pos[ind] = i;

for(int j = q[i].size() - 1;j >= 0;--j){
best_suff = 0;
ans[ id[i][j] ] = query(0,0,N - 1,q[i][j],i);
}
}

for(int i = 0;i < Q;++i)
printf("%lld\n",ans[i]);

return 0;
}



• +5

By MarioYC, 9 years ago,

Could anyone give me a hint on how to solve this problem?

I solved POJ 3167 in which the problem was based using a modified KMP, but i couldn't come up with anything that solves UNTITLED.

• +3

By MarioYC, 9 years ago,

Hi everyone, today I solved this problem using Dynamic Programming, the state is easy to get (n,c1,c2,c3) and a useful observation is to notice that if you have n,c1 and c2 then c3 can be found, so it isn't necessary for it to be part of the state. With this and some prunning it is enough to get AC (I though I would get TLE). I see solutions that are much faster, how can this be done?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MOD 100000000000000000LL

int r[125];
long long memo[126][126][126];

long long solve(int pos, int c1, int c2, int c3){
if(pos == -1){
if(c1 || c2 || c3) return 0;
return 1;
}

long long &ret = memo[pos][c1][c2];

if(ret == -1){
ret = 0;

for(int i = 0;i <= c1;++i){
for(int j = max(0,r[pos] - i - c3);j <= c2 && i + j <= r[pos];++j){
int k = r[pos] - i - j;

ret += solve(pos - 1,c1 - i,c2 - j,c3 - k);
if(ret >= MOD) ret -= MOD;
}
}
}

return ret;
}

int main(){
int n,c1,c2,c3;

scanf("%d %d %d %d",&n,&c1,&c2,&c3);

int diff = c1 + c2 + c3;

for(int i = 0;i < n;++i){
scanf("%d",&r[i]);
diff -= r[i];
}

if(diff != 0) printf("0\n");
else{
memset(memo,-1,sizeof memo);
printf("%lld\n",solve(n - 1,c1,c2,c3));
}

return 0;
}


• +3

By MarioYC, 9 years ago,

Hi everyone, I'm getting TLE in this problem, I'm trying and offline approach (I was getting RE doing it online), solving only for values of v that are given in the queries, I find the adjacents groups of numbers >= v in O(n) using 2 pointers.

The complexity is O(N x (#different values of v) + QlgQ).

Could someone suggest me an optimization or different approach? Thanks :)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[100000];
long long cont[100001];
long long ans[100000];

struct query{
int v,a,b,id;

query(){}

bool operator < (query X)const{
return v < X.v;
}
}q[100000];

int main(){
int N,Q;

scanf("%d %d",&N,&Q);

for(int i = 0;i < N;++i)
scanf("%d",&a[i]);

for(int i = 0;i < Q;++i){
scanf("%d %d %d",&q[i].v,&q[i].a,&q[i].b);
q[i].b = min(q[i].b,N);
q[i].id = i;
}

sort(q,q + Q);

for(int i = 0;i < Q;){
int e = i;

while(e < Q && q[e].v == q[i].v) ++e;

int v = q[i].v;
memset(cont,0,sizeof cont);

for(int j = 0;j < N;){
if(a[j] < v) ++j;
else{
int e2 = j;

while(e2 < N && a[e2] >= v) ++e2;

int m = e2 - j;

for(int k = 1;k <= m;++k)
cont[k] += m + 1 - k;

j = e2;
}
}

for(int j = 1;j <= N;++j)
cont[j] += cont[j - 1];

for(int j = i;j < e;++j)
ans[ q[j].id ] = (q[j].a <= q[j].b? cont[ q[j].b ]- cont[ q[j].a - 1 ] : 0);

i = e;
}

for(int i = 0;i < Q;++i)
printf("%lld\n",ans[i]);

return 0;
}


• +8

By MarioYC, 9 years ago,

Hi everyone, could someone help me find my mistake in this problem. Basically what I do is improve the obvious DP approach (with state : position, last color, and how many consecutives carpets were equal) by considering only important indexes in the interval [1,L] (these are 1,L,all s_i, and all e_i + 1).

• +8

By MarioYC, 9 years ago,

As the title says, in a graph where the distance of going between two nodes is the concatenation of the strings in the edges along the path between this two verticesm, and we want to find the lexicographically shortest distance, what distance function and which algorithm can we use to solve this kind of problems?

I was trying to solve this problem, and implement a code which uses the Floyd-Warshall algorithm, but there is a problem with cases like this:

V = 3, E = 3, s = 0, e = 2 0 -> 1 a 0 -> 1 ab 1 -> 2 c

The code returns "ac", but the right answear is "abc".

• +5

By MarioYC, 9 years ago,

Does someone know a special fact about this conjecture that could help to get a complexity lower than O(180*n), which is the one you get using a dp approach, I tried these two codes:

http://ideone.com/XN4td http://ideone.com/cWhNR (tried to use pointers to speed it up)

but both give me TLE.

• 0

By MarioYC, 9 years ago,

Hi everyone, so I found this problem today, and it seems like a really obvious bipartite matching, but I've been getting TLE in it. Is there some faster way to solve it?

• 0

By MarioYC, 9 years ago,

Hi everyone, I found this problem today, the small n suggested to use a bitmask, so I tried a DP with complexity O(L·n·2n) plus some preprocessing using KMP algorithm to find matches.

You can see my code here.

At first I got TLE, I wask doing a for loop to go through all bits of the mask at the dp part, I changed that to use __builtin_ctz in order to access only position with a bit set to 1 in every iteration, that should have cut down the time to the half, since it goes from n·2n combinations to n·2n - 1, and that gave me an AC.

But I see really faster solutions, is there some additional optimization? or maybe another approach?

• 0

By MarioYC, 9 years ago,

Hi everyone, today i saw this problem, and since i'm usually not good with 3D geometry, i tried to turn it into a linear algebra problem using barycentric coordinates. So if the vertices of the first triangle are A1, B1, C1 and the vertices of the second triangle are A2, B2, C2, we can represent points inside the first triangle like: A1*w1 + B1*w2 + C1*w3, such that w1+w2+w3 = 1, and we can get a similar equation for points inside the second one: A2*w4 + B2*w5 + C2*w6, such that w4+w5+w6 = 1. We also need 0 <= wi <= 1, for every 1 <= i <= 6. Now we can make an equation for the common points:

A1*w1 + B1*w2 + C1*w3 = A2*w4 + B2*w5 + C2*w6

which is actually two equations, one for X's and another for Y's.

Now we could work with 4 equations and maybe reach some conclusion by looking at the rank of the system of equations. But I don't have and idea about how to deal with the inequalities 0 <= wi <= 1.

Can the problem be solved this way? Anyways I would also be interested in another way to solve, or other problems where barycentric coordinates can be used.

• 0

By MarioYC, 9 years ago,

Although I didn't passed this problem during the contest, I really enjoyed it.

The reason is I never I hadn't thought before about solving "point in a polygon" queries in a more efficient way other than using O(n) algorithm for every query.

But after getting hacked, and trying to optimize my code, I noticed something nice. If we use the ray tracing algorithm for one point inside a convex polygon, then we worry bout at most four sides of the polygon every time (I assume we are using the Ray casting algorithm), and this combines really nicelly with a sweep line approach, in which you only keep the interesting sides, and discard them when they can't be intersected by the points that follow.

Implementation : 1398412

• +9

By MarioYC, 9 years ago,

I'm trying to understand when there is a solution (even though it may have more than 500 moves).

It can't always be done with one divisor, for example A = 4, B = 9 (4->6->9), but I think it can always be done with two divisors, a proof of this would be related somehow to Bezout's identity. Say we pick d1 divisor of A, and d2 divisor of B then we can find integers x,y such that

d1 * x + d2 * y = B - A

since the gcd of d1 and d2 divides B — A, the thing is that one of x and y could be negative. Is there a way to make both positive?

• +13

By MarioYC, 9 years ago,

I've tried submitting a solution to problem 120J - Минимальная сумма : 1350678, 1350695

But I get Idleness limit exceeded on test 1, I tested my code using Custom Test, but it seems to be working Ok, how can I fix this?

• -9

By MarioYC, 9 years ago,

I've been solving some problem about DFS applications, this is the first one I do working with directed graphs. First I established that the following conditions should be enough for a graph to be a cactus, after doing a DFS and getting the DFS tree:

• DFS tree should contain all node
• There are no cross edges or forward edges
• No edge is a bridge, so every edge in the tree, has a back edge covering it
• Back edges don't intersect (no edge is covered by two back edges) and they don't overlap.
• Every node with two or more sons (except the root) should have a back edge starting in it.
• Previous conditions are enough for the graph to be Strongly connected.

However I'm getting WA, could it be an implementation mistake? or some error in the conditions I've assumed?

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 10000
#define MAXE 10000

int E,to[MAXE],nxt[MAXE],last[MAXN];

to[E] = v; nxt[E] = last[u]; last[u] = E++;
}

int n,cont,parent[MAXN],level[MAXN],sons[MAXN],back[MAXN];
bool done[MAXN],forward,cross;

void dfs(int pos, int lvl){
level[pos] = lvl;
sons[pos] = 0;
++cont;

for(int e = last[pos];e != -1;e = nxt[e]){
int x = to[e];

if(done[x]) cross = true;
else if(parent[x] != -1){
if(level[x] > level[pos]) forward = true;
else back[pos] = (back[pos] == -1? level[x] : -2);
}else{
parent[x] = pos;
++sons[pos];

dfs(x,lvl + 1);
}
}

done[pos] = true;
}

bool is_cactus(){
if(cont < n || forward || cross) return false;

for(int i = 0;i < n;++i)
if(back[i] == -2) return false;

for(int i = 0;i < n;++i)
if(i != 0 && sons[i] > 1 && back[i] == -1)
return false;

for(int i = 0;i < n;++i){
if(sons[i] == 0){
int e = level[i],pos = i;

while(pos != 0){
if(level[pos] == e){
if(back[pos] == -1) return false;
e = back[pos];
}else if(back[pos] != -1) return false;

pos = parent[pos];
}
}
}

return true;
}

int main(){
int T,m;

scanf("%d",&T);

while(T--){
scanf("%d %d",&n,&m);

memset(last,-1,sizeof last);
E = 0;

for(int i = 0,u,v;i < m;++i){
scanf("%d %d",&u,&v);
}

memset(back,-1,sizeof back);
memset(parent,-1,sizeof parent);
memset(done,false,sizeof done);
forward = cross = false;
parent[0] = -2;
cont = 0;

dfs(0,0);

puts(is_cactus()? "YES" : "NO");
}

return 0;
}



• +5

By MarioYC, 9 years ago,

For this problem, first I tried an O(mn) approach (http://ideone.com/rDWvZ) which gave me TLE at pretests.

Then I tried to search for a way to use data structures to speed up the process, but didn't get to anything that could work. Then I noticed that if I precalculated the answer for some groups, the minimum, and the maximum in those groups, I would have enough information to join those pieces and get answers for intervals. So with this, I speed up my solution to O(m * sqrt(n)) which should pass in time: http://ideone.com/y2kEV

Right now I'm getting WA 4, but the case is too big to debug it. Could someone please tell me why it fails?

• -3

By MarioYC, 9 years ago,
Today I read about cartesian tree(treap) from e-maxx's page, since it is in russian I decided to translate some parts.

Also here are some related links:

http://infoarena.ro/treapuri (a different implementation)
I would appreciate if someone could post problems that can be solved it, there are some at infoarena.

### Cartesian tree (Treap):

A data structure that stores a pair (X,Y) in the form of a binary search tree with respect to X and a heap with respect to Y.

Assuming that al X and Y are different, for an element (X0,Y0):

- All the elements in the left subtree are such that X < X0
- All the elements in the right substree are such that X > X0
- All the elements in the left or right subtrees are such that Y < Y0

Notation:

X's are the keys.
Y's are the priorites (choosed at random)

If we didn't use priorities, then it would be a normal binary search tree, and the given set of X's could meet a lot of trees, some of which are degenerate
(for example in form of a chain), so operations would be done really slowly.

Priorities can uniquely identidy a tree that will be built. On average using priorites provides us the asymptotics O(log n).

Operations:

- Insert(X,Y), Avg Complexity O(log N) : Inserts a new item, we could also not pass Y as a parameter, instead we can choose it a random inside
- Search(X), Avg Complexity O(log N) : Searches for the element with the specified key value X
- Erase(X), Avg Complexity O(log N) : Searches for the element X and erases it
- Build(X1,...,XN), Avg Complexity O(N log N) : Builds a tree of a list of values
- Union(T1,T2), Avg Complexity O(M log N/M) : Combines two trees, assuming that the elements are different
- Intersect(T1,T2), Avg Complexity O(M log N/M) : Finds the common elements of two trees

Description of the implementation:

- Each element (X,Y) contains pointers to the left (L) an the right (R) sons.
- To implement other operations we require two commplementary operations: Split and Merge
- Split(T,X) : divides the tree T into two trees L and R so that L contains all elements that are smaller than X, and R contains all elements that area are equal or larger than X.
This operation is performed in O(log N)

- Merge(T1,T2) : combines two subtrees T1 and T2, and returns a new tree. This operation is also implemented in O(log N). It works on the assumption that T1 and T2 have the
appropiate order (all X values in the first are less than values at the second)

### Implicit Cartesian Tree:

It is a simple modification of the usual Cartesian tree. It can be thought of as array on which you can implement the following procedures (complexity O(log N) online):

- Insert an element in the array at any position
- Removal of any element
- Sum, minimum, maximum of an arbitrary interval
- The addition, paint on the interval
- Reverse of an interval

The key idea is to use the indices of elements in the array as the key. However, these values are explicitely stored key.
The key of a node is the number number of nodes in its left subtree, and also, in the left subtree of its ancestors.

• +30

By MarioYC, 9 years ago,
I was reading this to try to understand how to calculate grundy numbers for cyclic games. However I don't get why there are some infinite positions where the first player wins.

Also to implement the algorithm, would I need a boolean matrix M[v][x] to know whether a vertex (v) has a son which a grundy number value equal to some number (x) ? or is it possible to use less memory (this would be about O(V^2) for V states considering we can get values up to V - 1) ?

• 0

By MarioYC, 9 years ago,
I was reading to levlam's code for Codeforces 85D (Sum of Medians) :  http://pastie.org/3224822

It is nice how he does insertion and elimination of elements in O(lg n) by using lower_bound, but I can't understand why the code passes since it has complexity O(n / 5) for each sum query. Could someone explain why it passes?

By n I mean the number of elements currently stored at the vector.

• 0

By MarioYC, 9 years ago,
Hi everyone, today I was reading this paper to understand how to solve the tree isomorphism problem. However, it isn't explained how to make the final optimization from O(nlgn) to O(n), could someone explain the idea or provide a reference to it?

Thanks :)

• +31

By MarioYC, 9 years ago,

Hi, I've solved this problem before with O(N^2 lgN) algorithm. For example: http://pastie.org/3129354

But today I got to this problem: http://www.spoj.pl/problems/CHASE/
I got TLE with O(N^2 lgN) algorithm, and a O(N^2) algorithm is mentioned in comments, could someone explain how it works.

N means the number of points given.

• +13

By MarioYC, 9 years ago,

Hi, I was trying to solve this problem : http://livearchive.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=2065

However I get TLE, the complexity of my algorithm is O(n^2 lg n) which I think is enough. So I was wondering if using atan2 to order points by polar angle is slow?

Code : http://pastie.org/3105825