Codeforces Beta Round #18 (Див. 2)

14 лет назад, # ^ |

Может быть проинициализирована переменная или же тесты не совпадают

→ Ответить

14 лет назад, # ^ |

Тест ровно тот же, что и в условии

→ Ответить

RAD	14 лет назад, # ^ \| 0 Сегодня во всех задачах тесты из условия совпадали с первыми тестами. Может быть, отличаются версии компилятора? → Ответить

14 лет назад, # ^ |

Ты делал копипаст из условия или сам писал ?

→ Ответить

14 лет назад, # |

+12

Будет ли разбор от авторов? Или я могу написать?

→ Ответить

14 лет назад, # ^ |

Будет здорово, напиши!

→ Ответить

jbernadas

14 лет назад, # |

Is it intentional that now the only way to submit is to select a file instead of pasting the code? I made a pair or mistakes because of that, because using the current way forces me to lose the tab with the problem.

Is it possible to restore the submit pasting functionality back?

→ Ответить

14 лет назад, # ^ |

It will appear soon :)

→ Ответить

jbernadas

14 лет назад, # ^ |

Thanks :), I always preferred pasting the code. Also, my status during the match dissapeared, and now it only shows the practice submissions.

→ Ответить

wilbertliu

14 лет назад, # |

Nice problems!
I like them all.. :)

Well, when will the tutorial of this round
announced?

→ Ответить

14 лет назад, # ^ |

Participant ArtDitel told that he will write it. Lets wait!

→ Ответить

wjomlex

14 лет назад, # ^ |

+13

If you want a quick overview...

Problem A - Geometry with *many* possible solutions including Pythagoras's Theorem, checking for perpendicular line segments, using trigonometry to test angles...

Problem B - Simulation, with modular arithmetic to speed things up

Problem C - If you keep track of the sum to the right of a point, and the sum to the left of a point, you can compute the new left-hand and right-hand sums by just subtracting one number from one sum, and adding it to the other. In this way, you can try all possible cuts in O(n)

Problem D - This can be done as a Weighted Interval Scheduling DP, though as a friend pointed out, 2^x > 2^(x-1) + 2^(x-2) + ... + 2^0, so you can just take the largest intervals first, greedily, because they will be worth more than all other intervals that they conflict with.

Problem E - Row by Row DP. Determine all possible chequerings for one row, and get the cost of using that chequering (which can be done in constant time, not O(n)!). Then for the next row, try all possible chequerings and see which ones are compatible with the row above. Take the minimum cost of these. This is ~650x650x500 which is just a *bit* too slow. But if you sort the results of the previous row by cost, you can get an answer closer to 650*500.

→ Ответить

Anurag

14 лет назад, # ^ |

what can be test#31 for problem A-Triangle?

→ Ответить

wilbertliu

14 лет назад, # ^ |

Hmm.., we don't know.. ;)
because testdata are hidden..

→ Ответить

Anurag

14 лет назад, # ^ |

I found that, Actually its related to "checking whether length of sides becomes zero , while changing the points"
example(as suggested by RAD)
0 0 1 0 4 1

Thanks RAD

→ Ответить

Hedayet

14 лет назад, # ^ |

I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?

→ Ответить

Hedayet

14 лет назад, # ^ |

I am also interested about case 31 for problem A. can anyone(admin/problem writer) tell us what can be the case?

→ Ответить

ydnl	14 лет назад, # ^ \| 0 Consider three points in a line like 0 0 0 1 0 3 → Ответить

Connector

14 лет назад, # ^ |

I pass #31 test when add checking the S of triangle

→ Ответить

liuyubobobo

14 лет назад, # ^ |

I'm a rookie about algorithm, i just interested in the Weighted Interval Scheduling DP method, can somebody offer me more information about that? thx a lot! :)

→ Ответить

wjomlex

14 лет назад, # ^ |

This lecture explains the O(n^2) WIS algorithm pretty nicely: http://www.cs.illinois.edu/class/fa08/cs473/Lectures/lecture12.pdf

