The contest is mov
Добро пожаловать на 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + misc). Продолжительность тренировки — 4 часа 30 минут. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!
Удачи!
Why?
Perhaps... To prevent intersection?
Very good question though
Isn't it better to move CF Round rather than Training Episode? Rounds are always on different days, while having Training Episodes on certain day would allow teams to include it to their regular trainings schedule.
I also expected the CF round to be moved instead. Maybe it just has lower priority since it's Gym... and can be done in virtual participation anyway.
And now I'm also curious why this got many downvotes in a short time.
Considering the number of participants (CF Round 267: 4k7, last gym training: less than 400), we can clearly see why the training should be moved.
I was not talking about the amount of the audience, was I?
Those 4.7k would participate on any day of the week, because it's ok to have cf rounds on different days and it's not difficult to schedule a 2-hours round for a single person comparing with scheduling 5-hours contest for teams of three.
How is problem F solved ?
Anyone can help me find my mistake on J? Here's my code : http://pastebin.com/T5vuiMHG
I get WA on test 2, but I can't see the test data and I have no idea where could I be wrong (can't think of any test case).
Why can't I see other solutions after the end of contest?
Because it is gym not usual CF round.
you can see other solutions after accepting it first.
I have correctly submitted problem C. But I can't see other solutions.
I can't really think of a good reason why it's made that way!! Is it for pushing your brains as one pushes his muscles in a real Gym?
Ha ha. Well-said. There must be some reason for it.
Yes. You can see other solutions after getting it accepted. http://codeforces.net/gym/100486/submission/------- Put the submission number in the blank place.
The author of the problem A probably was angry with life at the moment of creating it...
Hehe, you apparently don't have much experience with CTU Open. Nasty problems are relatively common there (which is normal considering there's a technical university involved).
Please someone discuss problem E (Invasion) and problem F (Intergalactic Mortgage). It will be really helpful.
I could not find a way for the problem E and got TLE in problem F using brute force.
Well obviously you got TLE, there are millions of cases in the input file. Not like it'd be so simple.
E: remember the min. distances to each vertex from the bad ones, update it using Dijkstra with breaks
F: linear recurrence relation
And while I'm at it, D is a simple O(NM) DP.
remember the min. distances to each vertex from the bad ones
How can I do that? Would you please explain in details please?
In one array. Do you know Dijkstra's algorithm? You remember distances there.
My question on problem F: What you mean by linear recurrence relation? I had simple linear recurrence relation too, but tried to find answer in O(n) for every test case, but it gave TLE. Can you please tell more about your solution? Is your solution faster? P.S. I had an idea about matrix exponentiation, but I think it is not necessary here
This talks also about linear recurrences and their solutions. There is a formula that allows you to compute the result in O(1).
I don't know what you mean by necessary, an O(N) solution obviously can't solve a million test cases in a second. Sure, you can use matrix exponentiation, you can use double exponentiation, whatever works in O(1) or
. Not O(N).
Thank you. By necessary I meant that there may be solution that is much easier. Most of contestants solved it too fast.
I don't know what kind of easier solution than googling a formula you have in mind, but I assure you no bruteforce would work.
my soln with complexity O(log N) is giving TLE for Problem F. :(
It's not because of that, it's because you're using cin on doubles.
Care to explain why cin on doubles should be avoided?
Because it's slow, why don't you guess...
(I don't know why it's slow, I don't have insight into C++. But it doesn't matter.)
The solution of problem E is do dijkstra for each consul and do the dijkstra only when the distance of bad node to good node is < k, the demostration of the time of the algorithm is:
the time of dijkstra is the number of number of times update one node, in this case the algorthm update each node k times, the time in general is O(k*nodes + k*edges)
Zorry for my english.
I know, you don't have to tell me :D
Any ideas on G?
Maybe, hypothetically speaking, there could be a heuristic — but the input size is large as hell, so I'd say that you need a sweepline algorithm that maintains the set of lines ordered by their intersections points with the sweepline. It has a name, google it — or you can think about it yourself, it should be similar to the convex hull trick in DP.
It feels like CTU Open problemsetters always tell themselves "so, for a seriously hard problem, let's have reasonably obvious but nasty geometry".
Any suggestion on how to solve problem B ?
take one number, use algorithm described in statement while number != 1, and save in std::map<long long, int> number of steps:
let d[x] be the number of steps to conver first number to number 'x'
then use algorithm to convert second number to 1 and while converting choose the shortest way to do convertation
How to solve I?
Optimized backtrack, probably. The authors suggest doing stuff like "if there's a cell with 1 neighbour, put a tile there first".
Это оффтопик, но последние два дня при попытке создать запись в блоге появляется страница "Codeforces временно недоступен".
Это только у меня так?
Прошу совета:
Как доказать в E что просто обновлять мин. расстояния из каждой базы до других зайдет в TL, как оценить кол-во операций? Одна дейкстра может работать за MlgN, т.к. расстояние до 100, то можно сделать bfs за M, но, это все равно выглядит не очень быстро.
F, использование формулы за O(1) (x*r^(n) — y(1 — r^n)/(1-r)) для получения остатка через все время дает WA, видимо из-за переполнения double до inf в тестах с большим нашим платежом и процентом, как сдать?
в Е там типа каждая вершина обновится максимум 100 раз
в Ф у нас был косяк с r == 0.
Вершина да, но просмотров ребер может быть больше.
ну там O(M * k) получается.
http://1drv.ms/1ttasBH картинка
тоже не согласен. В этом примере на каждое добавление могут пересчитываться почти все ребра.(т.е. организовываем N/2 элементов в такое дерево, остальные привязываем к корневой вершине полным графом), каждое добавление будет доходить до корня и обновлять расстояния в полном графе.
ну так не более 100 раз же дейкстра пойдет вниз по полному графу.
Ну раздели граф на 4 части, 1/4 сделай полным графом, 3/4 подвесь деревьями с разных сторон, тогда легко сделать чтобы было 300 просмотров полного графа. Как строго доказать? Почему таким образом, мы, например, не можем посчитать расстояние между всеми вершинами меньше чем за N^3.
я не понимаю как 300 просмортров полного графа может быть.
вот наше решение.
массив dist[] — кратчайшее расстояние до вершины i от какой-то уже построенной базы.
массив used[] — плохая ли вершина i или нет.
дальше как пришел запрос — делаем поиск в ширину с обновлениями и при этом ходим только в те вершины, до которых расстояние улчушилось(уменьшилось) и при этом расстояние не превосходит данного в инпуте k.
При таком решении не пойму как 300 раз можно пройти через вершину.
Поиск в ширину посещает всего N вершин, но работает за O(M), т.к. он может просмотреть все ребра, понимаешь разницу? Посетишь ты N, пометишь вершины 100 раз, верно, но кол-во просмотров ребер вроде может быть другим.
Все, понял строгое док-во большое спасибо.
Can someone tell me what is test case 2 on problem H ? I wrote a dp solution, but it keeps giving me WA