Задачи для разминки программистов

[Evgeniy Sklyarevskiy]

Вот здесь задачи (http://projecteuler.net/problems) для разминки программистов, некоторые подойдут и в этот раздел, только надо правильно перевести с английского.

Как точно перевести эту задачу (она там № 11):
What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid? — о каких четырех числах (номерах) решетки идет речь?

[Shuhrat Ismailov]

Как точно перевести эту задачу (она там № 11):

Цитата: What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?
— о каких четырех числах (номерах) решетки идет речь?
По -нашему будет так.
Какое наибольшее значение может принимать произведение четырех соседних чисел при условии, что они находятся на одной линии таблицы размером 20 на 20?
ЗЫ. Под линией понимается не только строка или столбец, может быть и диагональ. Важно лишь, что все числа соседние.

[Akmal Bafoev]

Вот здесь задачи (http://projecteuler.net/problems) для разминки программистов, некоторые подойдут и в этот раздел, только надо правильно перевести с английского.

Как точно перевести эту задачу (она там № 11):
What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid? — о каких четырех числах (номерах) решетки идет речь?

решается тупым перебором меньше чем за 1000 итераций.

[Evgeniy Sklyarevskiy]

таблицы размером 20 на 20 Меня смущает устройство этой таблиц: там в строках вписаны числа натурального ряда? Тогда в столбцах одинаковые числа? Или наоборот? Или произвольно расставлены числа в ячейках?

[Akmal Bafoev]

таблицы размером 20 на 20 Меня смущает устройство этой таблиц: там в строках вписаны числа натурального ряда? Тогда в столбцах одинаковые числа? Или наоборот?

вы по ссылке сходите.

[Evgeniy Sklyarevskiy]

решается тупым перебором меньше чем за 1000 итераций + надо все время помнить наибольшее значение произведения.

[DarkUser]

What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?Скучно-же...
я понимаю, там - вывести SQL запросом все целые числа от 1 до N, не используя таблиц. Или - вычислить какими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 центу?

[Evgeniy Sklyarevskiy]

вы по ссылке сходите. ааа спасибо понял!

[Akmal Bafoev]

решается тупым перебором меньше чем за 1000 итераций + надо все время помнить наибольшее значение произведения.

это не проблема.
всё что нужно конкретно для этой задачи если забить на то какие числа в полях - 2 переменных для хранения максимального произведения и текущего, 12 бит для счётчиков итераций, 12 бит для координат максимального произведения.

[Shuhrat Ismailov]

Меня смущает устройство этой таблиц
Наверняка таблицы произвольные, без изюминок.
На входе - произвольная числовая матрица порядка 20 на 20, на выходе четыре соседних элемента с индексами, доставляющие макимум произведению и само это максимальное произведение.

[Nadir Zaitov]

решается тупым перебором меньше чем за 1000 итераций.1000 итераций на 400 элементов таблицы.... серьезное заявление :)

[Akmal Bafoev]

решается тупым перебором меньше чем за 1000 итераций.1000 итераций на 400 элементов таблицы.... серьезное заявление :)

да, я наврал.
(20+1-4)^2*4 = 1156.

[JH]

20 строк, по 17 итераций = 340
20 столбцов, по 17 итераций = 340
потом диагональные строчки длиной от четырех клеток, всего 578

Итого 1258

[Nadir Zaitov]

1156.
1258А что такое итерация?
Давайте определимся, а то можно и в одном двойном цикле с тремя условиями все решить (это 20^2 или даже 20^2 - 3^2).

Я предлагаю считать количество чтений данных из таблицы

Вариант 1): БЕЗ КЕША: Без сохранения временных данных;
Вариант 2): С КЕШЕМ: с сохранением трех значений чисел.

[JH]

У меня получается, что без использования сложных схем, в лоб, нужно 1258 раз считать четыре элемента из таблицы, перемножить и, при необходимости, обновить текущее максимальное произведение

[Dolphin]

А мне лень думать. Придумайте алгоритм, а йа его к CUDA приспособлю - это уже интересно )

[DarkUser]

С КЕШЕМ: с сохранением трех значений чисел.Можно не кешировать, а просто сравнивать два элемента по обе стороны от тех 3-х, и перемножать с наибольшим.

[Nadir Zaitov]

1258 раз считать четыре элемента из таблицыили 391 раз считать до 10 элементов, сделав три сравнения для выбора какие именно элементы считывать. Тут вопрос сложности итерации. В чем ее считать?

[Nadir Zaitov]

Можно не кешировать, а просто сравнивать два элемента по обе стороны от тех 3-х, и перемножать с наибольшим.Кешировать нужно для того, чтобы на каждом шагу не считывать все 4 элемента. С кешем можно считывать в варианте расчетов JH всего 20 элементов, а не 17*4 элемента (хотя можно свести к 17*2-1 считыванию)

[Nadir Zaitov]

(20+1-4)^2*4 = 1156.не все явно варианты просмотрите... в последнем столбце и строке явно потеряны возможности.

[Nadir Zaitov]

Классическая задачка (Problem 31): In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
И алгоритм не так очевиден :)

[DarkUser]

Кешировать нужно для того, чтобы на каждом шагу не считывать все 4 элемента. С кешем можно считывать в варианте расчетов JH всего 20 элементов, а не 17*4 элемента (хотя можно свести к 17*2-1 считыванию)Это да, но я вообще операцию чтения, как хоть сколько-нибудь затратную, не стал бы учитывать. (или тогда уж закешировать все 400 элементов и не париться).

И алгоритм не так очевиден
Стандартный перебор, не?

[Nadir Zaitov]

Это да, но я вообще операцию чтения, как хоть сколько-нибудь затратную, не стал бы учитывать. (или тогда уж закешировать все 400 элементов и не париться).Тогда алгоритм в 400 шагов (итераций) решается, а не 1200 с гаком :). Потому и нужно решить что есть итерация.

Стандартный перебор, не?Софт быстренько так напишите? Хотя я не спорю - есть и затратный способ с полным перебором.

[JH]

Почему алгоритм не очевиден?

Вложенные циклы

lb2 от 0 до 1
lb1 от 0 до 2-lb2
p50 от 0 до ABS((2-2*lb2-lb1)/0.50)
p20 от 0 до ABS((2-2*lb2-lb1-0.50*p50)/0.20)
p10 от 0 до ABS((2-2*lb2-lb1-0.50*p50-0.20*р)/0.10)
p5 от 0 до ABS((2-2*lb2-lb1-0.50*p50-0.20*р-0.10*р10)/0.05)
p2 от 0 до ABS((2-2*lb2-lb1-0.50*p50-0.20*р-0.10*р10-0.05*p5)/0.02)
p1=(2-2*lb2-lb1-0.50*p50-0.20*р-0.10*р10-0.05*p5-0.02*p2)/0.01

Даже на очень слабой машине отработает в мгновение ока, причем ни одного оборота цикла "впустую". Или опять будут неизвестные ранее ограничения?

[Nadir Zaitov]

Даже на очень слабой машине отработает в мгновение ока, причем ни одного оборота цикла "впустую". Или опять будут неизвестные ранее ограничения?Трудоемкость алгоритма высокая. Это и есть полный перебор.

[DarkUser]

Тогда алгоритм в 400 шагов (итераций) решается, а не 1200 с гаком . Потому и нужно решить что есть итерация.Ну, я-бы определил как умножение(деление/сравнение etc) двух чисел. (Тогда хотя бы было что оптимизировать)


Софт быстренько так напишите? Хотя я не спорю - есть и затратный способ с полным перебором.Могу либо быстро, либо оптимизировано. Это быстро: :)


(define (count-change amount)
(cc amount 8)
)

(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount (- kinds-of-coins 1))
(cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)
)
)
)
)

(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 2)
((= kinds-of-coins 3) 5)
((= kinds-of-coins 4) 10)
((= kinds-of-coins 5) 20)
((= kinds-of-coins 6) 50)
((= kinds-of-coins 7) 100)
((= kinds-of-coins 8) 200)
)
)

(count-change 200)

[Nadir Zaitov]

Код:Это что за язык. Я ничерта не понял.

[infoliokrat]

Классическая задачка (Problem 31...
А неклассическую и даже не решенную задачку можно предложить? (Может ее отсюда другие будут копировать, так как только что появилась, потому что зайдя на сайт прочитал:
http://uforum.uz/images/misc/birthday.gif (http://uforum.uz/calendar.php?do=getday&day=2012-02-04&sb=1)shuh2004 (http://uforum.uz/member.php?u=19201) (32)
Сегодня день рождения у http://uforum.uz/images/misc/birthday.gif (http://uforum.uz/calendar.php?do=getday&day=2012-02-04&sb=1)
и тут же вспомнил, как мне, второкурснику, председателю студсовета общежития декан физфака выговаривал за то, что в нескольких комнатах общежития студенты что-то отмечали... Даже не спрашивал что отмечают, попадались и студентки, записывал в блокнот № комнаты и шли дальше. Прошли только 2 этажа, он записал пяить !!! комнат. На другие этажи не пошли. Грозился выселить всех, но удалось уговорить простой арифметикой...(комендант, офицер запаса, стоял "смирно", потом улыбнулся) ибо когда он громко возмущался в кабинете коменданта общежития, то сказал такую фразу: я понимаю, что можно отмечать праздники, хотя бы день рождения. а тут- среда. середина недели!!! )

егодня день рождения у http://uforum.uz/images/misc/birthday.gif (http://uforum.uz/calendar.php?do=getday&day=2012-02-04&sb=1)shuh2004 (http://uforum.uz/member.php?u=19201) (32)

Задача: Сколько одновременно может отмечаться дней рождения студентами в общежитии, в котором 14 этажей, 1 служебный и два аспирантских, но на студенческих этажах по 14 блоков из 2 комнат (А и Б), а в каждой комнате по 4 студента?
Причем условимся, что дни рождения студент (ка) отмечает обязательно и распределены они равномерно, а год невисокосный. (Родившиеся 29 февраля тоже отмечают день рождения. Проверка проводилась в октябре).
Я ему сказал: Иван Павлович, ну ведь день рождения можно же, а вчера была стипендия, так что точно некоторые на сегодня перенесли день рождения! Буркнул - подумаю..., амнистия была получена. (Вариант: день рождения отмечается тогда, когда в блоке хотя бы 2 именинника, причем даже в соседние дни).

[DarkUser]

Это что за язык. Я ничерта не понял.LISP (Scheme) :)

вот на паскале:

const
Coins: array[1..8] of integer = (1, 2, 5, 10, 20, 50, 100, 200);

function Calc(Amount: integer; ACoinSetId: Integer): integer;
begin
if Amount = 0 then
begin
Result := 1;
Exit;
end;
if (Amount < 0) or (ACoinSetId = 0) then
begin
Result := 0;
Exit;
end;

Result := Calc(Amount, ACoinSetId - 1)
+ Calc(Amount - Coins[ACoinSetId], ACoinSetId);
end;

begin
Writeln(Calc(200, Length(Coins)));
Readln;
end.


