Given $$$n, a, b$$$ are all positive numbers $$$(1 \le a, b, n \le 10^{18})$$$.

Count how many numbers from $$$1$$$ to $$$n$$$ that can be represented as $$$a\times x + b\times y$$$ with $$$x,y \ge 0$$$ are arbitrarily non-negative integers.

I only know a $$$O(\sqrt{n})$$$ algorithm.

Thanks.

I'm trying to generate a testcase so that Prim with complexity $$$O(N^2)$$$ is significantly faster than Prim with priority queue $$$O((N + M)log(N + M)$$$ (Here $$$N$$$ is number of vertices and $$$M$$$ is number of edges).

However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $$$N = 2500$$$ and $$$M = N * (N - 1) / 2$$$ (As polygon doesn't allow bigger constraint)).

I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).

Thanks.

Given an array of $$$N$$$ $$$(1 \le N \le 10^5)$$$ elements $$$A_1,A_2,\dots,A_N$$$ $$$(1 \le A_i \le 10^6)$$$. You can replace $$$2$$$ consecutive elements with their sum. Find the minimum number of replacements such that the resulting array is non-decreasing.

As you can easily see, it is the same as split $$$A$$$ into maximum number of segments such that their sums from left to right is non-decreasing.

Thanks.

Given a string $$$S (|S| \le 100)$$$ and $$$n (n \le 1000)$$$ strings $$$T_1, T_2, \dots, T_n (|T_i| \le 30)$$$. Each string $$$T_i$$$ has a corresponding point $$$p_i (1 \le p_i \le 10000)$$$.

You can do the following operation any number of times (until you cannot choose any substring): Choose a substring in $$$S$$$ that is equal to one of $$$T_i$$$, delete that substring in $$$S$$$, you get $$$p_i$$$ points and the remaining characters of $$$S$$$ concatenate.

What is the maximum points you can get by doing the operations?

I was thinking about a solution using DP and Aho Corasick.

Specifically, let $$$dp(i, j) = $$$ the maximum points you can get with the first $$$i$$$ characters of $$$S$$$ and you are standing at node $$$j$$$ in the Trie after doing some operations.

But I came across a problem. When we move from $$$dp(i, j)$$$ to $$$dp(i + 1, k)$$$, if we jump from node $$$j$$$ to node $$$k$$$ with suffix link, we lost some information of the prefix that we haven't used in any operation yet.

Could you guys suggest any alternatives?

Thanks in advance.

Recently, a friend of mine do this problem 1137C.

His solution involves using dfs for Tarjan algorithm. As the number of vertices is pretty big, about $$$50 \times 10^5$$$, the submission without inline get RTE 123001685. Depend on the exit code, I doubt that it get stack overflow error. And after putting inline in front of the dfs function for tarjan, it gets AC 123002929.

Not only that, here are 2 submissions (my friend took from someone) that is completely the same but with RTE and AC status. RTE: 123002279, AC: 123002352. The only difference is he added 3 non-sense lines into the RTE code and it got AC.

I have some questions in mind:

• Does Stack overflow error the main thing that caused RTE?

• Inline is supposed to be automatically added by the compiler when possible, isn't it? (As I heard somebody says so)

• Why putting those 3 non-sense lines work the same as adding inline?

Recently, I've just created a mashup gym contest (333319) for my teacher. But now I cannot rewrite the statement anymore, it showed "Can't read problem descriptor". Not only that, when I clicked to see the problem, it pop up the error page.

Given a polygon $$$n (n \leq 10 ^ 5) $$$ vertices on a 2D Descartes plane. $$$(|x_i|,|y_i| \leq 5. 10^8)$$$. This polygon is not self-intersecting, 2 consecutive edges have only 1 common point (which is the vertex). Find the sum of all segments of the 2D plane lie completely inside the polygon. (can be a real number).

Input:

5

0 0

-2 2

-2 -1

2 -2

2 0

Output: 12.5

Explain: The answer is the sum of all the red segments. The middle point is $$$(0,0)$$$.

