We gladly invite all the programmers around the world to take part in the Pool C contests of "IPC ACM ICPC PREPARATORY SERIES"
This is a team contest (upto 3 participants in a team) of 5 hours each with ACM ICPC rules, organized on CodeChef.
You can read more about the contests, schedule, event format and rules from the previous blog post and website.
The Schedule of the Pool C contests is as follows :
| Contest by | Date and Time |
|---|---|
| Team apqAW2 | 28th Feb, 20:00 (IST) |
| Team Akatsuki | 6th Mar, 20:00 (IST) |
| Team Apocalypse | 9th Mar, 20:00 (IST) |
You can register for the contest at https://www.codechef.com/teams/register/IPC15P3A
Eligibility Criteria
The IPC programming series, though aimed at ACM ICPC aspirants, is not limited to them. Anyone who wants to try their hand at the problems from some of the finest programming minds in India can do so. Yes! It is open to all the programming enthusiasts across the globe.
Update The second contest of pool C by team Akatsuki has just started! Happy Coding!
Update 2 The third contest of this pool is going to start in less than half an hour! Get your coding shoes on!
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
Why are the editorials not published for previous contests ??? Contest is not enough , if we dont learn something.
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
Editorial to a couple of problems in Pool C , contest — 2
ASYA1
ASYA3
When will the editorials to the rest of the problems be published?
Can you provide me the link to the editorial for the previous contest? I am unable to get it.
Can someone explain the solution of this problem: https://www.codechef.com/IPC15P3B/problems/FIBEQN using matrix exponentiation.
These contests are completely of no use if editorials are not provided.
It's codechef,you shouldn't expect anything . No editorials for feb long challenge let alone these contests.
Wrong. You guys have a terrible habit of needing a crutch of an editorial all the time. Put some brains into the problem until the editorial is published(if at all), maybe you'll find something interesting on your own without editorial's help, and that'll make you very happy. Try some more.
I wouldn't call reading editorials "a terrible habit" :)
P.S. vkditya0997, at least you can read codes by other contestants :) Understanding solution by reading a code is also a useful skill.
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
editorials please
How to solve ARRGM and MSDBIN?
ARRGM: Regard each position contains A[i] stones, then each stone either moves to position 2*i, 3*i or 5*i. It's easy to use grundy. MSDBIN: Construct Aho-Corasick for n numbers (represent each number as a string in decimal). Then dp on this tree.
Can someone explain PRMAX
Min-Cost Max Flow : Consider all types and all profits as a vertex. There are only two conditions :
1) No of items of a type can't be more than M[i] , so add an edge from source to vertex of ith type with capacity = M[i] and cost = 0.
2) No two item can have same price , so add an edge from vertex of profit P to target , with capacity 1 and cost = -P.
At last if we have an item of type x and profit y , then add an edge from type x vertex to profit y vertex with capacity 1 and cost 0. Find min-cost max flow of graph , that is the ans.
Many have extra N(given in the question) vertices apart from all types and profits. Are those needed? They have used them between each type and profit.That is if the ith entry is tp[i] and p[i] then for the vertices corresponding to these two entries, (say they are u and v) there is a vertex connecting them (say x). So source connects to u(for type), u connects to x, and x connects to v(for profit).
I have got AC on the question without using any extra vertices , other than those mentioned in the above comment.So according to me those are not needed.
My solution
Make an array of vectors V[N] where V[i] stores all the types which give profit i.
Now traverse the vector from MaxP to 1
While traversing the ith vector , if there is any type 'x' which is used less than M[x] times , then assign it to this profit
If there is no type left which is used less than M[x] , then for all the types present in this vector , see if there is any previous type which this can be swapped with.
basically if we want to assign 'X' to profit 'I' but X is already used M[X] times but 'X' was used before for profit 'J' which also had some other type say 'Y' which is used less than M[Y] times , then assign 'Y' to profit 'J' and bring 'X' here.
For more clarity you can look at the code
The idea is kind of similar to the working of ford fulkerson algorithm for finding max flow.
How to solve DLHP
We need to use dominator tree . I will be publishing the editorial in a while. Sorry for the delay !