Блог пользователя adurysk

Автор adurysk, история, 9 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -28 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

editorials please

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve ARRGM and MSDBIN?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain PRMAX

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve DLHP