Given a 2D table of size $$$n \times m (n, m \leq 400)$$$. Cell $$$(i, j)$$$ has value $$$a[i][j] \leq 10^6$$$. Find the rectangle which has maximum area and the rectangle consists of pairwise distinct values.

Input:

3 3

1 3 4

2 4 3

5 6 3

Output: 6. (Rectangle $$$(1,1) \rightarrow (3, 2)$$$).

Thanks! <3

Given a undirected graph with $$$N (N \leq 100)$$$ vertices, $$$M (M \leq N * (N + 1) / 2)$$$ edges (there can be edge connect a vertex with itself but all edges are distinct).

Find the number of minimum paths that every edge is in exactly 1 path.

Thanks.

UPD: I just realized it is sum of (odd vertices / 2) for every connected component (and some special case like m = 0, odd vertices = 0).

In problem 316C2, the solution is to find Max Flow Min Cost of the constructed graph.

Skimming through some fastest submissions, I noticed that there is a function called modify_label that replaced SPFA to find shortest path in normal MFMC. Here is one of those submisions.

And this modify_label only cost $$$O(|V| + |E|)$$$ complexity, result in small overall complexity. I think this has some relation with Johnson's algorithm.

Please someone explained it to me how this function works and how this is applicable with this problem. Thanks :<.

Recently I've come across problem 887F of a Div 2 and seeing the tag with 1600 rating difficulty was really surprising to me.

And there are actually only 77 people has solved it and it is even less than problem E of the same contest — which has rating difficulty of 2700. And that's really weird, isn't it?

So I wonder if there are some issues with the new rating estimation for problems ?

Thanks for reading <3 <3.

Recently, I realised a problem about my typing habit. I learned how to type with 10 fingers about 5 months ago and when it comes to typing normally (mainly letters and numbers) I will obviously type with 10 fingers.

However, when it comes to coding I just used my fingers wrong for pressing ; or . or , or < or [ ... or the Shift, the Backspace key ... — All the buttons that is mainly your little finger role — which is a small and kind of weak finger so it's really hard to code fast using that finger right?

So I want to ask you guys what fingers do you use to press those frequent characters when coding and figure out what may be the best to learn to code the fastest ?

It's may not really what's important about Coding but I'm just curious ^^. Thanks for reading <3 <3 !!

Hello Codeforces Community,

I have been thinking about a simple but intriguing question in my mind recently.

As day by day, we have many new contests with many new problems being made for us to do. So is there a time when all the ideas to make new problems are actually used up and there is no idea left to create a beautiful and new problem (that wasn't created before) ?. And then problem setters have to use some old ideas and problems of long time ago to create new contests for us (and this won't be interesting at all) ?

I wonder if this scenerio could be possible then?

Thanks for reading <3 <3.

Recently, I have tried doing QTREE6 on SPOJ.

I read and did the exactly same algorithm (with nearly same code) here and still got TLE.

This is my TLE submission.

The weird thing is his code just ran about 0.19 s, while mine getting over 1 s (even the code seems to be so similar). I have tried many ways like : switching scanf / cin, add some pragma lines, eliminate recursion of hld function ... but still it didn't work.

I really want to know the reasons so I can learn what really make my code so slow.

Thanks so much for reading <3.

I suddenly came across these lines of code when looking at others' submissions: (M is a prime)

    inv[1]=1;
    for(i=2;i<N;i++)
        inv[i]=(M-M/i)*inv[M%i]%M;

I tried to google it to understand the formula but ended up finding nothing. So could anyone give me the proof for this?

Thanks a lot <3 <3.

Recently, I have been searching for some articles about "Smaller to larger" technique on Google, but ended up finding nothing really useful (only the first 2 pages mention about it but they are all about Sack(dsu on tree) :> ...).

So could you guys show me some good documents about that technique and provide me as many as problems you guys have come across during your coding journey? <3

P/s: or share your way of understanding and applying this technique, if you could <3.

Thanks so much and have a great day <3.