Hello Codeforces Community!
IIITD invites you to Procon 2015, the annual programming contest conducted as a part of our technical fest. We, the problem setters have tried our best to make problems of varying difficulty levels so that there is something interesting for every participant.
Time: The contest will be held on 8th August, 18:00 IST. See the time in your timezone here: link
Contest Details: The contest will be held on the codechef platform here: link
Problem Setting and Testing Team: Ashish Khatkar (ashish1610), Mohit Wadhwa (lifecodemohit), Ambar Pal (AmbarPal), Priyanshu Singh (tgamerz), Anmol Singh (kzanmos), Gaurav Rathee (garyclay08).
Special thanks to Kshitij Jain (kshitij_jain) and Rohan Garg (rohangarg) for their guidance and reviewing the problems.
Prizes: Only for Indian students
Cash prizes: INR 15000
Total Prizes: INR 25000
Hope to see a lot of participation!
UPD: Reminder, contest starts in less than 1.5 hrs.
UPD: Contest has already started less than 2 hrs to go.
UPD: Contest is over. Editorials will be published soon.
UPD: Editorials for all problems except Graph Sum is published. You can find them here
UPD: Editorial for Graph Sum is added.
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).
Colorful problem setters!
Why prizes only for Indian students?
Maybe because the contest is being organized by the programming club of the university which is completely run by students and thus it would be hard and expensive for the students to send the prizes to international competitors.
The intention of the contest is to promote programming among Indian Students :)
... so how long is it?
We are getting the discrepancy corrected. Contest duration is 2.5 hours.
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).
Nice problemset, I enjoyed it :)
Thanks :)
The problems didn't all load at the same time for me and I've never used codechef before so I got confused and just clicked the first problem I saw... so I ended up solving Code Land before I realised there were 4 easier problems. I regret everything.
We are sorry for the goofup. The problems were getting synced thats why there were only 4 problems initially.
I hope you liked the problem set.
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).
Doesnt this question " https://www.codechef.com/COOK35/problems/TYTACTIC " look a lot similar ?
I can assure you that we did not see this problem earlier. We'll look into this.
I had no solution in mind , so I tried to google for some hints. "update vertex sum of subtree" is the query that landed me this question and it's tagged editorial ( but I didn't copy and avoided this question :P )
There are a lot of problems with update element sum subtree or update subtree sum subtree:) What was really the important idea was the exponentiation and to reduce it to matrix of 2x2. I got tle first because I didn't see that m=2*sutm_of_1_and_2
But of course there are similar problems. It is almost impossible to come up with an original query problem. I have given a problem with updating tree vertex values and calculating subtree sums myself before, just as there are tons of different problems about sums/minimums/maximums/different numbers queries.
In my opinion the interesting and original part of the problem was to generate the last 5 digits of the N-th fibonacci number quickly :)
How to solve Code Land Problem?
Editorials are up.
Code (AC) : http://ideone.com/Mfu9PK
In my opinion Code Land was significantly easier than Range Queries. Perhaps I'm missing some easy solution of Range Queries?
I solved it using Mo's algorithm, however did not come up with solution for Code Land problem. What was your approach for it?
Thought of sqrt decomp for range queries but no ideea... Waiting for editorial to see new ideas with mo's algorithm :)
Hello, BAM! Good to see you ;) In Romania, "Mo's algorithm" is the RangeMode "smen". You just solve the queryes offline sorting by some points which are marked from sqrt to sqrt(the most left one). In case of the same point, you sort by the right limit. In this way it is very easy to process the queryes using a Fenwick Tree. Read the solution to that problem, maybe it will shed some light, bro.
I used the same algorithm for Range Queries. For Code Land my approach was as follows:
We'll be aiming for O(N2) complexity per test so it's fine to generate the costs of each edge using the function provided. Then it is clear that we'll be removing some critical edge, so let's build the DFS-Tree. We can in O(N) find all critical edges and mark them as critical (though finding them in O(N2) is fine too).
Now let's take some edge A - B and say that this will be the edge we'll add after removing some other. Imagine the DFS-Tree and vertices A and B in the tree. The edge we'll have to remove is some critical edge along the path from A to B in the tree. Out of all critical edges along that path, it makes sense to remove the one with the minimum cost.
There are O(N2) paths in the DFS-Tree so we can precompute the cheapest critical edge along each path. Afterwards we can simply try all O(N2) edges as the "add" edge and in O(1) find which edge we'll have to remove.
All the steps are very easy to implement in O(N2), so I was surprised to see so few people that managed to solve the problem :)
Note : By DFS-Tree I mean the tree formed by the edges chosen by DFS traversal. Of course this is just a random spanning tree of the graph.
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).
Can "range queries" be solved in anything faster than n*logn*sqrt(n)? (n*logn or n*sqrt(n))
Auto comment: topic has been updated by ashish1610 (previous revision, new revision, compare).