map's blog

By map, 4 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.ru/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: zksh-team@phystech.edu.

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.com/blog/entry/16119

Read more »

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

By map, 5 years ago, translation, In English,

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

Read more »

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

By map, 6 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."

Read more »

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

By map, 7 years ago, In Russian,

Как научить msvs выводить все warning-и при построении по умолчанию?

Для конкретного проекта это несложно: нужно просто в свойствах проекта.
Либо /wall в компилятор засунуть, либо в прагме написать
#pragma warning(default :4) - http://msdn.microsoft.com/en-us/library/23k5d385(v=vs.100).aspx - не помогает.
Вероятно, нужно просто поменять стандартную конфигурацию debug-а.
Тестить, что все получилось можно строчкой вида "if (a=b){}"

И, пожалуйста, не надо писать, что "вижак - говно" и т.п.

Read more »

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

By map, 7 years ago, In Russian,
В 3 раунде объясните пожалуйста решение задачи В. Вроде просто считать динамику d[k][i][j] - ответ, если нажали К клавиш, и наши пальцы на i, j.

Read more »

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

By map, 7 years ago, In Russian,
  1. http://codeforces.ru/contest/140/submission/1000181 :
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<math.h>
  5. #define esp 1e-8
  6. int n,a,b;
  7. double c,cc;
  8. int main(){
  9.     int m;
  10.     scanf("%d%d%d",&n,&a,&b);
  11.     if (n==1){
  12.         if (a>=b) printf("YES\n");
  13.         else printf("NO\n");
  14.         return 0;
  15.     }
  16.     cc=asin(1.0)*2.0/(double)n;
  17.     c=asin(b/(a-b+0.0));
  18.     if (c<cc+esp) printf("YES\n");
  19.     else printf("NO\n");
  20.     return 0;
  21. }

n = a = b = 5 - при взломе выдало "NO".
c=asin(b/(a-b+0.0));  - довольно странно должно было посчитаться.

Read more »

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

By map, 7 years ago, In Russian,
Стандартно: подскажите пожалуйста, как решать задачу С.
И N.

Read more »

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

By map, 7 years ago, In Russian,
Подскажите пожалуйста, как решать задачу С.

Read more »

 
 
 
 

By map, 8 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.

Read more »

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

By map, 8 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.com/blog/entry/1571

Read more »

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