There's also an O(n log n) algorithm, but it's a bit more complicated: http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec3.pdf

The UVa online judge has a list of Dynamic Programming problems: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114

I can't recall any UVa problems that are Weighted Interval Scheduling though... but solving DP problems will help you with other DP problems because they all have important similarities.

→ Ответить

liuyubobobo

14 лет назад, # ^ |

thank you so much!

i never expect somebody may answer such a primary question so detailed!

thank you very much!

→ Ответить

wjomlex

14 лет назад, # ^ |

Welcome :)

→ Ответить

forthright48

12 лет назад, # ^ |

← Rev. 2 →

-6

I have never heard of Weighted Interval Scheduling DP before. Thanks for sharing your resource. You sir, are awesome! :D

Here, I found another source:

www.cs.cornell.edu/courses/cs482/2007su/dynamic.pdf

This contains both N^2 and NlogN idea.

→ Ответить

PavelKunyavskiy

14 лет назад, # |

А куда делась отсылка текстом а не файлом? Или ее убрали специально?

→ Ответить

14 лет назад, # ^ |

Случайно вышло: она обязательно вернется :)

→ Ответить

cortez

14 лет назад, # |

А задачу Е можно свести к задаче о решении системы линейных уравнений?

→ Ответить

KADR

14 лет назад, # ^ |

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

Пусть f(i,a1,a2) равно наименьшему количеству измененных символов, требуемому для того чтобы первые i строк стали подходящими и в строке i чередовались символы a1 и a2 (a1!=a2).

Тогда запишем f(i,a1,a2)=min{f(i-1,b1,b2) | a1!=b1 && a2!=b2 && b1!=b2}+cost(i,a1,a2), где cost(i,a1,a2) - количество изменений, необходимое для того чтобы в строке i чередовались символы a1 и a2.

→ Ответить

steiner

14 лет назад, # ^ |

И это O (n * 26 ^ 4), верно? Это заходит?)

→ Ответить

KADR

14 лет назад, # ^ |

Успевает меньше чем за секунду. Можно ускорить до O(n*26^3), если после подсчета f(i,a1,a2) для всех a1 и a2 пересчитывать матрицу M, элемент M(a1,a2) которой равен min{f(i,b1,b2} | | a1!=b1 && a2!=b2 && b1!=b2}. Заметим, что из f(i,j,*) мы возьмем минимум, либо второй минимум. Значит, матрицу M посчитать можно за куб. Думаю, если еще подумать, то можно ускорить и до квадрата :)

→ Ответить

steiner

14 лет назад, # ^ |

Ясно, спасибо) Я был уверен, что не зайдёт.

→ Ответить

Dru	14 лет назад, # \| 0 Когда вижу длинные числа, всегда кажется что притесняется C++ :) Как работать с длинной арифметикой, в задаче D, например? Разрешается ли пользоваться заготовленным кодом? → Ответить

Edvard

14 лет назад, # ^ |

Я пишу на C++. Но если на контесте попадётся задача на длинку то я включаю Eclipse

→ Ответить

fetetriste

14 лет назад, # ^ |

И пишете на C++ в Eclipse?

→ Ответить

Edvard

14 лет назад, # ^ |

Непонятка вышла. Не на С++ я пишу в фаре, а в Eclipse пишу на Java (несмотря на то что не умею писать на Java :))

→ Ответить

nk.karpov

14 лет назад, # |

Помоему написать свою длинку дело 15 минут )) к тому же тут нету сложных операций ;) (Деление, извлечение корня, быстрого умножения)

→ Ответить

Dru	14 лет назад, # ^ \| 0 15 минут из 120 - время. На Java ведь их не надо тратить. При составлении задач, похоже, на длинную арифметику уже никто внимания не обращает. Означает ли это, что заготовки кода разрешены? → Ответить

14 лет назад, # ^ |

А почему нет? В конце концов ты у себя дома пишешь

→ Ответить

Dru	14 лет назад, # ^ \| 0 Ну ок, и то правда. Будем считать, что разрешено всё, что не запрещено. → Ответить

