I am currently trying to solve this problem. The problem is that I get Runtime Error on test cases 9b and 9c, even though I don't have any problem running it on my computer (both mac os and linux).

What do you think is the reason? Can you tell me if it works on your system?

Problem Statement
Test Data
My Code

I am looking for CNOI (Chinese National Olympiad in Informatics) problems with creative, elegant solutions. I would be very glad if you could give me some suggestions.

By the way, is it possible to find editorials to these problems on the internet?

I will hold a local offline programming contest in the near future. It will be in ACM-ICPC format. Which software do you suggest as a judge?

P.S. It would be really good if it's easy to set up.

I was writing a problem, which is interactive, on polygon. There was a checkbox, which said interactive, so I thought I can use the problem on a Codeforces round. Then, I realized interactive problems can be on only gym contests, which is really sad news for me right now because I was really enthusiastic about this problem until just now.

What's the rationale for it? Are there any plans on changing this rule?

And which other platforms that support interactive problems are there that I can submit my problem?

I've decided to watch these lectures, but I don't know which ones are more important (common) for competitive programming.

What do you suggest?

I couldn't prove the greedy algorithm which is used in the A part of this problem, so I looked it up on the internet and found this. There is a proof there, but I think that it's incomplete. Specifically, it doesn't prove subproblem needs to be solved optimally for problem to be solved optimally. Thanks for help in advance.

Also, I'm really bad at greedy algorithms. Is there any text on proof techniques for greedy algorithms, must-solve problems, or other important stuff on greedy algorithms you know?

I was trying solve this problem and I've thought of O(T * N) solution that uses Tarjan+DP. I thought O(T * N²) wouldn't work because . But solutions on this blog and this blog seem to me as O(T * N²).

How do they get accepted? Is it just because of weak test cases, or is there something else I'm missing here?

There are 3 numbers: T, N, M. 1 ≤ T, M ≤ 10⁹, 1 ≤ N ≤ 10¹⁸ .

What is asked in the problem is to compute . Obviously, O(N) or O(M) solutions wouldn't work because of 1 second time limit. What can I do?

I need a data structure that supports 4 operations:

• ADD( val ) : Adds val (which is a number) to data structure
• REMOVE( val ) : Removes val from data structure
• SUM( val ) : Returns sum of all elements greater than val
• NUM( val ) : Returns number of all elements greater than val

Operations should be better than O(n) in terms of time complexity. Do you have any ideas?

Hi, I've encountered this graph problem recently, but I couldn't solve it yet. What do you think about it?

There are N vertices and at most N directed edges. Some vertices don't have any edge connecting itself with some other vertex; some have only one. Every vertex has some value assigned to itself (A_i is the value of ith vertex). We can use any edge to move other vertices from the current vertex. We can use even edges that are incoming, but incoming edges cost 1 point, whereas outgoing edges cost nothing. What is the maximum sum of values of vertices that can be traversed when we start at vertex u with K points?

1 <= N <= 1,000

1 <= K <= 100

1 <= A_i <= 10,000

UPD. Things that I forgot to say:

• The graph might have cycles.
• The value of an edge can be added only once to total sum.
• To be clear: Every vertex has 0 or 1 outgoing edge, but there isn't any limit for incoming edges.

I couln't analyse the complexity of this solution to this problem. Can someone explain why even simple recursive approach doesn't get TLE?

I've come across to this problem on UVa. It basically asks for second shortest path. I've looked it up on the internet, but I couldn't find any practical implementation of it. Are there any good tutorial on this topic?

Note: I'm asking about both SSP and APSP. Also, is second shortest path simpler than more general kth shortest path algorithms in terms of complexity?

UPD: Thank you really much for your help, I've solved the problem! But the thing is nobody has mentioned any algorithm for All-Pair Second Shortest Path problem yet. Can someone who is knowledgeable about this problem explain it?

I was researching about 2d (multi-dimensional) segment trees. Firstly, I've looked PrinceOfPersia's tutorial, but there wasn't much about 2d segment trees; that's why I've researched a little bit and found this blog.

Even though, PrinceOfPersia's tutorial doesn't tell much about 2d segment tree, it says that every node in main segment tree is also a segment tree. On contrary, other blog describes a totally different idea.

Can someone explain me (or point out a website that explains it) the idea represented in PrinceOfPersia's tutorial and compare (complexity, usages etc.) these two different approaches? Also, it looks like range update with lazy propagation would work with a quad tree. Is lazy propagation possible in other one?