Рекурсивно вычисляем {к-во способов разменять сумму N с помощью K достоинств монет}, как сумму {способов разменять N с помощью K-1 достоинств монет} и {способов разменять N-Достоинство[K] с помощью K достоинств монет}. (Алгоритм нагло честно сперт из библии SICP (http://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs) )

[Nadir Zaitov]

Алгоритм нагло честно сперт из библии SICPДаже это полный перебор. Там нет алгоритма как это решить квадратной таблицей (M,N), где N - число монет, a M - число, которое раскладывается? Решается за время, линейное от числа монет или числа M. Ваш же (т.е. их) алгоритм не линеен. Потому и говорил, что задача - классика (замена количества проходов на затраты памяти).

[DarkUser]

Даже это полный перебор.Согласен. Есть вариант - сохранять уже вычисленный результат, в хеш-таблице (Где ключ - комбинация оставшейся суммы и номера монеты).
UPD. Скорость вырастает - раз в 100

[Nadir Zaitov]

У меня получился такой код (Pascal ABC):Const MoneyLimit=200;
Const CoinsLimit=8;
Const Coins: array[1..CoinsLimit] of integer = (1, 2, 5, 10, 20, 50, 100, 200);


var iCalc:Array [1..MoneyLimit, 1..CoinsLimit] of Integer;
iM: Integer;
iCoin: Integer;
begin
{Всегда только для 1 пенни есть только одно решение}
For iM:=1 to MoneyLimit do iCalc[iM,1]:=1;
For iCoin:=2 to CoinsLimit do
For iM:=1 to MoneyLimit do
if iM < Coins[iCoin] then
{Если до номинала монетки не добрались, то зачем считать?}
iCalc[iM,iCoin]:=iCalc[iM,iCoin-1]
else
if iM = Coins[iCoin] then
{Если номинал, то нужно помнит, что у нас таблица, а не рекурсия}
iCalc[iM,iCoin]:=iCalc[iM,iCoin-1] + 1
else {Если больше номинал, то все стандартно}
iCalc[iM,iCoin]:=iCalc[iM,iCoin-1] + iCalc[iM-Coins[iCoin],iCoin];
Writeln(iCalc[MoneyLimit, CoinsLimit], ' варианта')
end.

Кстати - ответ у меня получился такой: 73682 варианта. Вдруг у меня ошибка в коде?

[DarkUser]

ответ у меня получился такой: 73682 варианта. Вдруг у меня ошибка в коде?У меня столько же.

[Nadir Zaitov]

Согласен. Есть вариант - сохранять уже вычисленный результат, в хеш-таблицеЯ его и использовал. Только почему хеш, а не кеш?

[DarkUser]

Я его и использовал. Только почему хеш, а не кеш?Хэш-таблица (http://ru.wikipedia.org/wiki/Хеш-таблица) - меньше места занимает. В отличие от кеш-массива. Хотя по скорости и проигрывает. А так - да, смысла особого нету.

[Nadir Zaitov]

Хэш-таблица - меньше места занимает. В отличие от кеш-массива. Хотя по скорости и проигрывает. А так - да, смысла особого нету.Век живи - век учись. Уверен, они могут раза в три требования по памяти уменьшить.

[Nadir Zaitov]

Problem 370Let us define a geometric triangle as an integer sided triangle with sides a b c so that its sides form a geometric progression, i.e. b^2 = a · c .

An example of such a geometric triangle is the triangle with sides a = 144, b = 156 and c = 169.

There are 861805 geometric triangles with perimeter 10^6 .

How many geometric triangles exist with perimeter 2.5·10^13 ?Вот вам задачка не для "полного перебора". Какие идеи?

[German Stimban]

Интересная задачка - на вход подаётся математическое выражение. На выходе его нужно привести к упрощённому виду:
Например
a+a+b+b+c-a --> a+2*b+c
(a+b)*(a+b) --> a*a+2*a*b+b*b
(a+b)*(a+c) --> a*a+a*b+a*c

[Akmal Bafoev]

Интересная задачка - на вход подаётся математическое выражение. На выходе его нужно привести к упрощённому виду:
Например
a+a+b+b+c-a --> a+2*b+c
(a+b)*(a+b) --> a*a+2*a*b+b*b
(a+b)*(a+c) --> a*a+a*b+a*c

тут я вижу приведение к полиномиальному виду.

[DarkUser]

a+a+b+b+c-a --> a+2*b+c
(a+b)*(a+b) --> a*a+2*a*b+b*b
(a+b)*(a+c) --> a*a+a*b+a*c
Не совсем понял, в чем упрощение у 2-го и 3-го примеров.
И какие операции могут встречаться, кроме сложения/умножения/скобок?

[DarkUser]

Имхо, решается просто, приведением к выполнению операции на двумя полиномами
(сложность полиномов зависит от словаря. Исходя из данных примеров:
Sum(Ki{* (a|b|c)}{* (a|b|c)}{* (a|b|c)}) ).
Сама операция над полиномами, сводится к перепросчитыванию индексов Ki, в зависимости от оператора.

[Nadir Zaitov]

математическое выражениеА если там функциональное выражение. Ну элементарно типа Sin(2x)/(2sin(x)) должно упроститься до cos(x). Nkn все ж входящие выражения имеют фиксированный вид?

[German Stimban]

Не совсем понял, в чем упрощение у 2-го и 3-го примеров.
И какие операции могут встречаться, кроме сложения/умножения/скобок?
Ну в смысле раскрытие скобок и т.д.
математическое выражениеА если там функциональное выражение. Ну элементарно типа Sin(2x)/(2sin(x)) должно упроститься до cos(x). Nkn все ж входящие выражения имеют фиксированный вид?
Будем считать, что только арифметические действия и скобки. Причём скобки могут быть вложенными.

[Nadir Zaitov]

Ну в смысле раскрытие скобок и т.д.Задачка кажется простой. Если задать формат ввода и вывода, то делать программку кажется не проблема.

[German Stimban]

Задача не только и не столько для программистов, будет интересна математикам.

Есть число N, которое представляет собой сумму квадратов четырёх различных чисел.
Минимально возможное значение N=30=1+4+9+16
А какое максимально возможное значение N? Или ряд бесконечен?

[JH]

Герман, конечно же, бесконечен. Мне кажется, это настолько очевидно, что даже не знаешь, как приступить к доказательству.

[DarkUser]

Есть число N, которое представляет собой сумму квадратов четырёх различных чисел.
Минимально возможное значение N=30=1+4+9+16
А какое максимально возможное значение N? Или ряд бесконечен?
Пусть ряд конечен, и N - максимальная сумма.
Но тогда можно составить новую сумму, N1 = N*N + (N+1)*(N+1) + (N+2)*(N+2) + (N+3)*(N+3).
N1 > N => максимально большого N не существует.

[Nadir Zaitov]

Есть число NНужны еще условия на N. Типа оно само является кубом простого числа или произведением трех простых чисел. Что-нибудь достаточно дурацкое, чтобы исключить возможность представления в разумном виде.

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

[German Stimban]

Есть число N, которое представляет собой сумму квадратов четырёх различных чисел.
Минимально возможное значение N=30=1+4+9+16
А какое максимально возможное значение N? Или ряд бесконечен?
Чёрт, задачу сформулировал неверно.
Существует ли максимальное число, которое невозможно представить в виде суммы квадратов четырёх различных чисел

[DarkUser]

Существует ли максимальное число, которое невозможно представить в виде суммы квадратов четырёх различных чиселМне кажется, что не существует. Чем дальше, тем больше таких чисел будет попадаться. А вот вычислением минимального можно заняться. Хотя, имхо, все опять к NP-перебору сведется. скучно )

[German Stimban]

DarkUser, 30=1+4+9+16=1*1+2*2+3*3+4*4

[Nadir Zaitov]

DarkUser, 30=1+4+9+16=1*1+2*2+3*3+4*4

Герман, Дакюзер уже доказал вроде б, что такого числа нет. Если бы такое число N было бы, то возьмем его квадрат и добавим 14 = 1²+3²+3²
получим новое число M, такое что M = 1²+2²+3²+4²

Герман... я опять ошибся. Минимальное нужно найти число или максимальное?

[German Stimban]

Минимальное нужно найти число или максимальное?
Алексей предложил минимальное, я сказал, что оно равно 30.

А в моей задаче надо найти максимальное число, которое нельзя выразить суммой четырёх квадратов

[DarkUser]

Алексей предложил минимальное, я сказал, что оно равно 30.Теперь я сформулировал неверно :) Я имел ввиду, минимального НЕ представимого суммой 4-х квадратов.
Хотя если разных и больших 0, то это уже N = 1.

[Nadir Zaitov]

А в моей задаче надо найти максимальное число, которое нельзя выразить суммой четырёх квадратовТут важно слово "разных". Так как иначе это не есть истина (http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9B% D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6%D0%B0_%D0%BE_% D1%81%D1%83%D0%BC%D0%BC%D0%B5_%D1%87%D0%B5%D1%82%D 1%8B%D1%80%D1%91%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1 %80%D0%B0%D1%82%D0%BE%D0%B2).

[Elementar]

Предлагаю следующую задачку:

На столе лежит стопка из N монет (N - четное). Часть из них повернута гербом, остальные решкой. Не известно какие как повернуты, известно лишь, что K из них (K<=N) повернуты гербом.
За один ход можно либо перевернуть какую-то монету, либо переместить какую-то монету во вторую стопку.
Найти минимальное количество ходов, за которое мы можем получить 2 стопки монет, в каждой из которых будет одинаковое число монет, повернутых гербом.

[Nadir Zaitov]

Предлагаю следующую задачку:

На столе лежит стопка из N монет (N - четное). Часть из них повернута гербом, остальные решкой. Не известно какие как повернуты, известно лишь, что K из них (K<=N) повернуты гербом.
За один ход можно либо перевернуть какую-то монету, либо переместить какую-то монету во вторую стопку.
Найти минимальное количество ходов, за которое мы можем получить 2 стопки монет, в каждой из которых будет одинаковое число монет, повернутых гербом.В задаче чего-то не хватает. Части условия, например.

[Ildar Valiev]

На столе лежит стопка из N монет (N - четное). Часть из них повернута гербом, остальные решкой. Не известно какие как повернуты, известно лишь, что K из них (K<=N) повернуты гербом.
За один ход можно либо перевернуть какую-то монету, либо переместить какую-то монету во вторую стопку.
Найти минимальное количество ходов, за которое мы можем получить 2 стопки монет, в каждой из которых будет одинаковое число монет, повернутых гербом.
Из данного условия:
При самом благополучном стечении обстоятельств, ответ будет К/2 для четного К, и (К-1)/2 + 1 для нечетного.
При самом неблагополучном стечении - К*2 для К любой четности.

[Nadir Zaitov]

Из данного условия:
При самом благополучном стечении обстоятельств, ответ будет К/2 для четного К, и (К-1)/2 + 1 для нечетного.
При самом неблагополучном стечении - К*2 для К любой четности.А расписать?

[Elementar]

В задаче чего-то не хватает. Части условия, например.

На столе лежит стопка из N монет (N - четное). Часть из них повернута гербом, остальные решкой. Не известно какие как повернуты, известно лишь, что K из них (K<=N) повернуты гербом.

За один ход можно либо перевернуть какую-то монету, либо переместить какую-то монету из нашей изначальной стопки во вторую стопку.

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

Надеюсь, стало понятнее.

[Elementar]

Из данного условия:
При самом благополучном стечении обстоятельств, ответ будет К/2 для четного К, и (К-1)/2 + 1 для нечетного.
При самом неблагополучном стечении - К*2 для К любой четности.

Ответ не должен зависеть от благополучного или неблагополучного стечения обстоятельств :)

[JH]

Перенесем К монет во вторую кучку (К ходов, итого К)
При этом во второй кучке оказалось Х монет, повернутых гербом вверх, и К-Х монет гербом вниз. В первой же кучке оказалось К-Х монет гербом вверх.
Теперь каждую монету во второй кучке переворачиваем (К ходов, итого 2К).
В итоге во второй кучке оказывается К-Х монет гербом вверх, как и в первой.
Получается, что нужно сделать 2К ходов.
В принципе, если К>N/2, то на втором ходу нужно переворачивать первую кучку (в ней монет меньше), и тогда общая сумма ходов будет К+(N-K)=N

Полученный ответ: 2К или N, whichever less.

Но как доказать, что это именно минимальное число ходов, думать не хочу :)

[Nadir Zaitov]

Надеюсь, стало понятнее.разобрался. Я не так понял задачку.

[Elementar]

