I am quite confused about whats going on this year, what I heard is , there is going to be two world finals this year. What teams go to the first one and what teams go to the second one?

Dear Codeforcers, I am an international student who is currently studying at UNSW Sydney. I am doing a double degree of advanced maths and computer science. I have been doing informatics Olympiad in my high school and ACM-ICPC atm. As Summer(for Australia) holiday is approaching, I am really interested in finding a software engineer internship at Sydney. However, I did some research and without exaggeration, every company requires residency(permanent residency or citizenship). Some companies only hire graduating students. Is there any suggestion you guys can give me? That would be very appreciated!

Kind Regards

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

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

(1) add a new line which is represented as y = k_ix + 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?

In my point of view i don't think that's actually a good idea coz Codeforces has hack system, if u can't see the test data, then u probably have to debug it forever :L

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

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

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

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

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

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

Something need to say

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]

A. Night at the Museum

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.

C++ CODE

B.Coupons and Discounts

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.

C++ CODE

C. Socks

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.

C++ CODE

D.80-th Level Archeology

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⁶

C++ CODE

E. Funny Game

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.

C++ CODE

F. Video Cards

it is easy to notice that A_i ≤ 2 × 10⁵

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.

C++ CODE

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²) 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² + m² = k²

just do a change k² - m² = n²

futherly (k + m)(k - m) = n²

as we know, n² × 1 = n² so we can suppose that k + m = n², 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]