teja349's blog

comp.exe contest on Codechef
By teja349, history, 7 years ago, In English

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.

  • Vote: I like it
  • +61
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like 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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why can't I submit as practice?!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The problems are added to practice.You can submit them now.

    → Reply