14 лет назад, # ^ |

Я считаю, что заготовки нельзя использовать и разрешать (конечно нельзя отследить никак, но все же), так как таким образом человек может просто скопипастить любой стандартный алгоритм.

Так что задачи на длинную арифметику - абсолютное зло

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

Что собственно все и делают, потому что это нормально.
Идиотизм-то как раз таки по 200 раз писать один и тот же алгоритм.

Например я давно для себя сделал штучку типа skidanovalex.ru/ahelper.html, чтобы не зависимо от того, откуда я пишу, все нужные алгоритмы были со мной :о)

→ Ответить

dev_il

14 лет назад, # ^ |

прикольно =) ... похоже ты сейчас не один будешь пользоваться своей штучкой )

→ Ответить

daftcoder

14 лет назад, # ^ |

Меня крайне порадовал контраст:
"I'm a computer programmer. I like coding a lot, and not so long ago I was one of the best tough-algorithms coder in the world.
Here's the list of my selected achievements. Some of the scoreboards..."
Русская версия - Если в двух словах - я программист и металлюга :о)
И дальше по тексту... :)

→ Ответить

AVoz	14 лет назад, # \| 0 у кого нибудь в задаче Д были проблемы с 4-м тестом? можете привести контрпример или вспомнить в чем была ошибка? → Ответить

14 лет назад, # ^ |

Ты решение сначала напиши)))

→ Ответить

AVoz	14 лет назад, # ^ \| 0 не понял? идею сюда написать? или имеете в виду что я не отправлял решения? ЗЫ если второе то будьте внимательнее у меня и во время и после контеста есть отправленные решения → Ответить

Edvard

14 лет назад, # ^ |

+12

Всё зависит от твоего решения. В моём решении была проблема, что я проверял на юзанность не весь отрезок, а только концы.

→ Ответить

RAD	14 лет назад, # ^ \| 0 Если еще нужно, 4й тест: 10 sell 179 win 1278 sell 1278 win 179 win 788 sell 788 win 1819 win 1278 sell 1454 sell 1819 → Ответить

AVoz	14 лет назад, # ^ \| 0 спасибо большое! → Ответить

fobnn

14 лет назад, # |

Hi,i'm a newbie

→ Ответить

14 лет назад, # |

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

→ Ответить

nk.karpov

14 лет назад, # |

Вопрос совести ? )) всё равно никто контролировать не будет, а можно научится кодить на Java или Python

→ Ответить

Dru	14 лет назад, # ^ \| 0 Не хочу Java или Python :) Участники должны быть в равных условиях. Видимо, это означает, что единственно верный вывод - разрешить любые заготовки. Кроме всего прочего, это более естественно. → Ответить

Egor	14 лет назад, # ^ \| 0 ну вот у Java проблемы вечные с тл там, где решения на плюсах легко проходит. У всего есть свои плюсы и минусы → Ответить

Tactic

14 лет назад, # |

Nice problems!

I have a question though. How am I supposed to include the BigInt class in my solution? I'm writing in C#.
Thanks!

→ Ответить

ma327

14 лет назад, # ^ |

long long int i guess.

→ Ответить

Tactic

14 лет назад, # ^ |

How do I declare a long long int?
and is it enough to hold 2^2000?

→ Ответить

ridowan007

14 лет назад, # ^ |

I dont know about C# but as for C/C++ long long int can cover only 2^63 . long long unsigned can 2^64

→ Ответить

Tactic

14 лет назад, # ^ |

So how could this be solved in C#?

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

In .NET 4.0:

using System.Numerics;

BigInteger a;

Then you can use it as a regular integer number. All the operators are overloaded, so you can easily do something like that:

BigInteger a = BigInteger.Parse( Console.ReadLine( ) );
BigInteger b = BigInteger.Parse( Console.ReadLine( ) );
BigInteger c = a + b;

But AFAIR this server doesn't support .NET 4.0, so anyway you will need to implement big integers by hands if you want to solve that problem using C#.

→ Ответить