Перенесем К монет во вторую кучку (К ходов, итого К)
При этом во второй кучке оказалось Х монет, повернутых гербом вверх, и К-Х монет гербом вниз. В первой же кучке оказалось К-Х монет гербом вверх.
Теперь каждую монету во второй кучке переворачиваем (К ходов, итого 2К).
В итоге во второй кучке оказывается К-Х монет гербом вверх, как и в первой.
Получается, что нужно сделать 2К ходов.
В принципе, если К>N/2, то на втором ходу нужно переворачивать первую кучку (в ней монет меньше), и тогда общая сумма ходов будет К+(N-K)=N

Полученный ответ: 2К или N, whichever less.

Да, алгоритм верный.

[Nadir Zaitov]

В принципе, если К>N/2, то на втором ходу нужно переворачивать первую кучкуВот тут проблема. Переворачивать можно только монету и видимо верхнюю.

[Elementar]

Вот тут проблема. Переворачивать можно только монету и видимо верхнюю.

За один ход можно либо перевернуть какую-то монету, либо переместить какую-то монету из нашей изначальной стопки во вторую стопку.

В следующий раз буду аккуратней составлять условия :)

[Elementar]

Тогда следующая задачка (возможно кому-то она покажется программисткой, кому-то математической).

Есть N монет, стоящих подряд. За один ход можно выбрать некоторую последовательность стоящих подряд монет (длина последовательности <= N), длина которой обязательно должна равняться некоторой степени двойки (2, 4, 8, ...), и переместить самую старую монету группы в еѐ начало, передвинув на одну позицию от начала все монеты группы, следовавшие ранее до самой старой.

Необходимо для заданного количества монет подсчитать минимальное число операций, которое потребуется для их упорядочивания по возрастанию даты чеканки согласно описанному алгоритму в худшем случае.

[JH]

Перенесем К монет во вторую кучку (К ходов, итого К)
При этом во второй кучке оказалось Х монет, повернутых гербом вверх, и К-Х монет гербом вниз. В первой же кучке оказалось К-Х монет гербом вверх.
Теперь каждую монету во второй кучке переворачиваем (К ходов, итого 2К).
В итоге во второй кучке оказывается К-Х монет гербом вверх, как и в первой.
Получается, что нужно сделать 2К ходов.
В принципе, если К>N/2, то на втором ходу нужно переворачивать первую кучку (в ней монет меньше), и тогда общая сумма ходов будет К+(N-K)=N

Полученный ответ: 2К или N, whichever less.

Да, алгоритм верный.

Не совсем верный. Вариант с N ходами (переворачиванием монет в первой стопке) выдает одинаковое количество монет гербом вниз, что не совсем соответствует условию. Так что вторую половину решения вычеркиваем. Ответ: 2К

[Elementar]

Не совсем верный. Вариант с N ходами (переворачиванием монет в первой стопке) выдает одинаковое количество монет гербом вниз, что не совсем соответствует условию. Так что вторую половину решения вычеркиваем. Ответ: 2К

Ну почему, все верно. Просто там кучки чуть по-другому формировать надо :)

[JH]

Ну почему, все верно. Просто там кучки чуть по-другому формировать надо
А, понял. Получается, так:
Если 2К>N, то решение меняем. Сначала переносим N-K монет во вторую кучку.
Во второй кучке оказывается Х монет гербом вверх, в первой (в которой осталось К монет) оказывается К-Х монет гербом вверх (и Х гербом вниз). Переворачиваем монеты в первой кучке и получаем в обеих кучках по Х монет гербом вверх, итого N ходов.

Недокрутил решение в первый раз.

[Elementar]

А, понял. Получается, так:
Если 2К>N, то решение меняем. Сначала переносим N-K монет во вторую кучку.
Во второй кучке оказывается Х монет гербом вверх, в первой (в которой осталось К монет) оказывается К-Х монет гербом вверх (и Х гербом вниз). Переворачиваем монеты в первой кучке и получаем в обеих кучках по Х монет гербом вверх, итого N ходов.

Недокрутил решение в первый раз.

Да, именно так. Я почему-то подумал, что именно это и было в первом посте.

[Ildar Valiev]

Elementar, 2K получается в "худшем" случае. В "лучшем" будет K/2 для четных и (K-1)/2 + 1 для нечетных. Под лучшем случаем полагается, когда монеты, гербом ввех лежат на вершине стопки. Для этого достаточно переложить K/2 или (K-1)/2 монет во вторую стопку для четного и нечетного K соответственно. Для нечетных также нужно будет перевернуть одну монету гербом вверх из первой стопки. Но так как задание было найти для любого случая, то да, ответ - 2K.

[Elementar]

Elementar, 2K получается в "худшем" случае. В "лучшем" будет K/2 для четных и (K-1)/2 + 1 для нечетных. Под лучшем случаем полагается, когда монеты, гербом ввех лежат на вершине стопки. Для этого достаточно переложить K/2 или (K-1)/2 монет во вторую стопку для четного и нечетного K соответственно. Для нечетных также нужно будет перевернуть одну монету гербом вверх из первой стопки. Но так как задание было найти для любого случая, то да, ответ - 2K.

Выше уже упоминалось, что нужно брать либо min(2K, N), либо нужно рассмотреть 2 случая K<=N/2 и K>N/2.

Также в условии было сказано, что "Не известно какие как повернуты". Поэтому я не совсем понимаю, что Вы понимаете под "лучшим" случаем.

[Ildar Valiev]

Также в условии было сказано, что "Не известно какие как повернуты".
Даже верхние в стопках?

[Elementar]

Даже верхние в стопках?

"Не известно какие как повернуты". Про верхние в том числе :)

Так что там со второй задачей? Есть идеи?

[Ildar Valiev]

"Не известно какие как повернуты". Про верхние в том числе
Значит я не так понял. :)

Так что там со второй задачей? Есть идеи?
Пока в голову только сортировка "методом пузырька" приходит :)
Хотя есть еще идея, но ее надо проверить:
Берем самую большую "рамку" (наибольшую позволенную последовательность, которая является степенью числа 2) и проходим этой рамкой по всей последовательности N, сдвигая ее на 1 монету при каждом шаге. Затем уменьшаем рамку в два раза и так же проходим по всей последовательности. Продолжаем до тех пор, пока длина рамки не станет равна 1.

[JH]

Как-то связано с бинарной записью, не догоню, как. Завтра надо на свежую подумать

[Elementar]

Хотя есть еще идея, но ее надо проверить:
Берем самую большую "рамку" (наибольшую позволенную последовательность, которая является степенью числа 2) и проходим этой рамкой по всей последовательности N, сдвигая ее на 1 монету при каждом шаге. Затем уменьшаем рамку в два раза и так же проходим по всей последовательности. Продолжаем до тех пор, пока длина рамки не станет равна 1.

Ой, уже на примере из трех монет не работает: 3 2 1 -> 2 1 3.

[Ildar Valiev]

Ой, уже на примере из трех монет не работает: 3 2 1 -> 2 1 3.
Да, что-то я совсем не подумал :)


Тогда решение такое, правда не знаю насколько оно оптимально:
Пусть
N - общее кол-во монет,
O - кол-во упорядоченных монет,
L - сколько монет осталось упорядочить,
S - размер рамки.
Примечание: нумерация монет начинается с нуля.

шаг 1. L = N, O = 0;
шаг 2. S = максимальная степень двойки, так, чтобы S <= L;
шаг 3. если S = L (то есть кол-во оставшихся монет кратно 2), то передвигаем наименьшую монету вперед, переход на шаг 6;
шаг 4. накладываем рамку на конец всей последовательности, передвигаем наименьшую монету вперед;
шаг 5. накладываем рамку на монету под номером O (первую неупорядоченную), передвигаем наименьшую монету вперед;
шаг 6. O++, L--;
шаг 7. если L = 1, перейти на шаг 9;
шаг 8. перейти на шаг 2;
шаг 9. конец.

Сложность алгоритма получается (N-1) * 2 - |log2(N)|

[Elementar]

шаг 3. если S = L (то есть кол-во оставшихся монет кратно 2), то передвигаем наименьшую монету вперед, переход на шаг 6;


Тут баг, не кратно, а степень двойки.


Сложность алгоритма получается (N-1) * 2 - |log2(N)|

Ну или тупо O(N). Но алгоритм верный. Попытайтесь доказать (по индукции, например). Вообще идея с псевдокодом меня немного улыбнула :)

Тогда усложнение задачи:
Предположим, что N достаточно большое (10^18, например) и за разумное время O(N) не сработает. Можно ли быстрее как-нибудь?

[JH]

Я так смотрел. Берем самую большую "рамку" (назовем ее Smax), не превышающую N (т.е. для N=20 рассматриваем рамку из 16 монет), и накладываем ее с КОНЦА первоначальной цепочки, с выполнением операции перевода старшей монеты в начало, на каждом шаге сдвигая рамку на 1 шаг ближе к началу. Это гарантированно "поставит на место" самую первую монету в искомой последовательности. Потом повторяем операции, опять с конца начальной цепочки, сделав на один шаг меньше, т.е. первую, уже стоящую на месте монету, не трогаем. Это гарантированно упорядочит вторую монету. И так далее, пока не упорядочатся монеты с первой до N-Smax+1 (для 20 монет это упорядочит с первой по пятую). Затем с оставшимися монетами проводим то же самое, взяв следующую, меньшую размером, рамку. И до победного конца. Не знаю, насколько это будет долгий процесс при 10^18.

[JH]

Я так смотрел. Берем самую большую "рамку" (назовем ее Smax), не превышающую N (т.е. для N=20 рассматриваем рамку из 16 монет), и накладываем ее с КОНЦА первоначальной цепочки, с выполнением операции перевода старшей монеты в начало, на каждом шаге сдвигая рамку на 1 шаг ближе к началу. Это гарантированно "поставит на место" самую первую монету в искомой последовательности. Потом повторяем операции, опять с конца начальной цепочки, сделав на один шаг меньше, т.е. первую, уже стоящую на месте монету, не трогаем. Это гарантированно упорядочит вторую монету. И так далее, пока не упорядочатся монеты с первой до N-Smax+1 (для 20 монет это упорядочит с первой по пятую). Затем с оставшимися монетами проводим то же самое, взяв следующую, меньшую размером, рамку. И до победного конца. Не знаю, насколько это будет долгий процесс при 10^18.

Поправка, по дальнейшему размышлению.
Для приведения на место 1-й монеты достаточно двух операций. Накладываем самую большую рамку сначала на конец, потом на начало. И так дальше, по две операции на каждую цифру. Когда диапазон неупорядоченных монет сузится до размера самой большой рамки, достаточно наложить ее один раз и затем переходить на следующую, меньшую по размеру, рамку. Итого на каждую монету по 1 или 2 операции. Для 10^18 придется сделать 2*10^18 операций максимум.

[DarkUser]

Предположим, что N достаточно большое (10^18, например) и за разумное время O(N) не сработает. Можно ли быстрее как-нибудь?Мне кажется, что как минимум одну неупорядоченную монету, как минимум один раз таки придется выпихнуть в начало. Что, в худшем случае, уже дает N перестановок.

[Elementar]

Поправка, по дальнейшему размышлению.
Для приведения на место 1-й монеты достаточно двух операций. Накладываем самую большую рамку сначала на конец, потом на начало. И так дальше, по две операции на каждую цифру. Когда диапазон неупорядоченных монет сузится до размера самой большой рамки, достаточно наложить ее один раз и затем переходить на следующую, меньшую по размеру, рамку. Итого на каждую монету по 1 или 2 операции.

Да, верно, и теперь работает за O(N). И читается приятней псевдокода :)

Для 10^18 придется сделать 2*10^18 операций максимум.

Это многовато :) Учитывая, что компьютер выполняет 10^9 операций в секунду, для N=10^18 потребуется 10^9 секунд, что примерно 32 года :mellow: (если я ошибся, поправьте).

UPD. Здесь я имел ввиду сложность подсчета, с ответом все в порядке.

[Elementar]

Мне кажется, что как минимум одну неупорядоченную монету, как минимум один раз таки придется выпихнуть в начало. Что, в худшем случае, уже дает N перестановок.

