map's blog

By map, 10 years ago, translation, In English

Hello, Codeforces! I'd like to invite you to Codeforces Round #289 (Div. 2). It'll be held on Saturday, January 31 at 15:00 MSK and as usual Div. 1 participants can take part out of competition.

This round will be carried out according to the ACM rules, which means that you get verdict of your solution on-line, and the duration time is 3 hours.

These differences in the rules are caused by the fact that this round is the second qualifying round for the WCC, which stands for Winter Computer Camp and can be also mentioned as ZKSH. Official school website — hhttp://it-edu.mipt.ru/en/zksh2015. There you can find the selection rules for WCC.

If you are a school student and you want to participate in the selection to WCC here are the steps:

  1. Sign up for the school at http://goo.gl/kz2qSf, if it was not done earlier.
  2. Create a free account at codeforces.com, if it was not done earlier.
  3. Sign up for the round on the link http://codeforces.net/contestRegistration/509. You should put a tick in the box "Do you want to participate in the selection to WCC?", and provide your last name, first name and email, which you entered for registration in the first step.

If you have any questions feel free to write to the address of the organizing committee: [email protected].

The authors of the contest (WCC technical committee) are really grateful to Max Akhmedov (Zlobober) for the help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for contribution to the development of programming by creating systems Codeforces and Polygon.

UPD. Tutorial — http://codeforces.net/blog/entry/16119

Full text and comments »

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

By map, 11 years ago, translation, In English

Hello! Where can I submit the intersection of half-planes in 2D?

Full text and comments »

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

By map, 12 years ago, translation, In English

Hello, I would like to touch the topic of development of good sports programmers. Many wonder how people reach the ACM ICPC finals or, for example, get 2200 + on Codeforces / Topcoder. In this regard, I ask all those, who have something to say on this subject, and in particular the above-stated category of people, answer the following questions:

  1. How much time are you engaged in SP?
  2. What gave the most powerful incentive to it and when?
  3. What resources and archives do you solve? (and how you could characterize them: acm.sgu.ru, acm.timus.ru, codeforces, topcoder, etc.)?
  4. What programming language and environment are you using? (If possible with a short (or complete) commentary)?
  5. How many hours a week do you spend on the SP (including whether your workouts are constant, or they are seasonal and are aimed for successful performance in a particular competition)?
  6. Which way to prepare for a serious personal competitions do you prefer?
  7. What motivated you most during your development, and motivates now?
  8. What are the determining factors for reaching success in SP?

9 *. Additional comments on this topic.

At codeforces.ru there are lots of individual posts, which reflect some points of this theme, but I would like to collect all in one place.

The only adjacent informative blog entry, I know. "

Please do not flood.

Note: Abbreviation "SP" stands for "sports programming."

Full text and comments »

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

By map, 14 years ago, translation, In English

Problem A.

In this task all you had to do was to make sure that the sum of all Σxi is 0, the sum of all Σyi is 0 and that the sum of all Σzi - 0 .
We have not written that condition evidently in order that participants will have a chance to break a solution.

 

Problem B.

In this problem, in fact, you should find a winner at every section. For each section, you must do a full search of all competitors to find a competitor with a minimum section time, which ran that section. Asymptotic of the solution is O(nm).

 

Problem C.

In this task, you had to update the collection of artifacts, which belong to Kostya’s friends, after each purchase . You had to set  a matrix c[i][j] - number of the j-th basic artifact that is required in order to collect the i-th component artifact. Further, one can make a matrix of composite artifacts, where a[i][j] is number of the j-th basic artifact of the i-th friend and a similar matrix b of composite artifacts, and  check whether i-th friend has any a composite artifact of O (MN) after each  i-th friend’s  purchase. Check whether one component of the artifact assembles for O (N): while checking whether the i-th friend is able to collect the j-th artifact you have to check, if there is such u, that c[j [u]> a[i][u], if so, the j-th artefact will not be collected, if not, then you have to increase the b[i][j] and update the values in a[i]).

So.the asymptotics of the processing of all purchases will be O (NQM). Then, we need  to make a list of artifacts for each person, keeping their quantity(a total of O (KN + KM), and sort it (a total of O (QlogQ)).

 

Problem D.

This game is over, because except for a finite number (2) of reflections about the line y = x,the coordinates are changed to non-negative integer (and at least one coordinate is changed to a positive number).

Algorithm for solving this problem  is DFS / BFS (states) where the state is a pair of coordinates, and two logical variables, which denote if the 1 (2) player had reflected a point about the line y = x.

Total number of states is obtained by S <= 4D^2 (pairs of coordinates) * 4 (Boolean variables).

Processing of one state takes O (N) actions (do not forget to try to reflect the point about the line y = x, if the player had not made it earlier in the game). Thereby, we have the overall asymptotic O (ND^2), which works on C + + in less than 200ms.

 

 

Problem E

To solve this problem you have to do a "move" subsegment and know :

 1. The set B of numbers, meeting once, with the function of extracting the maximum for O (logN)

2.The set of numbers appearing on this subsegments with keeping the number of times,that this number is found on this subsegments, with function of verifying how many times the number in this subsegments for O (logN).

 

While moving a segment from (a[i] .. a[i + k - 1]) for 1 item left (a[I + 1] .. a[I + k]) you have to:

1) Check whether a[i] with a[I + k]. If yes, then there is no need to modify the set, otherwise proceed to item 2 and 3.

2) Check how many times we have a[i] in the set A: if 2, then add a[i] to B, if 1, then remove it from  A and B. Do not forget to reduce the corresponding number of occurrences of a[i] in the current segment 1.

3) Check, how many times we have a[I + k] in the set A: if 0, then add a[i] in the B and A, if 1, then remove it from B. Do not forget to increase the corresponding number of occurrences of a[i] the current interval to 1.

 

After that, if the set is not empty, we should take peak from it.

 

So the asymptotics of this process will be O(NlogN).

 

As such data structures  set / map(for those who use C + +) and the Cartesian tree are suitable.

Full text and comments »

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

By map, 14 years ago, translation, In English

Hello!

Today I am the author of all tasks. At the contest you will be asked to help students from Chelyabinsk in solving their non-trivial problems.

I want to thank all those who helped me to prepare the round: Anton Garder for his invaluable assistance in the preparation of sets of tasks, Demid Kucherenko for assistance in the preparation of conditions, Artem Rakhov for coordinating the activities and patience J, Maria Belova for translating and  Mike Mirzayanov for a great system.

 Good luck!

Winner - Solo

Analysis - http://codeforces.net/blog/entry/1571

Full text and comments »

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