Анонс мероприятий Регионального Сообщества Спортивного Программирования

[The_Ice]

Да, что-то после знакомства с ФЯПами, на C как то писать стало лень)))

Пытался на codeforces на нем писать, но, постоянно упирался в ограничение на размер выходного файла, а вот на http://www.spoj.pl/ ограничение не такое суровое (:

Хотя, довольно продолжительное время, забиваю я на программирование

[0xDEADBEEF]

The_Ice

Ну мы ради великого Зеайса добавим)

ICFP не пробовал?

[The_Ice]

Не, не пробовал)

Можно попробовать, хотя я уверен, что буду на дне турнирной таблицы - навыки растерял уже (:

Просто вспомнилась фраза про хаскелл из твоего блога, вот и решил поинтересоваться о том, как дела у тебя с ним обстоят

[0xDEADBEEF]

ололо у меня же блог есть

Если честно сам не помню что было там) А на Хаскелл периодически посматриваю, да только руки не доходят серьезно заняться.

[The_Ice]

Разговор заставил меня вернуться к spoj.pl и я вспомнил что меня бесит в решении на haskell - это сложность уложиться в лимит времени

Вроде, задача не сложная:

The Next Palindrome

Problem code: PALIN

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:

2

808

2133

Output:

818

2222

Time limit: 9s

Source limit: 50000B

Пишем первую версию программки, получаем "time limit exceeded", вторую - с тем же результатом, ... приходим к четвертой версии с использованием мемоизации и принудительной строгости примерно такого вида:

module Main where

{--

смысл кэша:
имеем Map (число, следующий палиндром)
на каждой итерации смотрим: есть ли в мапе число <= нужного, но палиндром
которого больше данного нам числа, если нет - вычисляем, если есть -
возвращаем уже вычисленный палиндром
-}

import System.IO

import qualified Data.Map as IMap
import Control.Monad.State

type PolMap = IMap.Map Int Int
type PolS = State PolMap Int

tens = [ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
1000000000, 10000000000]

-- "рабочая" рекурсивная функция функции is_palindrome
_is_pali:: Int -> Int -> Bool
_is_pali x n | x < 10 = True -- однозначное число - это палиндром
| otherwise = x`seq`n`seq`
let last_digit = x `mod` 10
first_digit = div x $! ( tens !! n)
next = tailed `div` 10
tailed = mod x $! (first_digit * (tens !! n))
in if last_digit /= first_digit
then False -- если первая цифра /= последней - значит не
-- палиндром
else if n < 3 then True -- если число 2х/3х значное,
-- то нет смысла смотреть дальше
else next `seq` _is_pali next $! (n-2)

-- возвращает True, если переданное число - палиндром
is_palindrome:: Int-> Bool
is_palindrome x = x `seq`
let fcnt = (fromIntegral x)::Float
cnt = floor $! logBase 10 fcnt
in _is_pali x $! cnt

-- собственно - бэк-энд для нахождения следующего палиндрома
next_palindrome:: Int-> Int
next_palindrome x = if is_palindrome x
then x
else next_palindrome $! x+1

-- next_palindrome с использованием кэширования вычислинных "следующих"
-- палиндромов
mem_next_palindrom::Int-> PolS
mem_next_palindrom num = do
cache <- get
-- найдем максимальный вычисленный палиндром
let (max_key, max_pali) =
case IMap.null cache of
True-> (1,2)
_ -> IMap.findMax cache
if num >= max_pali
then do
-- если переданное число больше сохраненного палиндрома, то нет
-- смысла искать в кэше
let next_pali = next_palindrome num
put $! IMap.insert num next_pali cache -- сохраняем в кэш
return next_pali
else do
-- функция поиска подхдящей пары в кэше:
-- key должен быть меньше или равен переданному числу, а value > его
let filter_foo k v = k `seq` v `seq`
if k <= num && v > num then True
else False
filtered = IMap.toList $! IMap.filterWithKey filter_foo cache
case filtered of
[]-> do -- если подходящих значений не найденно - вычисляем и
-- добавляем в кэш
let next_pali = next_palindrome num
put $! IMap.insert num next_pali cache
return next_pali
((_,next_pali):_) -> return next_pali -- ура, оптимизация!