Ну да, ходов как минимум больше либо равно N.

Я имел ввиду уменьшить сложность алгоритма - подсчета этого количества ходов. Простое моделирование Ildar Valiev и JH выполняется за O(N). Может можно быстрее найти ответ?

З.Ы. Видимо я опять неясно выразился :)

[Nadir Zaitov]

Тогда следующая задачка (возможно кому-то она покажется программисткой, кому-то математической).

Есть N монет, стоящих подряд. За один ход можно выбрать некоторую последовательность стоящих подряд монет (длина последовательности <= N), длина которой обязательно должна равняться некоторой степени двойки (2, 4, 8, ...), и переместить самую старую монету группы в еѐ начало, передвинув на одну позицию от начала все монеты группы, следовавшие ранее до самой старой.

Необходимо для заданного количества монет подсчитать минимальное число операций, которое потребуется для их упорядочивания по возрастанию даты чеканки согласно описанному алгоритму в худшем случае.Сложность такой задачи должна быть действительно O(1), так как по заданному N "число операций" должно "в лоб" считаться, а не проводиться.
И она уже подсчитана:
Сложность алгоритма получается (N-1) * 2 - |log2(N)|
Точнее нужно б написать так: Ответ: для любого N нужно (N-1) * 2 - [log2(N)] операций

[Nadir Zaitov]

З.Ы. Видимо я опять неясно выразилсяКстати. Операция поиска наибольшего элемента из 2^k элементов на практике очень затратная. Интересно, откуда у Вас такая задачка родилась?

[Elementar]

Сложность такой задачи должна быть действительно O(1), так как по заданному N "число операций" должно "в лоб" считаться, а не проводиться.

Ну если быть более точным, то на вычисление log(N) потребуется уже O(log(N)) действий. Но при N<=10^18 это как раз будет O(1).

Кстати. Операция поиска наибольшего элемента из 2^k элементов на практике очень затратная. Интересно, откуда у Вас такая задачка родилась?

Эту задачку я встретил на одном ACM-like соревновании. Вот решил ею поделиться :)

Тогда следующая задачка (совсем несложная и тоже с одного соревнования).

В офисе есть N компьютеров. Чтобы соединить каких-то два компьютера по сети, нужно заплатить системную администратору 10 у.е. Требуется найти минимальную сумму, которую мы заплатим системному администратору, чтобы соединить компьютеры по сети таким образом, чтобы при выключении каких-то произвольных двух компьютеров (а такое в офисе бывает часто), все компьютеры были достижимы по сети (либо напрямую, либо через несколько других компьютеров).

Можно считать, что N>=4. Ответ обосновать :)

[Nadir Zaitov]

log(N) потребуется уже O(log(N)) действий. Берется большинством процессоров за такт. (что сложного узнать номер старшего бита или цифру в экспоненте). Кажется так.

[Nadir Zaitov]

В офисе есть N компьютеров. Чтобы соединить каких-то два компьютера по сети, нужно заплатить системную администратору 10 у.е. Требуется найти минимальную сумму, которую мы заплатим системному администратору, чтобы соединить компьютеры по сети таким образом, чтобы при выключении каких-то произвольных двух компьютеров (а такое в офисе бывает часто), все компьютеры были достижимы по сети (либо напрямую, либо через несколько других компьютеров).
Можно считать, что N>=4. Ответ обосноватьМожно доказать, что любой компьютер должен быть подключен по крайней мере к трем разным компьютерам. Итого 15 баксов на компьютер уже гарантированы (если их больше и равно 4-м).

Для четырех мы сразу получаем симплекс.

Дальше еще не начал думать :)

[Vitaliy Fioktistov]

Количество соединений не регламентируется? То есть теоретически, при N=30, скажем, никто не запрещает соединить один компьютер с 29 оставшимися? ;)

[Elementar]

Можно доказать, что любой компьютер должен быть подключен по крайней мере к трем разным компьютерам. Итого 15 баксов на компьютер уже гарантированы (если их больше и равно 4-м).

Для четырех мы сразу получаем симплекс.


Да, все именно так :)

Количество соединений не регламентируется? То есть теоретически, при N=30, скажем, никто не запрещает соединить один компьютер с 29 оставшимися? ;)

К одному компьютеру можно проводить сеть сколько угодно раз. Более того, между двумя компьютерами можно провести соединение сколько угодно раз :) Главное не забыть, что нужно найти минимальную сумму у.е. :)

[Ildar Valiev]

В офисе есть N компьютеров. Чтобы соединить каких-то два компьютера по сети, нужно заплатить системную администратору 10 у.е. Требуется найти минимальную сумму, которую мы заплатим системному администратору, чтобы соединить компьютеры по сети таким образом, чтобы при выключении каких-то произвольных двух компьютеров (а такое в офисе бывает часто), все компьютеры были достижимы по сети (либо напрямую, либо через несколько других компьютеров).

Как сказал Nadir Zaitov, каждый компьютер должен должен быть соединен как минимум с 3 другими. Для этого замыкаем все компьютеры в кольцо. Итого получается N соединений и по 2 связи на компьютер. Остается соединить каждый компьютер с любым другим несоседним компьютером. Это получается N/2 соединений для четного кол-ва компьютеров и N/2 + 1 - для нечетного.

Общий ответ - 2N + [N/2]. Здесь, [] - символы окгругления вверх.

[Elementar]

Как сказал Nadir Zaitov, каждый компьютер должен должен быть соединен как минимум с 3 другими. Для этого замыкаем все компьютеры в кольцо. Итого получается N соединений и по 2 связи на компьютер. Остается соединить каждый компьютер с любым другим несоседним компьютером. Это получается N/2 соединений для четного кол-ва компьютеров и N/2 + 1 - для нечетного.

Общий ответ - 2N + [N/2]. Здесь, [] - символы окгругления вверх.

Либо опечатка, либо опечатка. С нижней оценкой согласен.

[Ildar Valiev]

Либо опечатка, либо опечатка. С нижней оценкой согласен.
Эээ.. это очепятка :)

Общий ответ - N + [N/2]. Здесь, [] - символы окгругления вверх.

[Elementar]

Эээ.. это очепятка :)

Общий ответ - N + [N/2]. Здесь, [] - символы окгругления вверх.

Да, теперь все верно. И нижняя оценка доказывает, что меньше сделать не можем. Похоже пришло время следующей задачи, которой пока у меня нет :)

[Elementar]

А все, придумал =)

Дана квадратная таблица NxN (N строк, N столбцов). Из клетки A можно перейти в клетку B, только если у них есть общая сторона (например, из клетки (3, 4) можно попасть в клетки (3, 3), (3, 5), (2, 4) и (4, 4) ). Можно ли, стартуя из произвольной клетки S, обойти все клетки ровно по одному разу и вернуться в клетку S? Ответ опять же обосновать :)

[German Stimban]

Можно ли, стартуя из произвольной клетки S, обойти все клетки ровно по одному разу и вернуться в клетку S?
Если N чётное. то можно

[Elementar]

Если N чётное. то можно

Почему? А если нечетное?

[JH]

Почему? А если нечетное? Раскрасим, как шахматную доску, и все станет понятно. Для того, чтобы обойти весь квадрат, нужно сделать N*N ходов. Причем последний ход приводит нас в исходную клетку. Так вот, фигура оказывается в клетке того же цвета на каждом втором ходу. В случае с нечетным числом клеток невозможно на нечетном ходу оказаться в клетке того же цвета.

[Elementar]

Раскрасим, как шахматную доску, и все станет понятно. Для того, чтобы обойти весь квадрат, нужно сделать N*N ходов. Причем последний ход приводит нас в исходную клетку. Так вот, фигура оказывается в клетке того же цвета на каждом втором ходу. В случае с нечетным числом клеток невозможно на нечетном ходу оказаться в клетке того же цвета.

Верно.

Тогда усложним задачу - пусть у нас есть куб с размерностями A, B, C, причем A*B*C четно (иначе все было бы совсем легко). Двигаться теперь можно по соседним клеткам, у которых есть общая сторона. Опять же когда будет существовать путь из какой-то вершины, проходящий по всем вершинам один раз, и заканчивающийся в ней?

[JH]

Elementar, все ваши задачки в этой теме - математические, и никакого отношения к программированию не имеют.

[Nadir Zaitov]

Elementar, все ваши задачки в этой теме - математические, и никакого отношения к программированию не имеют.Имеют прямое.
Можно решать полным перебором, а можно подумать. Это важно для любого программиста.

[Elementar]

Elementar, все ваши задачки в этой теме - математические, и никакого отношения к программированию не имеют.

Без математики далеко не уедешь :) Да и задачи я давал на конструктив, а не на реализацию. Тупая реализация не всегда позволит Вам решить задачку. Возьмите задачу 15 с projecteuler.net. http://projecteuler.net/problem=15 и решите ее без использования математики. Да и скучные очевидные задачи на реализацию ИМХО скукота.

[Nadir Zaitov]

Возьмите задачу 15 с projecteuler.net.1,37847E+11
Нет?

[Elementar]

1,37847E+11
Нет?

Так :) Обычный C(20, 40) :)

[Nadir Zaitov]

Обычный C(20, 40) Не стал ответ выставлять. Даю возможность другим подумать :).

[Nadir Zaitov]

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Понравилось. А ведь не так просто (просто цифры малые). Программку сделать легко. А как найти быстро (с наименьшими затратами времени)?
600851475143 = 71 × 1471 × 6857

[Elementar]

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Ниже алгоритм за O(sqrt(N)).Замечание 1. Собственный делитель числа не превосходит корня числа.Замечание 2. Если число делится на какой-то делитель, жадно делим на него пока можем.Замечание 3. Перебирая возможные делители по возрастанию и учитывая предыдущие 2 замечания, получим все простые делители.На основе этих двух замечаний придумываем алгоритм, работающий за O(sqrt(N)). Вообще факторизация очень сложная задача, это лучшее решение, которое я помню.SPOILER DETECTED :)

[Nadir Zaitov]

SPOILER DETECTEDНа самом деле можно уложиться в O(Sqrt(N)/Log(N)) если двигаться сразу по известным простым числам.

[Elementar]

На самом деле можно уложиться в O(Sqrt(N)/Log(N)) если двигаться сразу по известным простым числам.

Да, точно. совсем забыл об этом. Правда на нахождение самих простых до корня уйдет как раз O(sqrt(N)loglogN), даже если просеить решетом, но если мы их чудесным образом знаем, то да :)

Тогда следующая немного боянистая задачка. Двое играют в игру. Записана последовательность из нулей и единиц. Первый игрок называет какой-то отрезок [l, r], второй игрок - четное или нечетное количество единиц на нем. В итоге было задано последовательно N вопросов - ответов. Нужно найти первый ответ, который был гарантированно неверен.

Например:

1 5 четно
1 2 нечетно
4 5 нечетно
3 5 четно
7 10 четно

Ответ - 4, поскольку 4ый ответ не может быть согласован с первыми 3мя.

Решение как всегда обосновать :)

[Nadir Zaitov]

Ответ - 4, поскольку 4ый ответ не может быть согласован с первыми 3мя.

Решение как всегда обосноватьЖестоко :) Совсем уже неправильно в открытом виде сразу ответ давать... к тому же задачка не для программистов.

Ответ - 4, поскольку 4ый ответ не может быть согласован с первыми 3мя.Задача явно не так сформулирована. Могут быть первые три неверными. а 4-й верным. Где гарантия?

[Elementar]

Совсем уже неправильно в открытом виде сразу ответ давать... к тому же задачка не для программистов.

Думал, что с примером будет понятней. А программист вроде должен обладать базовыми знаниями алгоритмов, для решения задачки все равно потребуется программку написать :)

Задача явно не так сформулирована. Могут быть первые три неверными. а 4-й верным. Где гарантия?

