COCI 2012/2013 Contest #3

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

+13

Как то 2 последние задачи на впихивание по памяти вышли. :(

→ Ответить

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

в предпоследней можно было строки отсортить. и с памятью все ок.

→ Ответить

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

Я думал над таким, но такое еще нужно загнать во время.

→ Ответить

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

нет, оно вообще легко заходит.

→ Ответить

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

Я очень не думал над реализацией, думал такое не зайдет. Видимо нужно было чуть больше посидеть над ней. :)

→ Ответить

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

Ага, как-то я не подумал, что маленький суммарный размер массивов — это еще не все. Сам dfs съел памяти больше, чем 32 МБ.

→ Ответить

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

И наложился вопрос: почему бы не поставить МЛЕ 256 МБ?

→ Ответить

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

Потому что это без такого ограничения, на мой взгляд, эта задача на 6ю не тянула.

→ Ответить

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

Ну тогда можно было сразу 8 МБ ставить. Хотя, с 32 МБ это вышло даже поучительно — иногда память съедается там, где вообще не ждешь.

→ Ответить

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

Ну я пока не представляю, как это можно запихнуть в 8 МБ, если разбивать каждый регистр на 32 вершины для BFS. Получаем, что одна очередь = 3.2М * 4. А как не разбивать я пока тоже не знаю, можно поделиться пожалуйста?

→ Ответить

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

Ну ответы можно хранить в массиве интов длины 100000. А насчет bfs — граф-то у нас специфический, так что в очереди одновременно сильно много чисел не могут находиться. Если писать с STL'евской queue, то память будет вовремя очищаться. Кстати, 7.7 МБ это если хранить граф списками смежности, создав 100000 векторов. Если же на массивах сделать, то еще меньше будет.

→ Ответить

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

← Rev. 2 →

ОК, спасибо, но тут всё-таки надо опираться на недоказанные вещи (что в очереди не будет много вершин одновременно — или это доказывается?), а с 32 МБ можно доказать что хватит на всех тестах, на всех языках (STL есть только в C++, а писать свой queue с выделением памяти — overkill) и не надо особо сильно извращаться, на мой взгляд. Так что по-моему, 8 всё-таки было бы перебором.

→ Ответить

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

Если уже говорить о других языках, то закономерный вопрос: эта задача решается на Java?

Насчет размера очереди — я не знаю, как доказать что он маленький и всегда ли это так.

→ Ответить

niyaznigmatul

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

Как уже ниже рассказали можно с помощью СНМ. На Java зашло без проблем. Хотя BFS тоже должен зайти, ребер мало, надо только очередь хранить.

→ Ответить

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

← Rev. 2 →

А если то же самое сделать bfs-ом, то проходит все тесты, заюзав максимум 7.7МБ. Задача на то, чтобы попихать.

→ Ответить

LashaBukhnikashvili

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

← Rev. 2 →

Individual results update!

UPD: My score is 350(50+80+100+120)

→ Ответить

GaryYe

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

← Rev. 2 →

Is problem F(PROCESOR) a graph problem?

I'm sorry if this question is really stupid :(

→ Ответить

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

+17

Yes, it is 2-SAT problem. But memory limit is realy stupid.

→ Ответить

usg

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

← Rev. 2 →

Can you explain more why problem F is 2-SAT problem? Thanks

→ Ответить

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

Why is it 2-SAT? You have a graph (32*N vertices) with edges which demand either different numbers on endpoints or the same. You can just DFS/BFS it to enumerate each connected component and since each component can be easily inverted — you can take the most significant vertice and assign 0 to it at the start of DFS/BFS.

The only challenging point is to get it into memory limit.

→ Ответить

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

And you can get into memory limit by making 2 optimizations:

While you have 32*E edges, don't store 32*E edges, store just E, which I will call multiedge. Since every multiedge generates exactly one edge for each vertice in the given register, we can decode it while doing DFS/BFS.
Use BFS, since it haven't got any overhead from recursion. Hence you only need 2 3.2M element arrays — one of char for storing assign bits (and simultaneously checking if we have been in that vertice) and one of int for the BFS queue.

→ Ответить

gen

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

We can use non-recursive DFS as well.

→ Ответить

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

← Rev. 2 →

But why? BFS is meant to be non-recursive, while in DFS you would have to store a lot more information about each vertice to be able to emulate recursion. So it might not pass in ML either, or I am missing something.

→ Ответить

gen

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

I don't understand. Can't we just change queue to stack?

→ Ответить

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

Yeah, but you still need more information, like the pointer of what neighbor of that vertice we are currently analyzing.

→ Ответить

gen

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

-8

Why? I always wrote non-recursive BFS and DFS with the only difference of queue and stack. Or do you mean some specifics of your solution for this problem?

→ Ответить

MarioYC

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

Yes, you can use a modified Union-Find.

→ Ответить

harhrayr

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

← Rev. 2 →

I had a bug in task 6 , when I finded it, the cotest ended :( This is my corrected code.

UPD: my score is 453

→ Ответить

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

← Rev. 2 →

You still have 64 points — you got MLE.

Sorry, I don't mean to be rude, but your comment easily suggests that you claim that you have full solution to 6th task.

→ Ответить

harhrayr

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

thanks, everything is ok :D

→ Ответить

.o.

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

My score is 490(50+80+100+120+140+0). I couldn't find any solution on the last problem T.T

→ Ответить

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

Weak tests in problem AERODROM My solution fails test:

30 1000
1 1 1 1 ... 1 1 1

but passes systests. Have anybody the same bug?

→ Ответить

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

Not only that — shouldn't you have long long overflow in this case?

100000 whatever
1 1 1 ... 1 1 1

→ Ответить

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

Yes, and in my test I have overflow too.

→ Ответить

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

Well, luck is on your side then. :) Maybe they haven't thought of this specific error, while generating the test, although I thought that this could be the place where many could fail. But as it depends on binary search values, and from a quick look you have a little bit different binary search from what I usually see people writing (either not changing middle value at all when assigning it, or changing but only in one case, not in both), maybe you got away with this for that reason.

→ Ответить

KAN

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

My solution is similar to your, but I set the bound to 2e18, and it fails on systests (105/120). Our solutions have the same bug, but I have less points than you have. It seems strange.

→ Ответить

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

I'm lucky today. I think it's impossible to catch all bugs using 8 tests.

→ Ответить

kuzmichev_dima

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

← Rev. 3 →

Imho, it's very bad idea to test solutions on less than 10 test cases (for example, today's task "malcolm" has only 5 tests)... Then I see so few tests, I remember informatics olympiads in my school, where we always have 5 tests, and almost everything passes them ;)

PS and, ofc, I have the same bug as tunyash in aerodrom, but my solution gets full score...wtf

→ Ответить

accidentallygivenfuck

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

← Rev. 2 →

I wonder will they add some extra tests, as they don't display general results immediately ?

→ Ответить

definitelynottourist

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

-8

Why am I getting "SIGABRT" while I am not using any assert method out there?

→ Ответить