-- efficient next_palindrome - бэк-энд для next_palindrome с использованием кэша
eff_next_palindrome:: Int-> PolMap-> Int
eff_next_palindrome num cache = evalState (mem_next_palindrom num) cache

main = do
cnt' <- getLine
let cnt = (read cnt')::Int
cache::PolMap
cache = IMap.empty
input 0 = return ()
input n = do
line <- getLine
let some = (read line):: Int
print $! eff_next_palindrome (some + 1) cache
input $! (n-1)
input cnt

но, по-прежнему получаем time limit exceeded

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

В итоге: --ЧСВ и засыпаю в дурацком настроении))) Конечно, по-хорошему, нужно было бы переписать на Сях и сравнить результат, но мне лень гг

[0xDEADBEEF]

Решение линейное. А это как-то на него не походит(

#include

const int MAXLEN = 1000000;

char s[MAXLEN], l[MAXLEN/2], rl[MAXLEN/2];

void next(){
memset(l, 0 , sizeof l);
memset(rl, 0 , sizeof rl);

int n = strlen(s);
int m = (n & 1) ? (n+1)/2 : n/2;
int i = 0;

//collect polyndrom
while(i l[i] = s[i];
i++;
}

for (int j = 0; j<=m; ++j){
rl[j] = l[m-j-1];
}

for (int j = m-(n&1), c = 0; j s[c] = s[j];
}
s[m] = 0;

// printf("RL: %s R: %s\n",rl,s);

if (strcmp(rl,s)<=0){
i--;
while(i>=0){
if (l[i] != '9'){
l[i]++;
break;
} else {
l[i] = '0';
i--;
}
}
}

// print
if (i < 0) {
putchar('1');
i = n;
while(--i)
putchar('0');
putchar('1');
} else {
i = m;
printf("%s", l);
if (n & 1)
--i;
while (--i >= 0) {
putchar(l[i]);
}
}
putchar('\n');
return;
}

int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%s", s);
next();
}
}

#include 

Пора наверно мутировать в хаскел-гуру...

[The_Ice]

Ох уж и намучался я с решением. Судя по всему, spoj.pl тоже меня опрокинул.

Твою прогу на С++ принял, а все мои на хаскелл отверг по TLE, я уже было решил плюнуть на хаскелл, коль я не умею писать на нем быстрый код, но, решил сравнить результат прог на своих данных и был и удивлен и разочарован одновременно:

Итоговая версия, на которой я решил прекратить попытки аппрува на spoj.pl, работает со строками и не проверяет, является ли число палиндромом (аналог твоей на С++) и выглядит так:

import Data.Char
import qualified Data.ByteString.Char8 as B

next_num:: B.ByteString-> B.ByteString
next_num str | B.null str = let !ret = B.pack "1"
in ret
| otherwise =
let !last_c = digitToInt $! B.last str
!headed = str `seq` B.init str
in if last_c < 9
then let !ret = B.snoc headed $! intToDigit (last_c+1)
in ret
else
let !inc_headed = next_num headed
!ret = B.snoc inc_headed '0'
in ret

next_polindrome:: B.ByteString-> B.ByteString
next_polindrome current =
let !len = B.length current
!half_len = (len `div` 2) + if odd len then 1 else 0
!half = B.take half_len current
!rhalf = B.reverse half
!tail_ = B.drop half_len current
!even_len = if (rhalf > tail_)
then let !ret = half `B.append` rhalf
in ret
else let !inc_half = next_num half
!inc_rhalf =
if (B.length inc_half > B.length half)
then B.tail $! B.reverse inc_half
else B.reverse inc_half
!ret = inc_half `B.append` inc_rhalf
in ret
!half_less = B.init half
!rhalf_less = B.reverse half_less
!odd_len = if (rhalf_less > tail_)
then let !ret = half `B.append` (B.reverse half_less)
in ret
else let !inc_half_raw = next_num half
!inc_half =
if B.length inc_half_raw > B.length half
then B.init inc_half_raw
else inc_half_raw
!inc_rhalf =
B.reverse $ B.init inc_half_raw
!ret = inc_half `B.append` inc_rhalf
in ret
in if even len
then even_len
else odd_len