Согласен, формулировка неполная. Нужно определить максимальное X такое, что существует последовательность удовлетворяющая первым X-1 вопросам-ответам, но последовательности, удовлетворяющей первым X вопросам-ответам не существует. В случае, если есть последовательность удовлетворяет всем N вопросам-ответам, тогда X = N+1.

[Nadir Zaitov]

Нужно определить максимальное X такое, что существует последовательность удовлетворяющая первым X-1 вопросам-ответам, но последовательности, удовлетворяющей первым X вопросам-ответам не существует. В случае, если есть последовательность удовлетворяет всем N вопросам-ответам, тогда X = N+1.Уже интересней.
А к решению линейных уравнений по модулю 2 это свести возможно?

[Elementar]

Уже интересней.
А к решению линейных уравнений по модулю 2 это свести возможно?

Вообще можно :) Правда, по-моему, немножко неэффективно получается (псевдополином) :)

[Nadir Zaitov]

Правда, по-моему, немножко неэффективно получаетсяКак раз таки нет. Если предположить, что знчения целы, то можно их считать как ноль или единицу. Метод Гауса работает на ура (пробовать подобрать треугольную матрицу. Причем добавлением следующего уравнения не сильно усложняет задачу. Вместо сложения и вычитания можно брать сразу команду XOR. делить ни на что не надо - у нас всегда единицы или нули.

[Elementar]

Как раз таки нет. Если предположить, что знчения целы, то можно их считать как ноль или единицу. Метод Гауса работает на ура (пробовать подобрать треугольную матрицу. Причем добавлением следующего уравнения не сильно усложняет задачу. Вместо сложения и вычитания можно брать сразу команду XOR. делить ни на что не надо - у нас всегда единицы или нули.

Ну ведь Гаусс будет работать за O(N*N*maxN), где maxN - длина объединения отрезков. Можно как-то отойти от СЛАУ по модулю 2 и свести к какой-нибудь другой задаче, основанной на четности-нечетности.

[Nadir Zaitov]

Можно как-то отойти от СЛАУ по модулю 2 и свести к какой-нибудь другой задаче, основанной на четности-нечетности.Нонсенс. СЛАУ по модулю 2 и есть задача на четность нечетность.

Предложите Ваше решение. Кстати, Гаус и СЛАУ имеет сложность O(N), где N - число уравнений, если обработку уравнения считать как одну операцию.
В сущности при решении Гаусом вы только и делаете, что XOR-ите тождества друг с другом, пока не получаете диагональное тождество + свободные члены тождества.
+ нулевые уравнения (линейно зависимые тождества можно будет быстро выкидывать) и так пока не получите несовместное тождество (нули у переменных, а единица в результате).

[Elementar]

Нонсенс. СЛАУ по модулю 2 и есть задача на четность нечетность.

Предложите Ваше решение. Кстати, Гаус и СЛАУ имеет сложность O(N), где N - число уравнений, если обработку уравнения считать как одну операцию.
В сущности при решении Гаусом вы только и делаете, что XOR-ите тождества друг с другом, пока не получаете диагональное тождество + свободные члены тождества.
+ нулевые уравнения (линейно зависимые тождества можно будет быстро выкидывать) и так пока не получите несовместное тождество (нули у переменных, а единица в результате).

Насколько я понял, Вы хотите преобразовать выражение [l, r] - odd/even в уравнение xl XOR ... XOR xr = 1/0. Да и на обработку одного уравнения уйдет O(maxN) операций, верно? Тогда, используя алгоритм Гаусса решения СЛАУ, в худшем случае сделаем O(N*N*maxN) XOR операций. Даже если будем делать в 64-битных числах, получаем 64*64-кратное ускорение, но степень-то не понижаем.

Мое решение основано на построении графа и нахождении цикла нечетной длины. Работает за O(N^2), где N - количество уравнений.

[Nadir Zaitov]

Мое решение основано на построении графа и нахождении цикла нечетной длины. Работает за O(N^2), где N - количество уравнений.Ок, давайте посмотрим.

[Elementar]

Мое решение основано на построении графа и нахождении цикла нечетной длины. Работает за O(N^2), где N - количество уравнений.Ок, давайте посмотрим.

В общем, идея такова. Для начала заметим, что мы можем ввести граф, где вершинами будут точки. Каждый отрезок [l, r] переведем в неориентированное ребро (l, r+1). Теперь каждый раз будем добавлять ребро либо с 0, либо с 1 (в зависимости от четности) и проверять наличие цикла нечетной длины в нем (можно делать это по модулю 2). Делается это за O(M), где M - количество ребер. Таким образом, решение будет работать за O(N^2). Ну и понятно, если где-то соврал, то там будет цикл нечетной длины (в одном месте отрезок будет содержать четное, в другом нечетное количество единиц).

[Nadir Zaitov]

проверять наличие цикла нечетной длиныОк. Допустим циклов нет (или есть) что это нам дает?

[Elementar]

Ок. Допустим циклов нет (или есть) что это нам дает?

Не каких-то циклов, а циклов именно нечетного веса. Если нет циклов, значит, последовательность существует, если он есть, ее не может быть: получаем противоречие - мы можем добраться за четное и за нечетное количество шагов до какой-то вершины.

[Nadir Zaitov]

Не каких-то циклов, а циклов именно нечетного веса. Если нет циклов, значит, последовательность существует, если он есть, ее не может быть: получаем противоречие - мы можем добраться за четное и за нечетное количество шагов до какой-то вершины.Ок. А где доказательство, что любая противоречивая комбинация таких тождеств приводит нас к кольцу?

[Elementar]

Ок. А где доказательство, что любая противоречивая комбинация таких тождеств приводит нас к кольцу?

Окей, сейчас поясню. Заметим, что соврал - это означает, что на каком-то отрезке [l, r] он сначала сказал, что стоит четное количество единиц, а потом сказал, что стоит нечетное. То есть, мы можем добраться из l до r+1 сначала за четное количество единиц, а потом за нечетное. Получаем эквивалентную задачу :)

[Nadir Zaitov]

Заметим, что соврал - это означает, что на каком-то отрезке [l, r] он сначала сказал, что стоит четное количество единиц, а потом сказал, что стоит нечетное.Вот именно это не так просто.
Например, набор может стать противоречивым в результате сбора нескольких цепей.
Может попробовать нарисовать? Звенья могут накладываться не полностью, а с пересечением.

[Elementar]

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

Сказал - я имею ввиду не именно назвал отрезок [l, r], а мог например назвать [a, b], [a, l-1] и [r+1, b] четными, а сам отрезок [l, r] нечетным. Пересечения автоматически учитываются.

[DarkUser]

Например, набор может стать противоречивым в результате сбора нескольких цепей.
Я это так понимаю:

//Добавить четность N отрезка [l, r]
AddEdge(l, r, N)
//Для все ребер, исходящих их l ([l, x])
1 for x: M[l, x] = NIL
//Добавляем ребро, являющееся сборкой нового добавляемого ([l, r]) и найденного ([l, x])
2 do M[min(x, r), max(x, r)] = (M[l, r] + M[l, x]) mod 2
//Для всех ребер входящих в r ([x, r])
3 for x: M[x, r] = NIL
4 do M[min(l, x), max(l, x)] = (M[l, r] + M[x, r]) mod 2
5 M[l, r] = N

Перед добавлением, проверять наличие значения ребра M[l, r]. Если не пустое и не равно новому, значит коллизия найдена.

[Nadir Zaitov]

Сказал - я имею ввиду не именно назвал отрезок [l, r], а мог например назвать [a, b], [a, l-1] и [r+1, b] четными, а сам отрезок [l, r] нечетным. Пересечения автоматически учитываются.Так я могу же противоречие могу нахлёстами накидать? Нахлёст - это когда:
[1..5]
[2..8]

Где доказательство, что для несовместимого условия существует обязательно замкнутая цепь нечетного веса?
Я это так понимаю:
Ничерта не понимаю (с)

[DarkUser]

Ничерта не понимаю (с)Просчитываем, на основе добавляемого отрезка, с какими он образует пары. Т.е. имеем, в результате, не только заданные отрезки, но и все их комбинации. С коими и сравниваем каждый новый отрезок, перед добавлением в граф.

[Nadir Zaitov]

DarkUser, тут главное вот это:
Где доказательство, что для несовместимого условия существует обязательно замкнутая цепь нечетного веса?
А алгоритм собрать то можно.

[Elementar]

Так я могу же противоречие могу нахлёстами накидать? Нахлёст - это когда:
[1..5]
[2..8]

Где доказательство, что для несовместимого условия существует обязательно замкнутая цепь нечетного веса?

Давайте сначала поймем, что такое "несовместимое условие". Это условие, при добавлении которого возникает 2 варианта для какого-то отрезка [l, r] - четный и нечетный. Нам нужно это обнаружить.

Теперь вспомним, когда мы проводили ребро из l в r+1: если утверждалось о четности или нечетности отрезка [l, r]. То есть, если мы склеим отрезки [a, b] веса ab и веса bc, то мы получим отрезок [a, c] и соответственно путь из a в c (a->b+1, b+1->c) веса ab XOR bc. Теперь пусть мы хотим вычеркнуть из [a, b] веса ab отрезок [c, b] веса cb (c>=a). Опять же, это тоже самое, что путь из c в а (c+1->b+1, b+1->a) веса ab XOR cb - главное не забыть про неориентированность ребер. Таким образом, мы получили 2 важные и достаточные операции - четность известного отрезка можно получить этими 2мя операциями. Теперь, если есть "несовместимое условие", значит, есть 2 пути из какого-то l в какой-то r+1 - четного и нечетного веса, которые в общем образуют цикл нечетной длины. [B]Q.E.D.

P.S. Вообще интересно получилось, сам предложил задачу, сам решил и еще сам объясняю правильность решения =) Куда мир-то катится =)

[Nadir Zaitov]

P.S. Вообще интересно получилось, сам предложил задачу, сам решил и еще сам объясняю правильность решения =) Куда мир-то катится =)
Elementar, еще раз.
То, что если есть нечетное кольцо, то условие не совместно - это ясно и без объяснений. Задача в обратном: доказать, что если условия не совместны, то существует кольцо.
Математика для начинающих, куда катится мир :)

[Elementar]

То, что если есть нечетное кольцо, то условие не совместно - это ясно и без объяснений. Задача в обратном: доказать, что если условия не совместны, то существует кольцо.


Давайте сначала поймем, что такое "несовместимое условие". Это условие, при добавлении которого возникает 2 варианта для какого-то отрезка [l, r] - четный и нечетный. Нам нужно это обнаружить.

Теперь вспомним, когда мы проводили ребро из l в r+1: если утверждалось о четности или нечетности отрезка [l, r].
Для уточнения можно добавить "ребро четного или нечетного веса".

Теперь, если есть "несовместимое условие", значит, есть 2 пути из какого-то l в какой-то r+1 - четного и нечетного веса, которые в общем образуют цикл нечетной длины. Q.E.D.

Именно это и доказывалось.

[Nadir Zaitov]

Это условие, при добавлении которого возникает 2 варианта для какого-то отрезка [l, r] - четный и нечетный.Это уже ужатое требование, которое нужно доказать. На самом деле это условие, при котором не существует набора чисел, ему удовлетворяющих.

[Elementar]

Это условие, при добавлении которого возникает 2 варианта для какого-то отрезка [l, r] - четный и нечетный.Это уже ужатое требование, которое нужно доказать. На самом деле это условие, при котором не существует набора чисел, ему удовлетворяющих.

Ах вот в чем было дело :) Я думал это очевидно :)

