Hi all,
We Computer Science Department at IIT Madras are hosting the contest comp.exe on Codechef(link) as part of our department fest Exebit.The contest will take place on 11th April,2018 at 21:00 IST.
The problemsetters and testers for the contest are me(teja349) and MegaBidoof. Thanks to TooDifferent for helping us in preparation of the contest.
I personally feel problemset is around Div2 level.There will be 8 problems with ACM type scoring.The contest is team contest (teams of 2).Duration is 120 minutes.
There are prizes worth 6K (only for Indian participants).
Registrations for prizes: Register here before the contest starts to be eligible for prizes. Hope you enjoy the contest!!!Good luck and have fun.
Lets discuss problems after contest (if any).
UPD: Contest starts in less than 1hr.All the best!!!
Thanks for the participation!!
We are sorry that for the question GCD Queries segment tree solutions and sparse solutions could pass. Though we had a solution with complexity of O((q+n)*log(MAX_element)).We leave it for you to try it.
Some Announcements:
The penalty time for wrong submission is reduced to 5 mins from 20 mins.
We strongly recommend to use fastio (for example scanf and printf in C++) in questions which involve huge input.
There is no particular order among questions .They are randomly ordered.
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
can Satisfying Gourments(https://www.codechef.com/COME2018/problems/CEXE05) problem be solved like this : We will build a bipartite graph of 2*n nodes n nodes for each brand and we will add an edge between node i from first brand to node j from second brand if they don't belong to the k pairs of restrictions imposed . Now we need to tell if there exists a perfect matching over this bipartite graph .
Is there any fast matching algorithm which find on a graph of N<=10^6 nodes and also M=Nc2-K edges ? or is there some observation to solve this?
That question is pretty straight forward case of 2-SAT..
So the number of nodes is the same as your graph, i-> brand 1
n+i-> brand 2
If ingredient i of brand 1 cant be with ingredient j of brand 1
Then the equivalent 2-SAT statement is (n+i)OR(n+j) so there will be directed edge from i to n+j and j to n+i.
Then simply run kosaraju algorithm to get SCCs.
If for any i, i and i+n are in the same SCC there is no solution.
You can read more about 2-SAT here
http://mirror.codeforces.com/blog/entry/16205
why can't I submit as practice?!
The problems are added to practice.You can submit them now.