main = do
cnt' <- getLine
let !cnt = (read cnt')::Int
input 0 = return ()
input n = do
line <- B.getLine
let !dropped = B.dropWhile (=='0') line
!next = next_polindrome dropped
B.putStrLn next
input (n-1)
input cnt

module Main where

Входные данные генерились просто:

Prelude> let nums = max_n:[1..max_n]
Prelude> let content = unlines $ map show nums
Prelude> writeFile "data" content

Prelude> let max_n = 100000

Т.е. первая строка - число 100000, а все остальные - это числа от 1 до 100000 включительно

Программы собирались такими командами:

ghc --make ./Palindrome.hs -o ./pali
g++ -O3 ./Test.cpp -o ./test

The Glorious Glasgow Haskell Compilation System, version 6.12.1
ice@desktop:~/devel/spoj/palindrom$ g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5

ice@desktop:~/devel/spoj/palindrom$ ghc --version

А запускались такими:

$ cat ./data | ./pali > ./pali_out
$ cat ./data | ./test > ./test_out

Т.е. вывод программы на haskell писался в pali_out, а твоей на С++ - в test_out и diff различий не находил

ice@desktop:~/devel/spoj/palindrom$ echo $?
0

ice@desktop:~/devel/spoj/palindrom$ diff ./pali_out ./test_out

Но! Самое интересное показали вот результаты вот этих команд:

ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./test > /dev/null`

real	0m37.444s
user	0m37.430s
sys	0m0.000s
ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./pali > /dev/null`

real	0m2.647s
user	0m2.640s
sys	0m0.000s

Тут я начал сильно сомневаться, но вот это говорит о том, что все правильно:

real 0m38.103s
user 0m38.080s
sys 0m0.010s
ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./pali > ./pali_out`

real 0m2.596s
user 0m2.580s
sys 0m0.010s
ice@desktop:~/devel/spoj/palindrom$ diff ./pali_out ./test_out
ice@desktop:~/devel/spoj/palindrom$ echo $?
0

ice@desktop:~/devel/spoj/palindrom$ time `cat ./data | ./test > ./test_out`

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

Оставалось только думать, что ситуация меняется при обработке чисел с 1_000_000 цифр, что и требовалось проверить, поэтому составил набор данных с БОЛЬШИМИ числами:

Prelude> let min_n = 10 ^ 1000000
Prelude> let max_n = min_n + 20
Prelude> let nums = 20:[min_n .. max_n]
Prelude> let content = unlines $ map show nums
Prelude> writeFile "huge" content
Prelude>
Leaving GHCi.

Удалил старые результаты, на всякий пожарный:

ice@desktop:~/devel/spoj/palindrom$ rm out
ice@desktop:~/devel/spoj/palindrom$ rm out1

И, момент истины:

ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali > ./pali_out`

real	0m0.667s
user	0m0.410s
sys	0m0.290s
ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./test > ./test_out`

real	0m1.351s
user	0m1.010s
sys	0m0.370s

И, вот с таким вот выражением лица , я осознаю, что за это время я успел и кэш прикрутить и многопоточность и все четно - я по-прежнему получаю time limit exceeded)))

Более того, выявился 1 баг:

-rw-r--r-- 1 ice ice 20000040 2011-01-30 00:04 pali_out

-rw-r--r-- 1 ice ice 30000040 2011-01-30 00:05 test_out

Учитывая, что в файле должно содержаться 20 чисел, состоящих из 1000000 цифр + 20 символов перевода строки, создается впечатление, что программа на С++ содержит багу (:

строка

char s[MAXLEN+1], l[(MAXLEN/2) + 1], rl[(MAXLEN/2)+1];

решает

Ушел на форум spoj.pl со злым выражением лица)

UPD:

Интересно то, что ленивая версия программы работает еще быстрее:

import Data.Char
import qualified Data.ByteString.Lazy.Char8 as B

next_num:: B.ByteString-> B.ByteString
next_num str | B.null str = B.pack "1"
| otherwise =
let last_c = digitToInt $ B.last str
headed = str `seq` B.init str
in if last_c < 9
then B.snoc headed $ intToDigit (last_c+1)
else
let inc_headed = next_num headed
in B.snoc inc_headed '0'

next_polindrome:: B.ByteString-> B.ByteString
next_polindrome current =
let len = B.length current
half_len = (len `div` 2) + if odd len then 1 else 0
half = B.take half_len current
rhalf = B.reverse half
tail_ = B.drop half_len current
even_len = if (rhalf > tail_)
then let ret = half `B.append` rhalf
in ret
else let inc_half = next_num half
inc_rhalf =
if (B.length inc_half > B.length half)
then B.tail $ B.reverse inc_half
else B.reverse inc_half
in inc_half `B.append` inc_rhalf
half_less = B.init half
rhalf_less = B.reverse half_less
odd_len = if (rhalf_less > tail_)
then half `B.append` (B.reverse half_less)
else let inc_half_raw = next_num half
inc_half =
if B.length inc_half_raw > B.length half
then B.init inc_half_raw
else inc_half_raw
inc_rhalf =
B.reverse $ B.init inc_half_raw
in inc_half `B.append` inc_rhalf
in if even len
then even_len
else odd_len

main = do
cnt' <- getLine
let cnt = (read cnt')::Int
content <- B.getContents
let lines = take cnt $ B.lines content
output [] = return ()
output (l:ls) = do
let dropped = B.dropWhile (=='0') l
B.putStrLn $ next_polindrome dropped
output ls
output lines

module Main where

С такими результатами на тех же данных data:

real 0m0.964s
user 0m0.930s
sys 0m0.020s

$ time `cat ./data | ./pali_l1> /dev/null`

Данные по времени на списке 800 больших чисел:

Prelude> let max_n = min_n + 800
Prelude> let nums = 800:[min_n .. max_n]
Prelude> let foo num = do{ appendFile "huge" $! (show num)++"\n"}
Prelude> mapM_ foo nums

Prelude> let min_n = 10 ^ 1000000

real 0m7.150s
user 0m5.470s
sys 0m3.230s
ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./test> /dev/null`

real 0m40.444s
user 0m38.760s
sys 0m4.580s
ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali> /dev/null`

real 0m19.001s
user 0m17.010s
sys 0m4.350s

ice@desktop:~/devel/spoj/palindrom$ time `cat ./huge | ./pali_l1> /dev/null`

pali - это строгая версия, pali_l1 - ленивая. А я всегда старался избавиться от ленивости *28

PS: извиняюсь за столь длинный пост - просто я немного озадачен результатом (:

[Agarb]

Пробежался по тексту и...

Если описанные в задачи действия выполнять «в лоб»...

Спасибо! поправили.

[Kenny#]

вопрос к организаторам.Вы не проводите открытых тренировок?Хотелось бы набраться опыта.

[0xDEADBEEF]

Kenny#

У нас в ближайших планах открытый семинар. Следите за анонсами.

[Kenny#]

Господа программисты!Прошу помощи ,совета так сказать.Не так давно, мой разум захватила идея решения задач формата ACM/ICPC .Так вот начал с acmp.ru там задачки простенькие решаемые,далее проджект эйлер ну в принципе нормально терпимо-решаемо.Затем попал на

timus и mipt вот тут подвис конкретно задачи уровня начинающих не всегда по "зубам" также учавствовал в контестах РССП (спасиб вам ) где успешно провалился.Так вот как господа прокачаться?вроде в суть задач врубаюсь но что-то не так.вижу слабые места залатываю -пробел в знаниях ,но снова неудача.Дайте что-ли направление как дальше двигаться.

p.s. вроде не дурак если важно единомышленников не имею

[danger]

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

\ | /

\/

[Agarb]

одной из самых хороших подготовкок я считаю схему:

"контест-разбор-дорешивание".

Так готовятся чемпионы России (ну и мира соответственно ) на Петрозаводских сборах по СП.

в контестах РССП мы тоже будем стараться придерживаться этой схемы.

также есть хорошие соревнования на codeforces.ru. Там в блоге после контеста почти всегда появляется разбор, и всегда доступно дорешивание. Так же по соревнованиям opencup.ru почти всегда в сети можно найти разборы и есть дорешка. Но не только эти сайты, - это вообще распространено. И topcoder.com кста тож нужно упомянуть )))

Кстати, началась серия контестов IX Открытого Кубока им. Е.В. Панкратьева по программированию (opencup.ru). Эти контесты проходят по воскресеньям и пересекаются по времени с нашими, поэтому привычное время проведения наших контестов вероятно изменится.

Пожалуйста, напишите кому какое-время удобно.

Например, насколько удобно будет время с 19:00 до 23:00 в будний день (напр. четверг)?

[0xDEADBEEF]

Дорешивание контестов будет доступно в четверг и пятницу (03.03 - 04.03) с 19.00 до 23.00

ЗюЫю В группе вконтакте есть раздел полезных ссылок.

[0xDEADBEEF]

В субботу (29 октября 2011 года) в 17:00 в аудитории 1316 Бурятского госуниверситета (1-й корпус - за памятником Доржи Банзарову на Ул.Ранжурова, 5, 3-й этаж) состоится первая из серии открытых лекций по структурам данных и алгоритмам.

Тема "Дерево отрезков - реализация и применение".

Также планируется обсуждение планов развития сообщества.

Приглашаются все желающие.

[0xDEADBEEF]

В субботу (5 ноября 2011 года) в 17:00 в аудитории №100 ВСГУТУ (1-й корпус - ул. Смолина 26, вход со двора) состоится вторая из серии открытых лекций по структурам данных и алгоритмам.

Тема "RMQ (Range Minimum Query)".

Приглашаются все желающие.

[0xDEADBEEF]

В субботу (12 ноября 2011 года) в 17:00 в аудитории №100 ВСГУТУ (1-й корпус - ул. Смолина 26, вход со двора) состоится третья из серии открытых лекций по структурам данных и алгоритмам.

Тема "Programming tips and tricks".

Приглашаются все желающие.

[nonlux]

Идея лекций очень хорошая. Жаль на первые две не попал да и в эту субботу обломс(.

Так как я не разу не был ВСГУТУ, так вход свободный?

Если я пропустил три лекции как это наверстать? ведь все что я не найду в инете, будет отличаться от ваших лекций на хочется быть на той же волне. в открытые просторы сети ты их не выкладываешь?

[0xDEADBEEF]

nonlux

Вход свободный, у охранника можно спросить как пройти до аудитории, я думаю.

Материалы по предыдущим лекциям можно легко найти на e-maxx.ru, по соответствующей тематике.

[nonlux]

Спасибо.

[D_Master]

Какова примерная продолжительность лекции?

[0xDEADBEEF]

D_Master

1.5 - 2 часа

[0xDEADBEEF]

В субботу (19 ноября 2011 года) в 17:00 в аудитории №100 ВСГУТУ

(1й корпус — ул. Смолина 26, вход со двора)

состоится четвертая из серии открытых лекций по структурам данных и алгоритмам

Введение в алгоритмы на графах

Приглашаются все желающие!

[0xDEADBEEF]

В субботу (26 ноября 2011 года) в 17:00 в аудитории №100 ВСГУТУ

(1й корпус — ул. Смолина 26, вход со двора)

состоится пятая из серии открытых лекций по структурам данных и алгоритмам

Поисковые алгоритмы на графах 1

Приглашаются все желающие!

[0xDEADBEEF]

В субботу (3 декабря 2011 года) в 17:00 в аудитории №1316 БГУ (ул. Ранжурова 5, 3 этаж)

состоится шестая из серии открытых лекций по структурам данных и алгоритмам.

Поисковые алгоритмы на графах 2: кратчайшие пути.

Приглашаются все желающие!