### Erfan.aa's blog

By Erfan.aa, 5 years ago, , ### 459A - Pashmak and Garden

Four vertices of a square with side length a (and sides parallel to coordinate axis) are in this form: (x0, y0), (x0 + a, y0), (x0, y0 + a), (x0 + a, y0 + a).

Two vertices are given, calculate the two others (and check the ranges).

Total complexity : O(1)

Sample solution: 7495194

### 459B - Pashmak and Flowers

If all numbers are equal then answer will be n * (n - 1) / 2, otherwise the answer will be cnt1 * cnt2, where cnt1 is the number of our maximum elements and cnt2 is the number of our minimum elements.

Total complexity : O(n)

Sample solution: 7495202

### 459C - Pashmak and Buses

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 kd different sequence at all, so if n > kd, 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 ≤ kd, 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.

Total complexity : O(n * d)

Sample solutions: 7495236

### 459D - Pashmak and Parmida's problem

First of all, we can map the given numbers to integers of range [1, 106]. Let li be f(1, i, ai) and let ri be f(i, n, ai), we want to find the number of pairs (i, j) such that i < j and li > rj. For computing lis, 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, li would be equal to cnt[ai] at position i (ri s can be computed in a similar way).

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 li to answer and add ri to the Fenwick tree.

Total complexity : O(n * logn)

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.

Sample solutions: 7495225 7495225

### 459E - Pashmak and Graph

In this problem, a directed graph is given and we have to find the length of a longest strictly-increasing trail in it.

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.

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.

Total complexity : O(n + m * logm)

Sample solution: 7495216 Tutorial of Codeforces Round #261 (Div. 2)  Comments (36)
 » Thanks for the fast editorial!
•  » » We're sorry. Some unexpected events caused that.
 » Can you please include judge's code that will be great.
•  » » Included. ;)
 » i donot understand the E's solution cannot u explain in more details ??
 » 5 years ago, # | ← Rev. 2 →   in problem c it think it will be k^d not d^k
 » thanks for nice editorial.
 » How can you get the n * (n - 1) / 2 formula in B (otherwise than by wolfram alpha)?
•  » » This formula is the number of unique pairs you can form with n given elements.Each element can be paired with n - 1 elements, and there are n total elements. If we multiply we get n(n - 1), but we must note that we've counted all pairs twice, so we must divide this number by 2 in order to get the right amount.
•  » » » Got it, thanks!
•  » » If all numbers are equal then we have to choose 2 numbers from total n numbers. Then there are total nc2 = n!/((n-2)!*2!) = n*(n-1)/2 ways.
•  » » you can't step in programmnig contests without this trivial knowledge :)
 » The solution of C(Pashmak and Buses) was awesome. Thanks a lot!!
 » I solved E with the same algorithm I get wrong answer in test 5 and don't know what's wrong ! this is my submission http://codeforces.com/contest/459/submission/7507479
•  » » Here is it. Look at /* That for-loop was modified */.
•  » » » I got it, Thanks :)
 » Can anyone explain how to solve problem D using divide and conquer. I think the idea used in this problem is similar to finding the number of inversions in an array using divide and conquer.But, I am not getting how to solve it exactly..
•  » » I can.In order to avoid using of data structures firstly compress all the numbers. Then you should calulate pref[i] = f(1, i, a[i]) and suf[i] = f(i, n, a[i]) for all i. Then you should simultaneously use merge-sort for pref and suf. And then you can do the same algorithm as for inversions by merging not prefl and prefr or sufl and sufr but prefl and sufr.I'll provide a code for this later.
•  » » » And here it is: 7516132
•  » » » Wherever you don't need to do the entire merge sort you have already two components you just need to sort them apart and focus only on the step of merging them .
 » can anyone please tell me where my solution is lagging to the problem 5. Help is appreciated. Thanks. http://codeforces.com/contest/459/submission/7556964
 » in problem C,can someone please explain what the author means by "n d-digits numbers in k-based numbers."??
•  » » n d-digits numbers basically means first n decimal based numbers and you need to represent those n numbers in the k-based numbers.For example, n=6, k=2, d=3first 6 numbers are 0,1,2,3,4,5. And in the 2-based number system(binary) 000, 001, 010, 011, 100, 101. And we get 6 different sequences as described in the editorial. As the bus number starts with 1 we need to add 1 to each digit of the number. So the numbers in k-based or sequences now become 111,112,121,122,211,212.Hope this helps. My solution
•  » » » thanks that was awesome
•  » » » can you please explain your code for generating the sequence, i don't understand it
 » 4 years ago, # | ← Rev. 2 →   http://codeforces.com/contest/459/submission/11762173 can someone help me with optimizations.used the divide and conquer technique. my code is getting tle. thanks :) ShayanH
 » For problem:D..just use fenwick tree to solve it. its fun to solve it with fenwick tree :-) my submission :- 17314867
 » unable to figure out problem A! Anybody help plz?? I am weak to figure out co-ordinate problems!
 » 4 years ago, # | ← Rev. 2 →   In problem C , Can anyone explain what does 'sequence of d elements from 1 to k' means in the editorial and how did we arrive to k^d , also how the pigeonhole principle is helping us here? Thanks. EDIT :- I solved the problem. Nice Editorial and Nice problem, I got it now. Thanks anyways.
•  » » each student can take k buses. for d students the number bus arrangements is k*k*k*....*k(till d) so k^d.
•  » » Each student can choose from k buses each day, so for each student there are k^d options to choose from for d days. Now there are total n students and we have to distribute these k^d options among them, if n>k^d, then at least two students will get exactly the same sequence for d days
 » Could someone please illustrate this part: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 kd different sequence at all,
 » Merge sort tree is getting MLE??Could someone tell me how to tackle this.My code : http://codeforces.com/contest/459/submission/36654409
 » Really good contest, with innovative problems. Here are all my solutions to the problems of this contest. I liked C, especially the Pigeonhole Principle and I liked D for the data structures. I wrote an editorial on it here.
 » How to solve Problem E using BFS/DFS? Can anyone explain me please?
 » In problem D, what does Fenwick tree store? and how is this tree used to find the answer?