adurysk's blog

ICPC Preparatory Series (Pool C) — Cool Prizes to be won!
By adurysk, history, 9 years ago, In English

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 byDate and Time
Team apqAW228th Feb, 20:00 (IST)
Team Akatsuki6th Mar, 20:00 (IST)
Team Apocalypse9th 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!

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Why are the editorials not published for previous contests ??? Contest is not enough , if we dont learn something.

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Editorial to a couple of problems in Pool C , contest — 2
ASYA1
ASYA3

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

When will the editorials to the rest of the problems be published?

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you provide me the link to the editorial for the previous contest? I am unable to get it.

→ Reply
»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

These contests are completely of no use if editorials are not provided.

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

    It's codechef,you shouldn't expect anything . No editorials for feb long challenge let alone these contests.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

editorials please

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve ARRGM and MSDBIN?

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

    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.

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

Can someone explain PRMAX

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

    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.

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

      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).

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

        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.

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

    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.

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

How to solve DLHP

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

    We need to use dominator tree . I will be publishing the editorial in a while. Sorry for the delay !

    → Reply