codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

459.md (3847B)


      1 Source: https://codeforces.com/blog/entry/13430
      2 
      3 ### [459A - Pashmak and Garden](/contest/459/problem/A "Codeforces Round 261 (Div. 2)")
      4 
      5 Four vertices of a square with side length *a* (and sides parallel to coordinate axis) are in this form: (*x*0, *y*0), (*x*0 + *a*, *y*0), (*x*0, *y*0 + *a*), (*x*0 + *a*, *y*0 + *a*).
      6 
      7 Two vertices are given, calculate the two others (and check the ranges).
      8 
      9 Total complexity : *O*(1)
     10 
     11 Sample solution: [7495194](//codeforces.com/contest/459/submission/7495194)
     12 
     13 ### [459B - Pashmak and Flowers](/contest/459/problem/B "Codeforces Round 261 (Div. 2)")
     14 
     15 If all numbers are equal then answer will be *n* * (*n* - 1) / 2, otherwise the answer will be *cnt*1 * *cnt*2, where *cnt*1 is the number of our maximum elements and *cnt*2 is the number of our minimum elements.
     16 
     17 Total complexity : *O*(*n*)
     18 
     19 Sample solution: [7495202](//codeforces.com/contest/459/submission/7495202)
     20 
     21 ### [459C - Pashmak and Buses](/contest/459/problem/C "Codeforces Round 261 (Div. 2)")
     22 
     23 For each student consider a sequence of *d* elements from 1 to *k* that shows the bus number which is taken by this student on each day. Obviously, there are *k**d* different sequence at all, so if *n* > *k**d*, pigeonhole principle indicates that at least two of this sequences will be equal, so that two students will become close friends and no solutions exist. But if *n* ≤ *k**d*, then we can assign a unique sequence to each student and compute the answer. For computing that, we can find the first *n* *d*-digits numbers in *k*-based numbers.
     24 
     25 Total complexity : *O*(*n* * *d*)
     26 
     27 Sample solutions: [7495236](//codeforces.com/contest/459/submission/7495236)
     28 
     29 ### [459D - Pashmak and Parmida's problem](/contest/459/problem/D "Codeforces Round 261 (Div. 2)")
     30 
     31 First of all, we can map the given numbers to integers of range [1, 106]. Let *l**i* be *f*(1, *i*, *a**i*) and let *r**i* be *f*(*i*, *n*, *a**i*), we want to find the number of pairs (*i*, *j*) such that *i* < *j* and *l**i* > *r**j*. For computing *l**i*s, we can store an array named *cnt* to show the number of occurence of any *i* with *cnt*[*i*]. To do this, we can iterate from left to right and update *cnt*[*i*]s; also, *l**i* would be equal to *cnt*[*a**i*] at position *i* (*r**i* s can be computed in a similar way).
     32 
     33 Beside that, we get help from binary-indexed trees. We use a Fenwick tree and iterate from right to left. In each state, we add the number of elements less than *l**i* to answer and add *r**i* to the Fenwick tree.
     34 
     35 Total complexity : *O*(*n* * *logn*)
     36 
     37 Also we can solve this problem using divide and conquer method. You can see the second sample solution to find out how to do this exactly.
     38 
     39 Sample solutions: [7495225](//codeforces.com/contest/459/submission/7495214) [7495225](//codeforces.com/contest/459/submission/7495239)
     40 
     41 ### [459E - Pashmak and Graph](/contest/459/problem/E "Codeforces Round 261 (Div. 2)")
     42 
     43 In this problem, a directed graph is given and we have to find the length of a *longest strictly-increasing trail* in it.
     44 
     45 First of all consider a graph with *n* vertices and no edges, then just sort the given edges by their weights (non-decreasingly) and add them to the graph one by one.
     46 
     47 Let *dp*[*v*] be the length of a longest *increasing trail* which ends in the vertex *v*. In the mentioned method, when you're adding a directed edge *xy* to the graph, set *dp*[*y*] value to *max*(*dp*[*y*], *dp*[*x*] + 1) (because of trails which ends in *y* and use this edge). You need to take care of the situation of being some edges with equal weights; for this job we can add all edges of the same weights simultaneously.
     48 
     49 Total complexity : *O*(*n* + *m* * *logm*)
     50 
     51 Sample solution: [7495216](//codeforces.com/contest/459/submission/7495216)