Добро пожаловать на 2014-2015 CT S02E01: Codeforces Trainings Season 2 Episode 1 (NEERC 99 + misc). Продолжительность тренировки — 4 часа 30 минут. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!
Удачи!
How many problems are there gonna be?
Haha, I like this pic! The end of evolution of human is programmer :)
There's a lot of funny ones on the Internet:
...
...
This is very true, because purpose of humanity existence is creating AI which can surpass human brain. Just like the purpose of previous evolution was to create human brain. After we create AI which surpasses human brain we will not be needed anymore. We are just a tool in Universe's quest of self-recognition and self-understanding.
Under this paradigm (not mine, loosely citing David Deutsch, if you've heard about him) the picture is very true — it basically gives the full story of human being — from emerging as smart monkey to finish as creator of new artificial life.
If you extrapolate the picture, it would seem like the next stage of evolution(artificially selected) is physically fusing with the machine. Genetic alteration is another possibility.
Whats the Idea of problem G — Highway ?
Minimum spanning tree. O(N2) passes comfortably.
how O(N^2) passes? there are 100000 cities.
There are 10000 cities (104), not 100000 (105).
i should kill myself.
How'd you do an O(N2) MST? Shouldn't it be O(n2 * log(n))?
No, you don't need to use a priority queue on edges with dense graphs. It's even simpler than
.
I still don't get it. I can't think about anything better than O(N3) or O(N2) with O(N2) memory.
It's Jarník-Prim's algorithm, but you keep the shortest distances from the so far constructed MST (from its vertices) to all other vertices in one array. When adding the next vertex, you're picking the one with the cheapest distance and updating the minimum distances to all vertices.
Yeah, that's what I was trying to implement, but I couldn't come up with an implementation without O(n^2) bool adjacency matrix to store if there was an edge between two nodes in the original graph. Turns out that using a set and checking it in O(log(m)) is enough. Final complexity: O(N2 * log(M))
In this case, you implicitly know all but M edges (Euclidean distance) and you can store these M in an adjacency matrix + remember the vertex from which the cheapest edge went to each vertex. See my code.
Damn, so simple... PS: Nice template, lol
Don't use a heap to extract-min, extract-min in linear time using a vector.
Can someone provide a link to solutions or explain how to solve H and G? Thanks!
G: see above
H: sort and greedy, the constraints allow an easy solution in
instead of pure 
.
Why O(104N + NlogN) work ....T_T I thought it should be a O(NlogN) solution...
Why wouldn't it work? N ≤ 1000 and it's slightly easier to code.
N <= 1000 ?... N <= 10000!
No, 1 ≤ K, N ≤ 1000 in my problem statement.
N <= 10000 in the gym... I thought the data must be enhanced...
No, always N ≤ 1000 for me. Are you sure you're looking at the right problem? It's H, Billboards.
Haha, please forgive me ...
Anyway ... I thought there must be a O(nlogn) solution base on voronoi-diagram ...
For problem H
I had an N*(log(20000)^2) solution.
You can sort the intervals by their end points and then for each interval check how many points inside it are already covered ... If the count of already covered points is sufficient(>=k), then do nothing ... else u need to start covering new points inside the interval from its end ... You can use binary search and segment tree to get this algorithm to work quickly.
Plus size S of output to the complexity, which gives a different bound using a simpler simulation of the greedy:
if the coordinates from the input are large, or 
if they're small (which is the case here).
In fact, when you need to print the output, there's no point in using segtrees or whatever.
On problem K, with this testdata
Why is this not valid ?
I think after 3rd tab you will get
aaaaas completition notaaaaaaaa.aww thanks! forget about that one :|
"aaaa" is a prefix of "aaaa" so on step 4 you will get "aaaa" again and not "aaaaaaaa".
When you press tab with "aaaa", you won't get "aaaaaaaa". The string will remain exactly the same ("aaaa").
P.S. Holy shit, why are people typing so fast? :(
Can someone tell the approach for A — Divisibility? Thanks
Simple DP on achievable modulos.
thanks,trying again to solve it
not getting the DP, can u tell? thnx!
What modulos can you achieve using all possible expressions with the first k numbers?
how to form all possible combinations of expressions,iterating would be time consuming.
That's why it's dynamic programming. Think about what I wrote — anyone that knows what DP is should be able to solve it with those hints.
is this possible with simple recursion?
If you mean backtrack, then probably not.
I mean binary recursion on sum +,- next element, exiting from recursion if (sum mod K) equals zero.
Then NO. Definitely not.
can somebody explain the approach of K ... is it trie+dp ??
While you could use trie, there's no need for it. A simple DP using
substr()checks is sufficient.thnx a lot ...
are the prefixes proper or any prefix ... i mean say have already typed "an" and one of my words contain "an" so will my 1 tab be wasted on this .
Read the comments here and you'll find out.
what's the data of the 18th testcase?I got wrong on it.But I can't find any error.
code
Whats wrong with my dp function? Plz help. Thank you,
code
whats wrong with my solution getting TLE. please help. Thank you.
Where do we find editorials for the Training Season2 episode 1. I am new to cf, can anyone help me out with this :| Thanks a lot!
Ask for kind help: for the task F, according to the rules, could we uniquely determine the output of the dictionary? (as the description does not give detailed explanation, while "sample input and output" instead.)
tourist is unbeatable. No matter if we start individually or as a team.
Why can't I see code from others people?
Because it's training competition. You can't see code of any problem from other participants, if you haven't solved this problem yourself.
Now it makes sense, thank you
Жалко что разбора нету. А его вообще кто нибудь делать будет?
My codes:
A B C D E F G H I J K L
(upd: B and J added)
То что надо, спасибо огромное тебе добрый человек.
Any hint for L?
Sort cows by sum of weight and strength. This is an optimal order.
Please publish the editorials.After trying if unable to solve we are left with no solution but to have a look at editorials.
Same code but choosing Java 7 instead of Java 8 made it pass (well under time limit). What's going on?!
I had AC instead of TLE by switching Java version for two times in official CF Rounds. As for my experience, Java 8 seems to be faster with Objects and standard data structures, while seventh version is better when you work with primitives/recursion.
Can anybody explain statement of task D?
What is the meaning of Ghost Participant ?
Whats the Idea of problem C? "Expression"
Just stacking the same type of expression (using the carry bit of the i least significant bits and the i + 1-st least significant bit) N times. You can see which expression it is from the sample.
How could I see the test cases?
Solve the problem, then you'll be able to. Sometimes.
I was wrong on test 9 of prob d, can I see the test case then? Thanks!
Solve the problem, then you'll be able to. Sometimes.
(Also, I can't see the tests now. That's why I'm saying "sometimes".)