Доказательство. Отлично, вернемся к нашей СЛАУ по модулю 2 Ax=b. Используем теорему Кронекера-Капелли (http://ru.wikipedia.org/wiki/Теорема_Кронекера_—_Капелли), получаем, что не будет существовать набора, если ранг матрицы A не совпадает с рангом расширенной A|b. Значит, в какой-то момент можно получить уравнений 0=1 (мы все-таки по модулю 2 работаем). А к этому уравнению, очевидно пришли после сложения двух уравнений xi1 XOR ... XOR xin = 0 и xi1 XOR ... XOR xin = 1. Значит, для какого-то отрезка было 2 варианта четности. Q.E.D.

[Nadir Zaitov]

Значит, для какого-то отрезка было 2 варианта четности.DS уверены, что уже доказали?
А к этому уравнению, очевидно пришли после сложения двух уравнений xi1 XOR ... XOR xin = 0 и xi1 XOR ... XOR xin = 1. Значит, для какого-то отрезка было 2 варианта четности. Q.E.D.Как из того, что было синим Вы пришли к тому, что было красным?
(Ц.У. эти 2 уравнения с СЛАУ появляются после ряда нетривиальных операций, не факт, что простым сцеплением уравнений).

[Elementar]

Значит, для какого-то отрезка было 2 варианта четности.DS уверены, что уже доказали?
А к этому уравнению, очевидно пришли после сложения двух уравнений xi1 XOR ... XOR xin = 0 и xi1 XOR ... XOR xin = 1. Значит, для какого-то отрезка было 2 варианта четности. Q.E.D.Как из того, что было синим Вы пришли к тому, что было красным?
(Ц.У. эти 2 уравнения с СЛАУ появляются после ряда нетривиальных операций, не факт, что простым сцеплением уравнений).

Конечно, доказали. Мы получили 0=1. У нас есть хотя бы одно уравнение x(i) XOR x(i+1) XOR ... XOR x(i+j) = 0|1 (Предположим, мы решали методом Гаусса). ПроXORим его с уравнением 0=1. Получим уравнение x(i) XOR x(i+1) XOR ... XOR x(i+j) = 1|0. Получили 2 варианта для этого отрезка.

[Nadir Zaitov]

У нас есть хотя бы одно уравнение x(i) XOR x(i+1) XOR ... XOR x(i+j) = 0|1Это не факт. Мало того, не факт что есть группа уравнений, начала и конец которых дают кольцо. Я не пытаюсь доказать обратное, вполне вероятно, что в этом есть смысл.
Но это нужно доказывать.

[Nadir Zaitov]

Короче решил я как математик подойти к проблеме графов и кольцевых маршрутов.
Возьмем такую последовательность:

от 1 до 7 сумма чисел четно/нечетно - пока без разницы
от 2 до 8 сумма чисел *
от 3 до 9 сумма чисел *
от 4 до 10 сумма чисел *
от 5 до 11 сумма чисел *
от 6 до 12 сумма чисел *
от 7 до 13 сумма чисел *
от 1 до 11 сумма чисел *
от 2 до 12 сумма чисел *
от 3 до 13 сумма чисел *
от 4 до 13 сумма чисел *
от 5 до 13 сумма чисел *
от 6 до 10 сумма чисел *

* - везде свыше также означает, четное/нечетное - пока без разницы.

Указанные 13 уравнений совместные, что видно из следующей картинки:

https://img.uforum.uz/images/bjxxlfh7973603.png

Те, в частности переменные №7, №8, №9 могут принимать (за счет выбора правой части равенства) любые наперед заданные значения. В частности, нечетные числа.
Причем указанные числа могут быть только концами графов, т.е. не входят в кольца.

Стало быть, добавим к указанным условиям например такое:

от 8 до 8 сумма чисел четна

и получим, что, указанное условие не создает кольцо (кроме самого себя, но оно по определению четно), и не дополняет никакое другое условие до кольца.

Стало быть мы знаем, что система несовместная, и знаем, что в ней нет колец с нечетным весом: в первых 13 уравнениях их нет, так как они совместные, а добавление 14-го уравнения не создает колец.

Вот вами потребность математики в программировании.

[Elementar]

Короче решил я как математик подойти к проблеме графов и кольцевых маршрутов.

Тут другого подхода и нет :)


Возьмем такую последовательность:
...
* - везде свыше также означает, четное/нечетное - пока без разницы.
Указанные 13 уравнений совместные, что видно из следующей картинки:


Последовательность не совпадала с тем, что было на картинке - поэтому я опирался только на картинку. Да и разница как раз есть, например, если взять все 13 четные или все 13 нечетные, получим разные результаты (смотрите ниже).


Те, в частности переменные №7, №8, №9 могут принимать (за счет выбора правой части равенства) любые наперед заданные значения. В частности, нечетные числа.
Причем указанные числа могут быть только концами графов, т.е. не входят в кольца.


Если не добавлять 14ое уравнение, все верно - иначе №7 будет участвовать в цикле (смотрите ниже).


Стало быть, добавим к указанным условиям например такое:

от 7 до 7 сумма чисел четна

и получим, что, указанное условие не создает кольцо (кроме самого себя, но оно по определению четно), и не дополняет никакое другое условие до кольца.


Ну это уже неверно. На языке матриц Ax=b у нас появится строчка 0=b7 XOR b8 XOR b12 XOR b14, если проXORим 14ое уравнение с уравнениями 7, 8, 12. Мы получаем наш цикл. И будет он четный или нечетный, скажет как раз выражение b7 XOR b8 XOR b12 XOR b14: если оно равно 0, все ОК, этот цикл четного веса и система совместна (ранг расширенной матрицы равен рангу начальной матрицы), если оно нечетно, то получили цикл нечетного веса и система несовместна (ранг расширенной матрицы на 1 больше ранга начальной матрицы), а, значит, и последовательности не существует.

А вот и цикл кстати - 1 8 7 14 5 12 1. Это отрезки (в скобках номера) [1, 7](1), [7, 7](14), [7, 13](7), [5, 13](12), [5, 11](5), [1, 11](8).


Стало быть мы знаем, что система несовместная, и знаем, что в ней нет колец с нечетным весом: в первых 13 уравнениях их нет, так как они совместные, а добавление 14-го уравнения не создает колец.


Это утверждение автоматически становится неверным.


Вот вами потребность математики в программировании.Без нее совсем никак.

Это не факт. Мало того, не факт что есть группа уравнений, начала и конец которых дают кольцо. Я не пытаюсь доказать обратное, вполне вероятно, что в этом есть смысл.
Но это нужно доказывать.

Получается, осталось доказать концовку. Пусть мы получили уравнение 0=1 при помощи XORа уравнением i. Тогда проXORим с уравнением i наше уравнение и получим, что в уравнении i (отрезке i) 2 варианта. Фактически это будет означать, что есть цикл, содержащий ребро с номером i.

Все-таки попытались доказать обратное :D

[Nadir Zaitov]

Последовательность не совпадала с тем, что было на картинке - поэтому я опирался только на картинку. Да. Тут я запорол - признаюсь. Запутался в описании - исправлю сейчас. Исправил. Обратите внимание, что 7 поменялось на 8.
Ну это уже неверно. На языке матриц Ax=b у нас появится строчка 0=b7 XOR b8 XOR b12 XOR b14, если проXORим 14ое уравнение с уравнениями 7, 8, 12. Мы получаем наш цикл.

Покажите мне соответствующий граф. Что-то я не догнал. Переменные 8 и 9 не являются одновременно вершинами двух ребер, чтоб их склеивать. С помощью XOR операций доказывать несовместность Вам не нужно - я сам знаю. Вы кольцевой граф покажите.

Получается, осталось доказать концовку. Пусть мы получили уравнение 0=1 при помощи XORа уравнением i. Тогда проXORим с уравнением i наше уравнение и получим, что в уравнении i (отрезке i) 2 варианта. Фактически это будет означать, что есть цикл, содержащий ребро с номером i.
не пытайтесь доказать иной факт. Вы докажите, что для несовместных уравнений в начальном наборе уравнений есть цикл с нечетным весом. То, что к циклу такому можно привести - и так понятно, не факт что он изначально существует.

[Elementar]

Покажите мне соответствующий граф. Что-то я не догнал. Переменные 8 и 9 не являются одновременно вершинами двух ребер, чтоб их склеивать. С помощью XOR операций доказывать несовместность Вам не нужно - я сам знаю. Вы кольцевой граф покажите.

Что ж пришлось рисовать ручками.

https://img.uforum.uz/images/qmgcdzb9545991.png

Последовательные ребра я специально помечал одним цветом, чтобы было проще. Главное, помните, как я ставил ребра, и, наверное, не надо говорить, что в этом графе я оставил только цикл (кстати, он нечетной длины, но не обязательно нечетного веса).

С помощью XOR операций доказывать несовместность Вам не нужно - я сам знаю.

не пытайтесь доказать иной факт. Вы докажите, что для несовместных уравнений в начальном наборе уравнений есть цикл с нечетным весом. То, что к циклу такому можно привести - и так понятно, не факт что он изначально существует.

Ну если к циклу можно привести понятно - нужно понять, что делает XOR операция. Для этого посмотрим давнее сообщение, которое и содержит доказательство - что получается цикл из изначальных уравнений.

То есть, если мы склеим отрезки [a, b] веса ab и [b+1, c] веса bc, то мы получим отрезок [a, c] и соответственно путь из a в c (a->b+1, b+1->c) веса ab XOR bc. Теперь пусть мы хотим вычеркнуть из [a, b] веса ab отрезок [c, b] веса cb (c>=a). Опять же, это тоже самое, что путь из c в а (c+1->b+1, b+1->a) веса ab XOR cb - главное не забыть про неориентированность ребер. Таким образом, мы получили 2 важные и достаточные операции - четность известного отрезка можно получить этими 2мя операциями. Теперь, если есть "несовместимое условие", значит, есть 2 пути из какого-то l в какой-то r+1 - четного и нечетного веса, которые в общем образуют цикл нечетной длины.

Осталось заметить, что когда мы XORим 2 уравнения вида xi+...+x(i+j) = 0 и xi+...+x(i+j) = 1, мы получается 2 пути разного веса склеиваем. При приведении к треугольному виду методом Гаусса, мы получим 0=1. Одновременно наш цикл нечетной длины. А XORить как-то по другому мы не будем (вспомните как работает Гаусс).

[Nadir Zaitov]

Elementar, Вы издеваетесь?
Где ребро 1-8, 8-9

[Elementar]

Elementar, Вы издеваетесь?
Где ребро 1-8, 8-9


Главное, помните, как я ставил ребра, и, наверное, не надо говорить, что в этом графе я оставил только цикл (кстати, он нечетной длины, но не обязательно нечетного веса).

Для начала заметим, что мы можем ввести граф, где вершинами будут точки. Каждый отрезок [l, r] переведем в неориентированное ребро (l, r+1).

Я не издеваюсь, это Вы невнимательно читали мои сообщения, возможно поэтому у нас и было недопонимание :)

[Nadir Zaitov]

Я не издеваюсь, это Вы невнимательно читали мои сообщения, возможно поэтому у нас и было недопониманиеХорошо, а каков вес тогда 1-8 и 8-9

[Elementar]

Я не издеваюсь, это Вы невнимательно читали мои сообщения, возможно поэтому у нас и было недопониманиеХорошо, а каков вес тогда 1-8 и 8-9

Я показал цикл нечетной длины. В зависимости от расстановки весов (а именно, количества 1 на нем) он будет нечетного или четного веса.

[Nadir Zaitov]

Например, из условия 1-7 сумма четно - ясно, что вес ребра = 0.
Далее вопросы: Как определить вес ребер 1-8, 8-9?
Где тут O(N×N) операций, если мне нужно продумывать разбиение отрезков на подграфы?

[Elementar]

Например, из условия 1-7 сумма четно - ясно, что вес ребра = 0.
Далее вопросы: Как определить вес ребер 1-8, 8-9?
Где тут O(N×N) операций, если мне нужно продумывать разбиение отрезков на подграфы?

Вес ребра 1-8 - это четность отрезка [1, 7], вес ребра 8-9 - соответственно, четность отрезка [8, 8]. А чтобы определить ацикличен ли граф, достаточно O(m) операций, где m - количество ребер. N проверок ацикличности графов с <= N ребер дают сложность O(N*N).

