Hi Codeforces, I met a problem which is matrix exponential in my country's selection exam day2, unluckily, i didn't solve it, only got all the subtasks, and i can't find much problems related to it. Would you guys give some advice? Cheers :)

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 174 |

5 | tourist | 166 |

6 | McDic | 164 |

6 | Um_nik | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

Hi guys, I am working on a problem as following:

(1) add a new line which is represented as *y* = *k* _{ i} *x* + *b* _{ i}, particularly *k* _{ i} is not mono

(2) give u *x*, ask the maximum *y* among all these lines

you have to do it online

Would anyone like to explain how set works specificly?

Thanks!

out of curiosity, is it an unusual round?

Hey guys, i was working on this problem 827D-Best edge weight

There is a skill i learnt from a code, if you used two-power walk (i don't know how to call it in a proper way), let *fa*[*i*][*j*] represents you start from *i*, walk 2^{ j} steps upward, the vertex you can reach. *p*[*i*][*j*] represents the same stuff but instead of storing the vertex you can reach, we store the minimum weight among all the edges you pass from *u* to *v*.

if you want to change the weights on all the edges on the path from *u* to *v* on the tree, you only need to do the following part:

```
void modify(int u,int z,int w) //change to w, assume z is the lca to (u,v) coz u can split it into u->lca,v->lca
{
int c = dep[u]-dep[z];
for(int i = 19; i >= 0; -- i) if(c&(1<<i)) p[u][i] = min(p[u][i], w), u = fa[u][i];
}
```

and then in the main function, we do

```
fd(j,19,1) fo(i,1,n)
{
p[j-1][i] = min(p[j-1][i], p[j][i]);
p[j-1][fa[j-1][i]] = min(p[j-1][fa[j-1][i]], p[j][i]);
}
```

i am wondering if this skill is correct and i can use it for any offline modification?

thanks :P

I just chekced the live board and there is only one american pariticpant, could anyone tell me why?

Hi fellows, I am a pupil to D&C optimization and I really want to practise on that skill.

Would anyone like to recommend some good problems which use D&C to optimize DP? Cheers!

There are soo many "In queue", is it able to be fixed before tonight's cf round?

Hi guys, i participated srm717 last night, and submitted q1, here is my idea (but failed in system test, i have no idea)

First we know there is one and only one solution, which makes the difficulty of this problem locate on constructing the graph.

So i came up with a greedy idea:

(1) we sort S[] from small to big, then we bruteforce i from 1 -> n

(2) we try to choose some nodes to be connected with node i, the nodes should satisfy that

they haven't been connected with i yet

their outdegree should be as small as possible

then i passed all the examples but got failed in system test.. i am a bit curious

btw the contest is not active therefore i can't see the test data

Thanks guys :)

hey guys, i was chatting with my dudes, and then we found an interesting problem, plz give me some ideas, cheers.

give u n numbers represented as ai(can be positive or negative),u have todeal with m operations

add x y c, add c to [x,y]

times x y c, times c to [x,y]

divide x y c, make everything in [x,y] divided by c, ignore the digits after decimal point

ask x y, ask the sum in [x,y]

ask how many times in [x,y] such that the prefix sum of i is negative

n,m smaller than 1e5, other numbers are integers

for constaints, it is like a warm up round

for others, it is a good round to practise if they are unofficial

can't live without cf in 1.5 months!

plzzzz

as the title

Lots of problems in Round#398 results.

It shows i passed A&D

but i got rk2300+, then drop 77 rating

What's going on????

first of all, this is my first tutorial of one whole round, so there must be some places that i need to improve, if you find bug, just comment it and i will be pleasure to update.

Secondly, this round i got rk 151 in div2. it's too stupid that i came up with a wrong idea which made me waste lots of time, but after the competition, i finish them, it seems the offical tutorial still not okay. Therefore, i published this one.

Third, i wanna say thanks to my friends: samzhang[15120] & quailty[quailty]

We know if we are *pos* _{ a} now and we wanna go to *pos* _{ b}, there are two ways.

1.clockwise, which cost |*pos* _{ a} - *pos* _{ b}|

2.counter-clockwise, which cost 26 - |*pos* _{ a} - *pos* _{ b}|

just choose the smaller one.

there are two ways to buy pizzas:

1.one day, two pizzas.

2.two day, one pizza each day.

We know it is always better if we can buy exactly *a* _{ i} pizzas in that day

but sometimes *a* _{ i} can't be divided by 2

so we need to buy option#2 : one pizza each day

then *a* _{ i} - 1 can be divided by 2

but don't forget *a* _{ i + 1} shoude decrease 1

why only one? beacause the main idea is to make smaller influence

btw, when *a* _{ i} < 0 ( after decreasing ), stop and exit.

