Блог пользователя sys.

Автор sys., 4 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

Автор sys., 4 года назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор sys., 5 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +175
  • Проголосовать: не нравится

Автор sys., история, 5 лет назад, По-английски

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)$$$

Полный текст и комментарии »

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится