Welcome to 2014-2015 CT S02E02: Codeforces Trainings Season 2 Episode 2 (CTU Open 2011 + misc). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!
It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.
Good luck!
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".
Can someone tell me what is test case 2 on problem H ? I wrote a dp solution, but it keeps giving me WA