---Grigor---'s blog

By ---Grigor---, history, 2 years ago, In Russian,

Здравствуйте друзья,

На практике возникла подобная задача, нуждаюсь в помощи. Подскажите, пожалуйста, как бы вы решили?

Даны множество людей и множество предметов. Каждый человек имеет определенное количество денег, каждый предмет имеют свою стоимость. Все значения целочисленны. Может ли это множество людей купить все имеющиеся предметы?

Каждый человек может купить сколько угодно предметов (если хватает денег), каждый предмет может быть куплен только одним человеком.

Я думал решать через поток в двудольном графе, но не знаю как запретить наличие частично насыщенных ребер в результирующем потоке.

Заранее благодарю!

Read more »

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

By ---Grigor---, 5 years ago, In Russian,

Всем привет,

Хотелось бы узнать, есть ли какая-нибудь информация об очередном сезоне Opencup? Дело в том, что в форме регистрации на XV Открытую Всесибирскую олимпиаду (olympic.nsu.ru) присутствует поле "Логин Открытого Кубка", но неясно что с ним делать. Ни на opencup.ru ни на snarknews.info о графике проведения Opencup не написано, а логинов нового сезона у нас пока что нет.

Если кто-нибудь знает, будет ли Всесибирская Олимпиада являться также этапом Открытого Кубка, поделитесь пожалуйста информацией.

Заранее благодарю.

Read more »

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

By ---Grigor---, 9 years ago, In English,
This problem can be solved in linear time, using the following idea:
1. If desired prefix and suffix intersect, then their common part is remaining with the initial sign and
therefore, this case is equivalent to the case when we take the same suffix and prefix, but without their common part
:

(s1 [s2 )s3 ] is equal to (s1)s2[s3] (s1,s2,s3 - some subsequences).
2. Let the sum of elements A1 .. An be equal to S. Then when inverting signs we get -A1, -A2 .. -An, and the sum is thereafter changed to -S, i.e. sum of elements on the segment will just change its' sign when inverting the whole segment's signs.
3. One can consider the initial problem as follows: we have to choose a consecutive subsequence (the part of the initial sequence, remaining between suffix and prefix), and invert all the numbers remaining out of it. Considering the sum of the whole sequence be S, and the sum of the target subsequence as S1 , the total sum will be equal to -(S-S1) + S1 = 2*S1 - S  -  this is the value, we want to get. S is a constant, therefore to maximize this value, we just have to maximize S1, i.e. find a consecutive subsequence of the initial sequence that has the biggest sum, and this can be done in linear as follows:
mx = 0;
for(i=0;i<n;++i)
{
sum += a[i];
if(sum < 0)
sum = 0;
mx = max(mx, sum);
}

Read more »

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