Hey, all.

I think that from time to time all of us stumble upon a solution for a problem that make we go 'holy shit, this is beautiful'. So, I'd like to ask you guys to post the most beautiful/creative/out of the box solutions you've ever seen/created in the programming competitions world, so we can all see how cool some of them are and get a little bit inspired.

Hi all.

Can someone give me some tips on how to solve the following problem?

Given a non-empty string S consisting of lowercase letters with length at most 10⁵, calculate the number of distinct sums for every substring of S. The sum of a string is defined as the sum of the values of all the characters in it. The values of the characters are in the range [1, 26], starting from a; i.e., the value of a is 1, the value of b is 2 and so on.

For example, the distinct sums for the string S = acd are 1, 3, 4, 7, 8; in this case, the answer should be 5.

This problem is from brazilian first subregional, which occurred yesterday, and the given time limit was 7 seconds.

Thanks for the help!

Hi all.

This week I solved two problems here on codeforces, both on C++. For my surprise, in those two problems, I received TLE as a verdict on really small testcases when using GNU C++11 as a language. The solutions for those tests were running pretty fast on my machine, so I decided to submit them with GNU C++14; surprisingly, those solutions were accepted, having really small execution time on the said tests.

Problem 1:

C++11, C++14

Problem 2:

C++11, C++14

What is the issue?

Appreciate the help!

Hi all.

I've came across this way of storing edges in many codes:

void addEdge(int u, int v) {
    head[edges] = v;
    prev[edges] = last[u];
    last[u] = edges++;
}

How does it work? Why is it used over the 'traditional' array of vectors?

I appreciate your help!

Hi.

I solved problem 519E - A and B and Lecture Rooms using the solution suggested by the editorial and still it is slow when compared to others solutions. The strange thing is that there are some cases with maximum N and M that take ~0.1s to run, but there are others that are way slower, even though N and M are not maximum.

My solution took ~1.6s while there are some that took ~0.1s.

Why is my solution so slow?

My solution: 16864045 Example of a fast one: 10141947

Thanks for the help.

Hi.

I was looking some solutions of problem 551C - GukiZ hates Boxes and I found this one: 11548616.

Basically, the code binary search the optimal time. One thing I can't understand is its stop condition (and then the choice of the optimal answer). The while stop condition in the main function is ma - mi > 1, i.e., it will stop when mi + 1 = ma and (I think) there will never be such case that mi = ma. After that while, he prints the value of ma (right 'pointer' of binary search).

My doubt is: why can't mi be the optimal answer? How is he sure that ma is already the optimal answer despite the fact that mi is still inside the 'search' range?

Any help is appreciated. Thanks!

Hi.

Can someone give me tips on how to solve problem I from NWERC 2009?

I've tried to solve it using something like a merge of many convex hulls but, besides being too complicated, the time complexity of this approach is quite high.

Any help is appreciated. Thanks!

Hi all.

Recently, I've been having some problems with the execution time of Top-Down DP approaches in some OJ. So, I'd like to know from your experiences (contests/competitions/rounds) whether it is safe to keep solving problems this way.

Thanks!