[Nadir Zaitov]

Вес ребра 1-8 - это четность отрезка [1, 7], вес ребра 8-9 - соответственно, четность отрезка [8, 8]. А чтобы определить ацикличен ли граф, достаточно O(m) операций, где m - количество ребер. N проверок ацикличности графов с <= N ребер дают сложность O(N*N).

Elementar, тогда просьба для тупых, для меня конкретно, объясните как работает Ваш алгоритм.

[Elementar]

Алгоритм решения задачи.

Для каждого отрезка [ai, bi] с четностью ci будем добавлять неориентированное ребро (ai, bi+1) веса ci.

Теперь последовательно будем добавлять отрезки [a1, b1], ..., [aN, bN] в виде ребер и после каждого добавления проверять, будет ли наш граф содержать цикл нечетного веса. Если есть цикл нечетного веса - условие несовместно, дальше продолжать не надо.

Почему это работает.

Сведем к системе
a1 XOR ... XOR b1 = c1
...
aN XOR ... XOR bN = cN

Если получаем, что ранг матрицы меньше ранга расширенной => можем получить уравнение 0=1.

Теперь сведем систему к графу. Если мы XOR'им уравнения с одинаковой левой границей
a XOR ... XOR b1 = c1
a XOR ... XOR b2 = c2
мы получаем уравнение тоже из последовательных членов.

На языке графов - это склеивание двух путей.

Теперь зачем я делал ребро bi+1. Потому что нужно было склеивать отрезки [a1, b1] [b1+1, c1] и в то же время склеивать отрезки [a1, b1] [a1, c1].

В общем описание довольно поверхностное, учитывая дискуссию в 2-3 страницы, поэтому отдельные моменты могу объяснить подробней.

[Nadir Zaitov]

Для каждого отрезка [ai, bi] с четностью ci будем добавлять неориентированное ребро (ai, bi+1) веса ci.

Теперь последовательно будем добавлять отрезки [a1, b1], ..., [aN, bN] в виде ребер и после каждого добавления проверять, будет ли наш граф содержать цикл нечетного веса. Если есть цикл нечетного веса - условие несовместно, дальше продолжать не надо.
Покажите как это работает. Вот наверное самый простой набор несовместных уравнений (переменные 2, я их не нумерую, а назsваю просто а и b):
a xor b = 1;
a=0;
b=0;

[Elementar]

Покажите как это работает. Вот наверное самый простой набор несовместных уравнений (переменные 2, я их не нумерую, а назsваю просто а и b):
a xor b = 1;
a=0;
b=0;

Если у нас есть a XOR b, следовательно, b = a+1 (если эта система не имеет отношения к нашей задаче, там не обязательно будет цикл, потому что мы используем ее свойство - всегда уравнения вида a XOR ... XOR (a+n) = b).

Теперь получаем такую систему
a XOR (a+1) = 1
a = 0
a +1 = 0

Получаем граф с неориентированными ребрами (a, a+2), (a, a+1), (a+1, a+2) с весами 1, 0, 0. Получаем цикл (a, a+2) -> (a+2, a+1) -> (a+1, a) веса 1.

[Nadir Zaitov]

Теперь получаем такую системуНе уходите в бок.
Давайте решим с помощью предложенного вами алгоритма исходную задачу. Ntv более, что граф полученный Вами к новой задаче как-то не совсем соответствует тому, как вы описали решение задачи.

[Elementar]

Не уходите в бок.
Давайте решим с помощью предложенного вами алгоритма исходную задачу. Ntv более, что граф полученный Вами к новой задаче как-то не совсем соответствует тому, как вы описали решение задачи.

Я не ухожу в бок, это Вы даете совершенно другую задачу для алгоритма :) Тоже самое, если я буду знать как искать квадратный корень по модулю (перебором элементов кольца) и применю это для вещественных чисел. Я утверждал, что этот алгоритм будет работать для данной задачи, а не для произвольной системы (в которой даны уже не отрезки, а отдельные точки). А граф как раз соответствует той системе, которую я Вам дал. Придумайте пример в нашей постановке, я Вам еще раз построю граф.

[Nadir Zaitov]

Вы даете совершенно другую задачу для алгоритма Как это так?
2 переменные, 3 условия "сумма от до четна/нечетна".

[Elementar]

Как это так?
2 переменные, 3 условия "сумма от до четна/нечетна".

Правильно ли я понимаю, что есть 3 отрезка: [a, b] c четностью 1, [a, a] с четностью 0 и [b, b] с четностью 0 (для определенности будем считать, что a<=b).

Тогда система будет иметь следующий вид:

a XOR (a+1) XOR ... XOR b = 1
a = 0
b = 0

А граф получается такой: отрезок [a, b] перейдет в ребро (a, b+1) веса 1, отрезок [a, a] перейдет в ребро (a, a+1) веса 0 и отрезок [b, b] перейдет в ребро (b, b+1) веса 1.

Теперь как будет работать алгоритм на графе. Изначально у нас есть только ребро (a, b+1) веса 1. Цикл нечетного веса не нашли. На следующей итерации добавляем ребро (a, a+1) веса 0. Цикл нечетного веса будет, если b=a, иначе двигаемся дальше - добавляем ребро (b, b+1) веса 0 и цикл нечетного веса будет, если b=a+1.

Мы же склеиваем отрезки, либо отрезаем от них часть - и так вроде понятно, что это будет работать.

[Nadir Zaitov]

Напишите и выложите лучше свою программу.
Ничерта не понял

[Elementar]

Напишите и выложите лучше свою программу.
Ничерта не понял

Если Вы не поняли алгоритм, чем поможет программа?

Предлагаю выбрать какой-то пример снова, я нарисую картинку.

[JH]

Задача. В большом турнире по покеру игроков рассаживают за столы, по 9 человек за стол, всем выдают поровну игровых фишек. Проигравший все свои фишки игрок вылетает из турнира. Если общее количество игроков не кратно девяти, то организаторы турнира рассаживают их как можно более равномерно, и могут пересаживать после каждой раздачи. (Например, оставалось 15 игроков, на двух столах, по 7 и 8 игроков соответственно, и вылетел один игрок за тем столом, где было 7, за этот стол пересаживают одного человека со второго. Из игры все время убираются лишние столы, чтобы по возможности везде сидело по 9 человек)

Вопрос. Если считать, что вылеты из турнира происходят в целом равномерно, то сколько человек должно вылететь "на твоих глазах", т.е. за тем же столом, где ты сидишь, пока ты окажешься за "финальным" столом? В зависимости от стартового количества игроков, которое равно, скажем, N

[Nadir Zaitov]

Предлагаю выбрать какой-то пример снова, я нарисую картинку.[1 2] нечетно
[1 1] четно
[2 2] четно

[Elementar]

[1 2] нечетно
[1 1] четно
[2 2] четно

https://img.uforum.uz/images/xzmmmwb9468053.png

Красным обозначено ребро (1, 3) (отрезок [1, 3]) веса 1.
Синим обозначено ребро (1, 2) (отрезок [1, 2]) веса 0.
Зеленым обозначено ребро (2, 3) (отрезок [2, 2]) веса 0.

1 итерация.
Добавляем ребро (1, 3). Цикла нечетного веса нет.

2 итерация.
Добавляем ребро (1, 2). Цикла нечетного веса нет.

3 итерация.
Добавляем ребро (2, 3). Появился цикл нечетного веса.

[Elementar]

Задача. В большом турнире по покеру игроков рассаживают за столы, по 9 человек за стол, всем выдают поровну игровых фишек. Проигравший все свои фишки игрок вылетает из турнира. Если общее количество игроков не кратно девяти, то организаторы турнира рассаживают их как можно более равномерно, и могут пересаживать после каждой раздачи. (Например, оставалось 15 игроков, на двух столах, по 7 и 8 игроков соответственно, и вылетел один игрок за тем столом, где было 7, за этот стол пересаживают одного человека со второго. Из игры все время убираются лишние столы, чтобы по возможности везде сидело по 9 человек)

Вопрос. Если считать, что вылеты из турнира происходят в целом равномерно, то сколько человек должно вылететь "на твоих глазах", т.е. за тем же столом, где ты сидишь, пока ты окажешься за "финальным" столом? В зависимости от стартового количества игроков, которое равно, скажем, N

1. Предполагается, что мы доходим до финального стола или тоже можем вылететь?

2. Считается ли пересаживание вылетом?

[JH]

1. Предполагается, что мы доходим до финального стола или тоже можем вылететь?

2. Считается ли пересаживание вылетом?
1. Да.
2. Нет.

[Nadir Zaitov]

1. Предполагается, что мы доходим до финального стола или тоже можем вылететь?
1. Да.
JH, класс. Стильно ответили :).
Учитывая, что вопрос перечислил все возможные события, то это даже круто.

[Nadir Zaitov]

Красным обозначено ребро (1, 3) (отрезок [1, 3]) веса 1.
Синим обозначено ребро (1, 2) (отрезок [1, 2]) веса 0.
Зеленым обозначено ребро (2, 3) (отрезок [2, 2]) веса 0.

1 итерация.
Добавляем ребро (1, 3). Цикла нечетного веса нет.

2 итерация.
Добавляем ребро (1, 2). Цикла нечетного веса нет.

3 итерация.
Добавляем ребро (2, 3). Появился цикл нечетного веса.Никаких склеек с помощью XOR не понадобилось. Так?

[Elementar]

Никаких склеек с помощью XOR не понадобилось. Так?

Конечно. Они только в доказательстве и появились. Тут правда мы можем не складывать веса, а XORить (ведь нам важна только четность).

[Nadir Zaitov]

Конечно. Они только в доказательстве и появились.Стало прояснятся то, что вы раньше написали. Нужно изучить.

[JH]

1. Предполагается, что мы доходим до финального стола или тоже можем вылететь?
1. Да.
JH, класс. Стильно ответили :).
Учитывая, что вопрос перечислил все возможные события, то это даже круто.

Хе, я хотел сказать "да, доходим"... Ну и, конечно же, можем вылететь тоже. Так что ответ в каком-то смысле был правильный. Вопрос как раз и заключался в том, что сколько человек должны вылететь на наших глазах (при том, что сами не вылетаем, надо стараться), чтобы попасть за финальный стол.

И еще. В число "вылетов на моих глазах" входят как случаи, когда я выбиваю игрока, так и случаи, когда другой игрок за "моим" столом выбивает другого игрока.

[Elementar]

Вопрос. Если считать, что вылеты из турнира происходят в целом равномерно, то сколько человек должно вылететь "на твоих глазах", т.е. за тем же столом, где ты сидишь, пока ты окажешься за "финальным" столом? В зависимости от стартового количества игроков, которое равно, скажем, N

Верхняя оценка max(0, N-9), нижняя оценка 0 (если не учитывать блайнды). То есть либо есть какой-то стол, где все жестко вылетают, либо мы сидим за этим злосчастным столом.

Или имелось ввиду матожидание?

[JH]

Верхняя оценка max(0, N-9), нижняя оценка 0 (если не учитывать блайнды). То есть либо есть какой-то стол, где все жестко вылетают, либо мы сидим за этим злосчастным столом.

Или имелось ввиду матожидание?
Имелось в виду среднее ожидание, и сразу в условии заложено, что вылеты идут равномерно на всех столах.

[Kane]

Наше тестовое задание для интернов:
Дано: N песочных часов и T - время которое требуется отмерить.
Алгоритм должен высчитывать оптимальный путь решения (наименьшее количество перевертываний), для любых N и T (либо выдать что решения нет).

[Nadir Zaitov]

Kane, часы одинаковые? В смысле, одинаковое время мерят?).

[Kane]

Kane, часы одинаковые? В смысле, одинаковое время мерят?).

Ну например даны часы - 7 и 4 минуты, нужно отмерить 9. Или даны 7 и 11, нужно отмерить 15.

