Добро пожаловать на 2013-2014 CT S01E04: 2013 Kashan Contest + Some Problems of 2009 Google Code Jam World Finals (GCJ WF 2009). Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.
Основной набор задач на тренировку предоставил mohammadrdeh. Спасибо, большая помощь! Берите пример.
Удачи!
I think, that solutions in the Gym section should be opened for everyone. In my humble opinion Codeforces is the best community of programmers, mostly because you can learn from others.
^Very True.I also think that the solution should be opened for all to see and learn new techniques.Please see if this can be done.
I agree with you! It will be very useful for many programmers, if the solutions of all participants will be available after you've finished the contest.
I don't agree, some people just spoil the rank list by virtual participating and submitting solutions in less than 1 minute. Moreover there are thousand of problems in Codeforces all with category and solution and editorial, I think that's enough for practicing.
I mean that solutions will be available after you have written a contest "online" or "virtual", that is, when Resolving. How you know "Resolving" does not affect to the rating.
But the solutions can be found easily online anyways. It's not a rated contest, so why does it matter?
I think soooo
nice problem setter
Hello everyone,
It's my first time participating in a training competition of codeforces and I would like to ask if the results afect the contestants rating.
Thank you very much for reading my question and I would like to wish everyone good luck to the upcoming event!!!
Have a nice competition, Adamos2468
Gym contests are unrated.
I hope you all enjoyed our problems. Also I want to thank my teammates, Alisafe and leviathan. Without their help I could not be able to prepare this problemset.
Thanks a lot for you and your teammates! It was really good contest — well-prepared and interesting. Also I'm sure it is right policy to share contests with community.
Hope, it could be a good tradition to use local contests for public trainings.
How to solve problem G and K and also L ?
K
Since P = product of primes, it can have at most 2^7 divisors (when P = 2*3*5*7*...). Thus you can do dynamic programming with state (how many number used, divisor of P).
G
It is data structure problem. You need to maintain which person is standing and how many pairs using some data structure. It's quite hard to explain in words. You can see code of ntu_tst_004
what about L ?
In Gym, you cannot see others code, without solving them . :( can you send me your code to my inbox. :)
-
hello! can you explain the problem K please!!
L: let's generate graph of alphabet by edges from input. It's obvious that this graph is some numbers of cycles. Let's look on first character of our text, call this character s0. We must change it to lexicography best character. Let we change it to some other symbol — obvious that this symbol must be the best lexicography symbol in cycle which contain s0. Let this symbol is placed d0 symbols after s0. Than X = l0*k0 + d0, where l0 — the length of cycle which contain s0, k0 — some number.
Let's look on i-th possition. Tryed to place different d[i], we must choose such that system of equations l[i]*k[i] + d[i] solvable and this d[i] best lexicography. How to check if solvable? Prefix of system of equations [1..i-1] solvable, we must check that last i perhaps for first [1..i-1]. Check it: solve this system l[j]*k[j] + d[j] = l[i]*k[i] + d[i], it's diophantine equations.
I hope that you understand our solution:)
hello everyone
one asked where I find the problems of this gym for submit again?? please!
How to solve problems D,E? Is E solvable in doubles?
the problem E require more precision geometry
the problem D is MST can you use kruskal o prim !!
http://codeforces.net/gym/100236/submission/4642949 — why this idea is wrong?
I dont see these code
can you explain your idea I dont understand your code
First, let's sort edges in decreasing weight order. IF edge connects vertices in different connected components. Then we take all edges with weight <=c and look if it connects vertices in same connected component. if they vertices are in same component, we take two components with the least(or biggest) rank in DSU and unite them. And in the final part we unite all componentsnot connected with the first vertex and pay c for this.
good first make sort in decreasing weight order. then run kruskal
now know how many road missing now check the road no used in kruskal y with weigth <= c and add is all
in order increasiing the last part
I very humbly request codeforces to open solutions of gym for public. If they do not want to open the submissions for all, then please give us a good logical difference between gym contests and regular codeforces contest policy of submissions.
It would be really helpful if we would be able to see the solutions.
If they open solutions, standings will be spoiled by solutions with less than 1 minute. I know that some people aren't bothered with that stuff, but some ARE.
This logic applies for the codeforces Div1, Div2 rounds too, Does the static standing matters. How can you stop somebody from submitting the solutions if they are available for learning, they might as well use direct solutions or might tweak them, I can not think of a reason to do so.
Your logic makes no sense. I could very easily obtain all the solutions and then create a new account and do the thing you said.
You would like to hamper the learning progress of people in order to keep your ego intact, surely a good logical approach.
Any Hints for ProblemC — Combiantion Locks?? I tried an approach using bitmasking, but was unable to decide among many states which to keep and which to reject??
Try to enumerate answers for little sizes. Then you will seen some interesting things with sum of elements)
Thanks for your hint.Do you konw how to prove the result?
Honestly, I don't know(((
Расскажите кто-нибудь, пожалуйста, как решать H, I, J, M!
Since there don't seem to be any official test data / judges' solutions available for this one, I guess I'll write an editorial. Just hold on!
Как решать J?
Будем рассматривать диапазон мест как отрезки. Задача сводится к тому, чтобы найти наибольшее количество не пересекающихся отрезков на окружности.
Наблюдение: Если есть отрезки которые полностью содержат другие отрезки, то их можно выбросить и больше не рассматривать. Так как если есть оптимальный ответ, который содержит какой-нибудь подобный отрезок, то его можно заменить на более мелкий(который содержится в нем), от этого хуже не станет.
Утверждение: если мы знаем про какой-либо отрезок, что он содержится в оптимальном ответе, то набор отрезков, которые входят в этот ответ можно набирать жадно, начиная с текущей по часовой стрелке.
Алгоритм: перебирать все отрезки, а потом начиная с них запускать жадный алгоритм, может не уложиться по времени. Поэтому можно заметить, что нам можно жадно брать сразу кучу отрезков, а не один, пока хватает длины окружности. Для каждого отрезка сохраним какая длина нам нужна если мы возьмем жадно
2^k(для каждогоk) отрезков начиная с текущей. Теперь мы можем для каждого отрезка за логарифмическое время найти максимальное количество отрезков, которые мы можем взять (прыжками по степеням двойки, подобно алгоритму нахождения lca двоичным подъемом).Еще можно так решать (доказывать решение не умею):
развернем 2 цикла отрезков, т.е. возьмем помимо отрезка [L, R] еще и отрезок [L+M, R+M]. Для нового набора отрезков решим задачу жадно. Теперь пройдемся двумя указателями по решению, находя лучшее решение, начинающееся с каждого из выбранных отрезков.
wow ,i'm stuck in nostalgia ,i have 20GB pic and movies form this contest in Kashan. thank u mohammadrdeh for ur nice problems.
Is there an analysis for the problemset?
I wrote a partial one. here