UPD: Thank you really much for good answers! They're really useful.

I was trying to solve this problem. I've found a solution whose complexity is O(N^4) (N = length of string). Since N might be 100, I've thought that it's not fast enough. Then I looked at the official solution, surprisingly, it is almost same with mine. Can someone explain the complexity of this algorithm and tell why it isn't TLE?

Problem: D. The Maths Lecture

My solution:

I have 3 arrays:

• base: It contains base values of digits modulo k.
• dp: dp[i][j] is the number of suffixes of length i which equals j modulo k.

dp[0][0] = 1

dp[i+1][(j+base[i]*d)%k] += dp[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == n-1 ? 1 : 0) <= d <= 9)

• dp2: dp2[i][j] is the number of prefixes of length i which equals j modulo k.

dp2[0][0] = 1

dp2[i+1][(j+base[n-1-i]*d)%k] += dp2[i][j] where (1 <= i < n) & (0 <= j < k) & ((i == 0 ? 1 : 0) <= d <= 9)

res equals (dp[n][0] + dp[n-1][0] * (dp2[1][1] + dp2[1][2] + ... + dp2[1][k-1]) + ... + dp[1][0] * (dp2[n-1][1] + ...)) % m

Source Code

This way seemed correct to me, but it outputs 835 instead of 590 for the 3rd test case. What's my mistake?

A friend of mine asked me a problem, but I couldn't find a good way to solve.

The problem: N is the number of ways to represent number X as sum of prime numbers. For example, if X is 10, N is 5 because (5 + 5) = (2 + 2 + 3 + 3) = (2 + 3 + 5) = (2 + 2 + 2 + 2 + 2) = (3 + 7) = 10. N is given to you. Compute X. (If there are more than one answer, you can output any of them.)

Do you have any idea?

I could't solve this problem, then I've read the editorial; but, I still can't understand how we convert dp states into matrices. Can someone, who knows the solution, elaborate?

PS: I know how to compute Nth power of matrix (size M*M) in O(M^3 * log N). I couldn't understand the values we are storing in the matrix and how kth matrix is used to get (k+1)th matrix.

UPD: I've coded the solution as terribleimposter told me, but I think that my implementation is awful. How can I improve it (especially initialising adjacency matrix) ?

If I'm not wrong, codechef has recently launched a built-in to-do list feature. Most of the time, I open tabs for problems I want to solve, and I usually can't solve all of them; these stack and lead to a lot of ugly opened tabs that I can't close. Of course, I can use an external to-do app, notebook etc. to list the problems I want to solve, but it's not as good as a built-in feature. I think that it would be great to have something like that also on codeforces. What do you think?

I implemented the solution of Jzzhu and Cities as it's told in the tutorial, but I've got WA on test 5. What's my mistake?

I solved this question with a solution like this, but the problem is that my solution's memory complexity is a lot. It used something like 250 MBs. Is my approach to problem wrong? If there is a better way to do it, what is it?

I'm a member of codeforces for a while now, and I'm familiar with format of contests, website interface etc. I have seen this post about tomorrow's SRM on topcoder and I've decided to participate in. Do I need to register for the contest as in codeforces' rounds? And it also seemed like I can't use my own editor on arena. Do I have to use the coding area to code the solution? Is there an option or workaround not to use its built-in editor? I'm also curios which one's (topcoder or codeforces) type of problems more similar to IOI?

In the solution of tutorial of this problem, levels are represented by vertices and transfers are represented by edges. Graph also has a start vertex. It says that the result is a minimum spanning tree of the graph. I couldn't understand why the answer is a minimum spanning tree. Can't a vertex of a minimum spanning tree have more than one adjacent vertex which is impossible for a tree to be the result? Can someone explain where I'm wrong?

I can't really understand this community. I've just asked help for something that I didn't understand. I would happily help someone if I knew where the mistake was. It was neither spam nor trolling. Can someone explain me why I've got all these downvotes? Is there a general criteria about posts that I need to obey?

I tried to code the idea that is in the editorial. It doesn't pass 14th test, but I can't find it why. I would appreciate any help. Thank you !

UPD:

I've used the code in this blog for calculating the f array, and I haven't changed any other parts of my code. It worked. Then I tried the idea using my monotonic queue class, which I've written before(and I know that that code is correct because I use it to calculate also g array), and it can't pass the 6th test right now. Where is the difference?

Accepted: 9080710

Wrong Answer: 9084717