Пример решения для 7 и 4:
Перевернуть двое разом, отмерить 7 минут, продолжать переворачивать 4 минутную в течение 7 минут.
После 7 минут в 4 минутной останется 1 минута, 7 минутная пуста.
Опять перевернуть оба, отмерить минуту.
4 минутная пуста, в 7 минутной - 1.
Отмерить оставшуюся минуту - всего 9.

Задача - составить алгоритм для любого количества часов и произвольного времени.

[Nadir Zaitov]

Задача - составить алгоритм для любого количества часов и произвольного времени.Кроме полного перебора нахождения "оптимального решения", существует решение в разумный срок?

[Kane]

Кроме полного перебора нахождения "оптимального решения", существует решение в разумный срок?

Перебор принимается, весь интерес в оптимизации перебора по скорости и памяти.

[Nadir Zaitov]

Kane, еще раз.
Можно требуемое время собирать по частям или нужен непрерывный кусок времени?
В Вашем решении получилоас (как мне сначала показалось) сборка нужного участка времени "по частям".

Решение для непрерывного времени решалась бы так:

1) 7-ми минутными часами отмеряем 14 минут переворачивая 2 раза.
После четырнадцати минут 7-минутные некоторое время бездействуют.

2) (Одновременно с процессом пункта №1) 4-х минутными часами отмеряем 16 минут переворачивая 4 раза.

3) (После завершения процесса №2) 7-ми минутными часами отмеряем 7 минут

Отсчет искомого времени нужно начинать после завершения процесса №1 (в 4-х минутных часах будет ровно 2 минуты).

Отсчет искомого времени нужно завершить после завершения процесса №3 (еще через 7 минут - итого 9 минут).

[Kane]

Можно требуемое время собирать по частям или нужен непрерывный кусок времени?
Ваше решение тоже подходит. Можно отнестись к этому так - у повара есть часы только 4 и 7 минут. Блюдо готовится ровно 9. Любые методы которыми он может отмерить ровно 9 минут чтоб приготовить блюдо - валидны.
Просто в моем способе меньше переворачиваний, а это одно из условий задачи.

P.S. А основная трудность написания алгоритма в том что он должен работать для любого количества часов и требуемого времени, учитывая оптимизации по скорости и памяти.

[Elementar]

Дано: N песочных часов и T - время которое требуется отмерить.
Алгоритм должен высчитывать оптимальный путь решения (наименьшее количество перевертываний), для любых N и T (либо выдать что решения нет).

В голову пришло только сложное решение.

Закодируем состояния часов при помощи набора из N чисел (a1, a2, ... , aN). Пусть вместимость i-х часов bi. Добавим еще один параметр t - текущий момент времени, будет отсчитываться от 0. Понятно, что время будет дискретное. Тогда dp[t][a1]...[aN] - минимальное время, за которое мы можем попасть в состояние (a1, a2, ..., aN) в момент времени t. Понятно, что в это состояние мы можем попасть из момента t-1 путем переворачиваний каких-то часов из доступных состояний. Тогда dp[t][a1]...[aN] = min(dp[t-1][c1]...[cN]+s), где ci либо ai-1, либо bi-ai-1, а s количество ci=bi-ai-1. На моменте 0 доступно только состояние (0, 0, ..., 0). Итоговая сложность решения O(T*a1*...*aN*2^N), затраты по памяти O(a1*...*aN) - храним только 2 строки.

Возможно можно пооптимизировать, если переворачивать только одни часы, но не уверен, что это будет правильно работать. И вообще есть ощущение, что есть более простое решение, основанное на остатках.

[Kane]

В голову пришло только сложное решение.
Тут есть еще одна тонкость, что в каждый момент времени у часов могут быть 2 состояния (то есть на примере 7 и 4 - по истечении 4, 7 имеет 2 состояния - 4 и 3).

[Elementar]

Тут есть еще одна тонкость, что в каждый момент времени у часов могут быть 2 состояния (то есть на примере 7 и 4 - по истечении 4, 7 имеет 2 состояния - 4 и 3).

Хотел бы уточнить.

Если эту тонкость нужно только рассмотреть в алгоритме - то да, она учтена (для этого работает S). А если на основе этой тонкости можно придумать более эффективное решение без перебора, то я еще подумаю.

Пока только получилось снизить сложность следующим образом. Правда теперь памяти потребуется (T*a1*...*aN). Идея такова - от состояния (t, a1, ..., aN) каждый раз достаточно считать до следующего переворачивания (в другие моменты мы переворачивать не можем) - перебираем все непустые подмножества "переворачиваемых" часов. Используем своебразный обход в ширину. По-моему, теперь переборное решение быстрее не придумать. Получаем ускорение по производительности - просматриваем только достижимые состояния. Для двух часов можно придумать что-то интересное, но для N часов не представляю как.

[Kane]

Используем своебразный обход в ширину.
Пока да, у нас почти все решения связаны с обходом в ширину.

[Elementar]

Пока да, у нас почти все решения связаны с обходом в ширину.

А что-то быстрее обхода достижимых состояний получилось придумать?

[Kane]

А что-то быстрее обхода достижимых состояний получилось придумать?
Ну, так, лениво смотрим на это дело, но пока с ходу ничего не придумывается кроме дерева состояний. Имеются подозрения что элегантное решение есть.

[Nadir Zaitov]

Имеются подозрения что элегантное решение есть.
Что касается "достижимости", то эту задачу нужно решить на самом первом этапе.
Если, например, принять, что часы у нас целочисленные, то посчитать НОД попарно у всех номиналов часов. Если он равен 1, то можно им отложить любой отрезок времени теоретически. Если они все имеют номинал кратный, например Q, то проверить, если искомое время кратно Q, то решение очевидно есть, если не кратны - то решения нет.

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

[Kane]

Есть идея для начало найти любое решение, а потом думать, как его можно "упростить", двигаясь, скажем, по по симплексу.
В принципе как выше говорил Elemental решение есть, расходящееся дерево комбинаций. С доказуемостью тоже более менее понятно. Теперь надо подумать как бы это сделать поэлегантнее.
Самый наивный алгоритм примерно таков - на каждом шаге вычислять доступные комбинации поочередно выбирая часы, примерно так:
[4,5,7] - выбираем 4
[4, 4, 3] - это надо вычеркнуть так как ниже есть аналог
[4, 1, 3]
[4, 4, 4] - вычеркиваем
[4, 1, 4] - вычеркиваем
На каждом шаге надо проверять сумму (учитывая любой непрерывный отрезок дерева, то есть не обязательно с корня).
Дальше то же самое с 5 и 7 и рекурсивно строим дерево. Вопрос - оптимизация наивного решения?

[Elementar]

Если, например, принять, что часы у нас целочисленные, то посчитать НОД попарно у всех номиналов часов. Если он равен 1, то можно им отложить любой отрезок времени теоретически. Если они все имеют номинал кратный, например Q, то проверить, если искомое время кратно Q, то решение очевидно есть, если не кратны - то решения нет.

Тут я не согласен, не всегда этого достаточно. Например, пусть у нас есть 7 и 9, но мы не можем отложить отрезок длины 10, несмотря на то, что он больше 7 и 9.

Еще нужно не забыть про минимальное количество перевертываний.


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

Но ведь не всегда гарантируется, что мы придем к глобальному минимуму. Мы можем прийти к локальному - а выпуклость функции не гарантируется, тем более она разрывная.


В принципе как выше говорил Elemental решение есть, расходящееся дерево комбинаций. С доказуемостью тоже более менее понятно. Теперь надо подумать как бы это сделать поэлегантнее.

Вопрос - оптимизация наивного решения?

Опять же: не посещать состояния дважды - не добавлять их в очередь, если они там есть. Этого можно добиться, если идти по достижимым состояниями в порядке увеличения t. Других особых оптимизаций не вижу (по времени).

[Nadir Zaitov]

Например, пусть у нас есть 7 и 9Одновременно 5 раз откладываем 7.
Одновременно 5 раз откладываем 9.
Разница между завершение откладываний 7-минутных часов и 9 минутных чему будет равно?

[Elementar]

Одновременно 5 раз откладываем 7.
Одновременно 5 раз откладываем 9.
Разница между завершение откладываний 7-минутных часов и 9 минутных чему будет равно?

Интересно, я не подумал, что можно откладывать не с момента 0 :) Тогда да, можно придумать поинтереснее решение.

[Kane]

Интересно, я не подумал, что можно откладывать не с момента 0 Тогда да, можно придумать поинтереснее решение.
Кстати да, тут можно разложить на подзадачи, время с момента 0 или начиная с любого отрезка. Изначально стоит задача с любого момента.

[Nadir Zaitov]

Но ведь не всегда гарантируется, что мы придем к глобальному минимуму. Мы можем прийти к локальному - а выпуклость функции не гарантируется, тем более она разрывная.Вопрос как поставить задачу, чтоб мы оказались на симплексе или в выпуклом множестве, чтоб решение гарантировало единственность.

[Nadir Zaitov]

К вопросу о задачке с часами:
За пять рублей — сто. Один эстрадный счетчик на
своих сеансах делал публике следующее заманчивое предложение:
—Объявляю при свидетелях, что плачу 100 рублей каждому, кто даст мне 5 руб лейдвадцатью монетами — по 50, 20 и 5 коп. Сто рублей за пять! Кто желает?
Воцарялось молчание.
Публика погружалась в размышление. Карандаши бегали по листкам записных книжек, — но ответного предложения не поступало.
— Публика, я вижу, находит 5 рублей слишком высокой платой за 100 рублей. Извольте, я готов скинуть два рубля и назначаю пониженную цену: 3 рубля двадцатью монетами названного достоинства. Плачу 100 рублей за 3 рубля!
Желающие,составляйте очередь!
Но очередь не выстраивалась. Публика явно медлила воспользоваться редким случаем.
—Неужели и 3 рубля дорого? Хорошо,понижаю сумму еще на рубль; уплатите указанными двадцатью монетами всего только 2 рубля и я немедленно вручу предъявителю сто рублей.
Так как никто не выражал готовности совершить обмен, счетчик продолжал:
—Может быть, у вас нет при себе мелких денег? Не стесняйтесь этим, я поверю в долг. Дайте мне только на бумажке реестрик, сколько монет каждого достоинства
вы обязуетесь доставить!
Доказать тройное утверждение:

ни 5, ни 3, ни 2 рубля нельзя выразить ровно 20-ю монетами по 50, 20 и 5 копеек.

[Nadir Zaitov]

К вопросу о задачке с часами:
За пять рублей — сто. Один эстрадный счетчик на
своих сеансах делал публике следующее заманчивое предложение:
—Объявляю при свидетелях, что плачу 100 рублей каждому, кто даст мне 5 руб лейдвадцатью монетами — по 50, 20 и 5 коп. Сто рублей за пять! Кто желает?
Воцарялось молчание.
Публика погружалась в размышление. Карандаши бегали по листкам записных книжек, — но ответного предложения не поступало.
— Публика, я вижу, находит 5 рублей слишком высокой платой за 100 рублей. Извольте, я готов скинуть два рубля и назначаю пониженную цену: 3 рубля двадцатью монетами названного достоинства. Плачу 100 рублей за 3 рубля!
Желающие,составляйте очередь!
Но очередь не выстраивалась. Публика явно медлила воспользоваться редким случаем.
—Неужели и 3 рубля дорого? Хорошо,понижаю сумму еще на рубль; уплатите указанными двадцатью монетами всего только 2 рубля и я немедленно вручу предъявителю сто рублей.
Так как никто не выражал готовности совершить обмен, счетчик продолжал:
—Может быть, у вас нет при себе мелких денег? Не стесняйтесь этим, я поверю в долг. Дайте мне только на бумажке реестрик, сколько монет каждого достоинства
вы обязуетесь доставить!
Доказать тройное утверждение:

ни 5, ни 3, ни 2 рубля нельзя выразить ровно 20-ю монетами по 50, 20 и 5 копеек.