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

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

Hello CodeForces Community!

I on behalf of my team — Akatsuki would like to invite you all to the first contest of the final season of IPC’s ICPC Preparatory Series. The contest is open to all those who have been shortlisted in the previous rounds. On top of this, we will be hosting a mirror contest with an hour delay in parallel to this. I hope it would serve as a good preparatory ground for all the ACM ICPC aspirants who are preparing for upcoming regionals.

Joining me in the problem setting panel, we have: sarveshmahajan (Sarvesh Mahajan), aditya1495 (Aditya Shah), deathsurgeon (Rupesh Maity), pakhandi (Asim Krishna Prasad).

Contest details Time: 25th September 2016 (2000 hrs) to 26th September 2016 (0100 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone. Contest link: https://www.codechef.com/IPC15FLA Mirror Contest details: Link: https://www.codechef.com/IPC15AMR Date: Sunday, 25th September 2016, 9:00 PM, IST. Check your timezone. Duration: 5 hrs. Note: This contest is open for the whole community.

Prizes: Cash prizes for the top three spots are declared after taking into consideration of the cumulative score (of the final 3 contests):

Global Category:

1st Prize: $1000

2nd Prize: $500

3rd Prize: $200

Indian Category:

1st Prize: INR 50,000

2nd Prize: INR 25,000

3rd Prize: INR 10,000

More details about the preparatory series can be found here: https://www.codechef.com/ipc/2015

Good Luck! Hope to see you participating!!

UPD : Editorials

LUFFY ASYA2 TREE02 ASYAPATH BOBPRIME TREEPAL HIKARU

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

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

I can't see the problem statements

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

You are only eligible for this contest if you have been shortlisted from previous 3 contests of IPC. Otherwise you can take part in the mirror of this contest which starts at 9 P.M. IST.

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

I received an invitation but i'm not able to submit. They are saying that i'm blocked. WTF is this, first you invite and then you restrict !

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

We I apologise for 10 mins delay at the begining of the contest.

Editorials will be out in a "few" days. Brief ideas for some problems-

HIKARU — check that sum of degrees is even and max flow. 1-N on left, 1-N on right, edge ij is i xor j capacity. check if the flow can be sum of degrees.

TREEPAL — Palindrome tree. DFS on tree and remove the node corresponding to vertex once the dfs for subtree is done. And also we should not repeat the suffix operations if we see same character children more than once.

LUFFY — Pick a line from (x,y) which doesn't intersect any police. Check if there is a cycle which intersects this line odd number of times. This can be done by assigning the weights of the edges that intersec this line with 1, all others 0 and checking if the graph is bipartite.

BOBPRIME — Inclusion, Exclusion. Use mobius values to calculate f(x,k) which is count of numbers <= x and have some prime power >=k . Another observation needed is that answer is at most 10^10

ASYAPATH — See comment below.

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

    Why did you make the solutions visible ? xD

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

      I was very sleepy after the round and forgot about the mirror round XD Anyway the mirror round was just for learning purpose, so no issues.

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

    In HIKARU we thought of the same approach but couldn't come up with a proof so as to why this would ensure that the flow through the edge i-->j and through the edge j-->i in the Bipartite graph would be the same? They should be same because the graph should be undirected (assumption based on problem statement. or else adjacent word would be ambiguous) but how is it ensured in the flow network formulated ?

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

      If the sum of degrees is even, and the max flow is equal to the sum of degrees, then there exists one integral flow. The proof is here

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

    LUFFY can be solved in O(N2).

    First check if the point lies in some circle itself. If it does, answer is "NO". Otherwise continue. This can be done in O(N)

    Now for every pair of circles that intersect, let's call them connected. Now for every connected pair of circles, join their centres using a line segment. If the result is a polygon that encloses the given point, then the answer is "NO", otherwise the answer is "YES".

    To check if the point lies in a polygon, use radial sweep.

    The same problem was in ASC1 | Problem F, with better constraints ( N ≤ 300 ).

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

What is the solutions for Palindrome Tree problem? I used some kind of palindromic tree data structure with O(n) but it got TLE.

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

    Because palindromic tree guarantees O(n) time only in linear strings. During the construction of palindromic tree, when you make transitions over suffix links, to get the suffix link of newly observed palindrome, in total it would be O(n) for a string in general but can go up to O(n2) for the tree. To overcome that, you need to make another transition table for each palindrome that directly points to a suffix link when you see a new character that cannot extend the palindrome. Some contestants passed the TL by using trie (a hack I should have thought of during TC generation :( ), however such a solution might fail.

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

How to Solve BobPrime?

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

    Nice solution: let's learn how to count good numbers  <  = X for some X, after that we can find the answer with binary search. In order to count good numbers for some X, we'll learn how to count numbers  <  = X with degree  >  = Y, and say that amount of numbers with degree exactly Y can be calculated as difference between  >  = Y + 1 and  >  = Y. Now in order to count such numbers we can say that for  >  = 1 all numbers are good (or maybe all except 1 which has degree 0, but it doesn't matter anyway), and for degree  > 1 we may take a look at prime divisors which have degree at least Y and for each possible set of these divisors (as they are at least squared now, we know that their product doesn't exceed sqrt(X), and X is only a few times bigger than 1e9 in worst case, so there are not too many of them to check) calculate in how many ways we can make a number divisible by such set raised to the power Y. In order to not count something multiple times you should apply inclusion-exclusion here.

    "I had a hard day and don't want to think too much, just give me my AC" solution: precompute amount of good numbers below X, 2 * X, 3 * X, ...,  for some X and hardcode it into your solution, now to answer a query find the segment [K * X + 1, (K + 1) * X] which contains the answer and solve it with a sieve in order to find a degree of each number there.

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

      Can you elaborate more on the nice solution please? What is a "prime divisor with degree atleast Y"? Is it PX, where X >  = Y and P is a prime?

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

Great Problems. Please provide an editorial. BTW, How to solve Break Tree and every problem after that?

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

    Break free can be solved using binary search and greedy. Let us binary search on the answer, now we have to find minimum number of edges to be broken to decrease all subtree sizes to less than X. The greedy idea is to DFS the tree, and whenever a sub tree has greater than X weight, remove the edge to the heaviest children. It is easy to see why this works. Complexity is where S = max sum of tree weights(2·1013).

    Code
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

How to solve Diagon Alley? btw testcases of this problem are weak, one AC solution gives WA on:

5 0 5
1 2 3 4 5
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The test cases are indeed really weak. It seems there is no test case where D < dist[N].

    See this submission for proof. The assertion which even fails on sample test 2 does not fail the main cases!

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

      That is because your solution gave WA on the first test case itself. For later test cases, the assertion fails. Check this submission which fails this assertion and this submission which is the exact same without the assertion.

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

      We did add test cases where D < dist[N]. But we missed D == dist[N] :(

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

When will you post the editorials?

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

I couldn't even understand sample cases of "Diagon Alley". Can anyone here explain the sample 1 ? Where does Aseem start from in the Alley ?

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

    Hey wineColoredDays,
    Aseem starts from the entrance and each shop is located at a distance dist[i] from the entrance. Any dependency (a, b) represents that b cannot be visited before visiting a.

    Here's the sample case 1:
    10 3 100
    9 14 16 21 34 45 56 64 75 98
    9 6
    5 2
    5 4

    Here you have to visit all the given shops, which are at distance dist[i]. After you're done visiting all these shops, you have to visit the ending point, that is at a distance 100 from the entrance.
    (9,6),(5,2),(5,3) are dependencies meaning that, shop[6] cant be visited until shop[9] is visited, shop[2] can't be visited until shop[5] is visited and similarly for shops[5] and shop[2].

    The optimal solution here would be:
    Representing shop numbers (1 -> 4 -> 5 -> 3 -> 2 -> 7 -> 8 -> 9 -> 6) and then finally going to the shop at distance 100.
    The total distance travelled in this order is 200.

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

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

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

Can you plesse provide editorial for Diagon Alley?