consider *l* _{ i}, *r* _{ i} as a non-directed edge.

so the question changes into: there are some conected components, one component must be the same color, query the minimum times to modify one vector's color.

it's easy to solve with *dsu* , first of all, we use dsu to get all conected components. For each conected component, we use the color which has the most frequency to colour this connected component.

so we get an algorithm.

imagine we need to sort an array *A*

we want *A* _{ i} < *A* _{ j} (*j* > *i*), we just need to make *A* _{ i} < *A* _{ i + 1}

this problem is the same way, if we want all words are sorted, we just need to compare each pair of adjacent words.

consider about the following two words: *A* *and* *B*(*A* *is* *in* *front* *of* *B*)

According to the notice, we know for each *i* we need *A* _{ i} ≤ *B* _{ i}

let x represent the answer, consider two elements, *A* _{ i}, *B* _{ i}

if *A* _{ i} = *B* _{ i}, skip

if *A* _{ i} < *B* _{ i}, absolutely

if *A* _{ i} > *B* _{ i}, we also say that

as soon as *A* _{ i} ≠ *B* _{ i} is satisfie, we can skip the rest.

how to solve these inequalities? just use Segment_Tree or Bit or Difference

i recommend Difference because *C* ≤ 10^{6}

let *dp*[*i*] represent the maximum difference when Petya is first,and he got prefix [1, *i*]

it's easy to see that

*s*[*i*] represent

do a change, we have

use suffix maximum array is enough.

consider transform as swaping characters.

it is easy to notice that *A* _{ i} ≤ 2 × 10^{5}

so we use an array to count the number of *A* _{ i}

after that, we suppose *A* _{ i} is the base

then we know all *P* that *P* = *k* × *A* _{ i}, find how many times *P* appears after modifying

it is easy to solve by the array we created.

because of this is harmonic progression, so it is an algorithm.

Thanks for reading!

At first, this solution is more simple than one solution i saw among the comments.

now let's see how to solve this problem.

First we know it just asks the minnium of cost. Obviously we should use DP.

Let *F*[*i*] represent the minnium of cost to create the 'A' string which has n characters.

Consider first operation, easily we know *F*[*i*] = *F*[*i* - 1] + *x*

How to deal with the second operation and third? We can consider them together!

But why? After thinking about that, we know that we use 'delete operation' when we have excess characters.

However, if we just add 'a', it is impossible to exceed.

The only reason of exceeding is we used the second operation!

After that, we can know E.G. we want aaaaa , we have aaa, so we first copy and paste(cost y), then we have aaaaaa, we have to delete one(cost x)

Particularly,

Therefore, it is an *O*(*n* ^{2}) algorithm. TLE!

We can use humdrum queue to make it much faster. As a result, it is *O*(*n*)

```
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define rep(i,s,t) for(int i = s; i <= t; ++ i)
typedef long long LL;
const int MaxN = 10000050;
int N, X, Y;
LL dp[MaxN], Ans = 1LL<<61;
pair<LL,int> Q[MaxN];
int front, tail;
int main()
{
scanf("%d%d%d",&N,&X,&Y);
front = 0; tail = -1;
dp[1] = X; Q[++tail] = mp(3LL*X, 1);
rep(i,2,N)
{
while(front <= tail && Q[front].se < (int)(i/2)+(i%2)) ++ front;
dp[i] = min(dp[i-1] + X, Q[front].fi + Y - (LL)i*X);
//f(i)=min{f(i-1)+x, f(j)+2*j*x-i*x+y}
while(front <= tail && dp[i] + 2LL*i*X < Q[tail].fi) -- tail;
Q[++tail] = mp(dp[i] + 2LL*i*X, i);
}
printf("%I64d",dp[N]);
return 0;
}
```

or see my submission here.

First, suppose n is the shortest side of the triangle, m, k are other two sides. According to Pythagorean Theorem, we know *n* ^{2} + *m* ^{2} = *k* ^{2}

just do a change *k* ^{2} - *m* ^{2} = *n* ^{2}

futherly (*k* + *m*)(*k* - *m*) = *n* ^{2}

as we know, *n* ^{2} × 1 = *n* ^{2} so we can suppose that *k* + *m* = *n* ^{2}, *k* - *m* = 1 [because we have SPJ]

easily, we get

because the side is a interger, so this solution can only be used when n is a odd.

So how to deal with even? we find that if (k-m) is odd, the solution is suitable for odd. On the other hand, we guess that if(k-m) is even, the solution is suitable for even.

just as this,

so, we get

this is an *O*(1) algorithm.

So if you want to see more clearly, you can see the formual on this page. if you have some questions, i am willing to help you.:) [my english is not very good, so please pass some grammer fault.:P]

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2020 18:27:23 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|