I saw a similar problem at the IFMO’s Internet Olympiad (russian statements, problem G). Unfortunately, jury’s solution and tests are incorrect.

Awesome and interesting problems, thank you very much!

If so, it looks strange, because such problems usually doesn’t require any skills except very basic school physics.

Could you tell about these tests? What is it like? Contests, yes/no tests or something else?

What is Physics problem? IOI’s olympiad in informatics, isn’t it?

Look: you have an array: 1 2 3 4 5. It has the following prefixes: "“, ”1“, ”1 2", and so on. You calculate sum of numbers in each such prefix and get 0, 1, 1+2=3, 1+2+3=6, 10 and 15 (let’s call it s[]). Then, to calculate, for example, sum from 2 to 4, you just calculate s[4] - s[1]=9. Elements before 2 were reduced.

This idea can help you solving this problem: you run down left border of a substring and then you can calc amount of required substrings in O(1) for each left border.

Try this idea: calculate sums in all prefixes (from empty to the whole sequence) and then sum of elements in a some substring is difference of two numbers. Hope this helps. If not, I can give you detailed solution.

Just good brute-force.

This opportunity was a present from admins in the first days of new year.

May be no, because not so many people have solved E in Div2.

Probably it won’t be.

There are problems with Div1C/Div2E — jury’s solution is incorrect. This problem is under investigation and round can be unrated.

But sometimes they are so sloooooow. std::sync_with_stdio(0); treats it.

Knapsack problem is NP and it’s not solvable using greedy algorithms. May be there are some special restrictions?

Approximate meaning: 1)I enter Codeforces 2)Here I need to get in Top-300 2)Here I need to get in Top-50 4)When will be the round which I can fail?

No. You not only edges corresponding to works, but also you need edges from t to t + 1.

MinCostFlow. Vertex is a time, and work is a edge with capacity=1 and cost=-C. We need to find minimal cost flow not greater than K. V~1000, E~1000 and you even don’t need Dijkstra’s algorithm with potentials.

There is one unofficial participant above Petr

with trip expenses covered by the organizing committee.

It’s a training, not even a contest (created with Codeforces::Gyms). And yes, it’ll be unrated.

Floyd’s algorithms gets TLE with TL=1s and V=500.

No, because you didn’t qualify to Round 1.

I think that Wild-card Round 2 will be some kind of marathon with challenging problem.

It’s usable anywhere with Microsoft Visual C++ — on your local machine and so on.

I see. Mike added that penalty is usual — 50 points per resubmission/wrong solution and you cannot be awarded less than 30% of points for correctly solved problem. So, for a solved 1000-points problem you’ll always get at least 300 points no matter of penalties.

As MikeMirzayanov answered above, there is penalty for resubmissions and errors on pretests, except failure on first test (even if there are more than one example test) — it’s ignored, as usual.

Not for qualifications. But problems are usually opened to everyone and you can submit solutions after contest’s end.

It’s UTC time. You can click on it to see what time will it be in your timezone.

Nohow. Stack size is a user limit under GNU/Linux and doesn’t depend on compiler. You can use ulimit -s to change/view it.

The only thing to add is that it’s MS Visual C++-specific and won’t work with GCC. In GCC you should specify -Wl,--stack=256000000 command line option to set stack size (in bytes).

What’s source of the problem? It looks like test question.

For example: if your age is 23 years and 8 months (by the moment of registration), you can compete. If your age is at least 24 years, you cannot.

“Note that numeric variables are read into strings and then converted into numbers — this is explained by the compiler specifics which reads numbers in different ways depending on whether they are read from cosole or from file redirected to the program input stream.”

Sorry, I’ve mixed it with Kyiv. These DST laws’ changes confuse me.

“in 7 hours” means “after 7 hours”. It’s 18:0019:00 Minsk time and 20:00 Moscow time.

If you use GCC, you can add -D__USE_MINGW_ANSI_STDIO=0 parameter to compilation command line and %lf will work quite OK.

%f is for float only. %lf is for double. It’s both for scanf and printf.

Yes, it does.

Because '\b' is a char too. It doesn’t have any special meaning outside terminal.

You can run gcc -E — it runs preprocessor and outputs preprocessed source.

What’s your problem? You don’t want to click twice, or I misunderstand you?

In fact, when you work with floats/doubles (in spite of compiler), you should remember that any number (including integers) can be stored like X+-EPS. So, pow(3, 3) can be 26.9999999999999. If you cast it to int, it becomes 26, not 27. It’s better to use something like (int)(pow(3, 3) + 1e-9) here. There is a very good article on TopCoder about floating point arithmetics.

You can try MSVC++ compiler instead of GCC. GCC’s optimizer can give very strange results with floating point numbers, and they think that it’s well-known not bug

1. Let there is at least one 'bridge' edge in our graph (which does not lie on any non-self-intersected cycle). Have a look at its ends - vertexes A and B. There is exactly one path from A to B. Obliviously, we cannot choose orientation for this edge.
2. Now we don't have any bridges in our graph. Let's run DFS and prove that if we choose 'from root to leaves' orientation for all tree edges and reverse orientation for the remaining ones, everything will be OK. First, it's oblivious that it's possible to reach any vertex from root (let it will be X). Then, let's prove that from each vertex A we can reach vertex B (parent of A in DFS' tree). In this case we can reach root by induction and our graph became strong-connected. So, we want to reach B from A. Let's remove edge from A to B from our graph. Because this edge wasn't a bridge, we have second path from A to B. Obliviously, we have some reverse edge from A's subtree to some of A's parents (we don't have cross-tree edges because it's DFS' tree). So, let's go to this edge's start, use it and then go down the tree. Ta-da :)
   

1. If n is small, we can use DP - just calculate answer for each point
2. Then, we understood that we are interested only in points, which are end point of some bus and our start point
3. The last thing is to recalculate DP faster, than O(m). We have two types of events - some bus' segment is started/finished. Sort them and be happy

// Get current size of heap in bytes
long heapSize = Runtime.getRuntime().totalMemory();

// Get maximum size of heap in bytes. The heap cannot grow beyond this size.
// Any attempt will result in an OutOfMemoryException.
long heapMaxSize = Runtime.getRuntime().maxMemory();

// Get amount of free memory within the heap in bytes. This size will increase
// after garbage collection and decrease as new objects are created.
long heapFreeSize = Runtime.getRuntime().freeMemory();