sys.'s blog

By sys., 4 years ago, In English

I have a question that I can't understand.

Solution said we should iterate x which is the number of subarrays with maximum sums that we will use. But what will we do if we have two subarrays with equal sums?

for example

4 3
-11 16 -11 -1

We will choose 16 for sure. Then we have two options. One is -11 16 and 16 -11 -1, the other is 16 -11 and -11 16 -11 -1. The first one has a better answer.

izban proved that if some pair of subsegments have same sum, it doesn't matter when we choose first $$$k - n$$$ subarrays. But his proof is not correct when we choose $$$> k - n$$$ subarrays.

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By sys., 4 years ago, In English

The statement shows "not available on English language" and the tutorial shows "Unable to parse markup [type=CF_TEX]". What happened?

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it

By sys., 5 years ago, In English

Many participants use std::map in their codes.

If the type of the key is int, it will be hacked by this:

2
2 1 2
10 0 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 589934621

Because (int) 4294967296LL == 0

Full text and comments »

  • Vote: I like it
  • +175
  • Vote: I do not like it

By sys., history, 5 years ago, In English

One day when I had my math class,I came up with an idea.But I found that I can't solve it.

After class I asked many people but they did't solve it too.

Here's the problem:

You are given a undirected weighted graph with n nodes and m edges.

You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.

A simple path means that you can't pass through one edge twice or more.

(I don't know how large n,m can be)

Update:Thanks to TimonKnigge,we can solve it in $$$O(m^2 \times n^3)$$$

Full text and comments »

  • Vote: I like it
  • +53
  • Vote: I do not like it