Erfan.aa's blog

Codeforces Round #261 Editorial
By Erfan.aa, 9 years ago, In English

459A - Пашмак и сад

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 - Пашмак и цветы

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 - Пашмак и автобусы

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 - Задача Пашмака и Пармиды

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 - Пашмак и граф

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

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

Comments Comments (55)
| Write comment?
»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Thanks for the fast editorial!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We're sorry. Some unexpected events caused that.

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can you please include judge's code that will be great.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i donot understand the E's solution cannot u explain in more details ??

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem c it think it will be k^d not d^k

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for nice editorial.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can you get the n * (n - 1) / 2 formula in B (otherwise than by wolfram alpha)?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    you can't step in programmnig contests without this trivial knowledge :)

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The solution of C(Pashmak and Buses) was awesome. Thanks a lot!!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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..

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      And here it is: 7516132

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was able to get an AC using ordered set but on using merge sort tree i am getting tle. Is it becuase the time complexity for using it is O(n*logn*logn) ??

        Thanks in advance.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C,can someone please explain what the author means by "n d-digits numbers in k-based numbers."??

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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=3

    first 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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem:D..just use fenwick tree to solve it. its fun to solve it with fenwick tree :-) my submission :- 17314867

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its fun but I am not able to understand why were doing what were doing. I mean I understand why this works but I cant still explain to myself. Can you explain me please?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i can try problem basically translates to finding all pairs such that

      1) i < j 2) number of a[i] from 1 to i > number of a[j] from j to n

      let count[a[i]] — count of a[i] from 1 to i

      for all i we will add to fenwick tree count[a[i]]

      now we will again iterate from beginning and keep on removing count[a[i]]

      what does my fenwick tree have at any i?

      for each "value" number of times that "value" can be obtained "value" is the count of some element from i + 1 to n

      now a simple query of count[a[i]] — 1 shall give me how many js are there such that count[a[j]] from i + 1 to n is lesser than count[a[i]] from 1 to i

      https://codeforces.com/contest/459/submission/85599666

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i am still not getting i have read your explanation 3 times...and i also know fenwik tree but still not getting...can you give some more explanation..?

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i didn't understand your last two liness for each "value" number of times that "value" can be obtained "value" is the count of some element from i + 1 to n

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
                  for (int i = 1; i <= n; ++i)
	{
		f.update(totcnt[a[i]], -1);
		totcnt[a[i]]--;
		forwdcnt[a[i]]++;
		ans += f.query(forwdcnt[a[i]] - 1);
	}

          do u undertsand this part? i realised this part can explain more than my stupid english

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But fenwik tree is used to answer subarray sum queries ?? why are we using it here and please can you can just tell what is totcnt and forwdcnt ??

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              fenwik tree gives me sum from 0 to R if i query on R i.e. prefix sum

              forwdcnt stores

              =>count of elements from 1 to i

              =>that have been seen upto i

              totcnt will store

              =>initially count for all elements in the entire array

              =>then as we iterate through the array we decrement the totcnt

              e.g. if my array is 1 1 1

              intitally forwdcnt[1] = 0 and totcnt[1] = 3

              after i = 1: forwdcnt[1] = 1 and totcnt[1] = 2

              after i = 2: forwrdcnt[1] = 2 and totcnt[1] = 1

              and so on

              https://codeforces.com/contest/459/submission/85599666 i think the code is easy and try tracing an example throught this code maybe??

              → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can you tell me the values of totcnt && forwdcntfor this test case(given in question)

            7
1 2 1 1 2 2 1
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              before loop totcnt[2] = 3 forwdcnt[2] = 0

              totcnt[1] = 4 forwdcnt[1] = 0

              after loop begins

              i   totcnt  forwdcnt

1   1: 3    1: 1
  
    2: 3    2: 0

2   1: 3    1: 1
    
    2: 2    2: 1

              and so on

              → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Merge sort tree is getting MLE??Could someone tell me how to tackle this.My code : http://codeforces.com/contest/459/submission/36654409

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why cant we use PBDS was problem D? it is giving me runtime error.. Can anyone explain me why ? Link to my solution- Your text to link here...

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    could you identify the error?

    i had encountered a similar problem on using PBDS but there memory constraints were given less clearly there it was 28 MB https://codeforces.com/contest/1354/problem/D here though that isnt the problem...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use Fenwick tree instead

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i did it by FWT just asking why this didnt work :)

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It requires much more of memory to work .. It have multiple points..Memory limit was given for the same

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of a simple solution using multiset first but it got TLE. Then I learnt about PBDS from gfg and used unordered_map in my code and it got AC.However, the same program with map got TLE. I am really not sure what's happening inside as I need to read how the data structure works but anyways, you can see my solution if it helps.

    My solution: 100429402

    Idea: I created the ordered_set of pairs by iterating backwards (from last index) in the array taking count of i-th element and the element as pair. Now I start iterating from 0th index and remove the current element and its count from the set and find the number of elements less than current count of i-th element using order_of_key.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      TLE'd because tight constraints? N <= 10**6

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For solution 100425668, it was not possible to pass since it was taking too much time as multiset does not provide an efficient solution for finding index of element. But, for the solution 100429256 and 100429402, you can see there is no difference other than map and unordered map. So, I think it was the map which was taking the extra time to keep its keys sorted. So, when I used unordered_map, I got AC. But still it took a lot of time(around 2.5s). I guess Fenwick Trees can give better solution.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, what if we're asked unique vertices (No, I am not curious, I interpreted the question wrongly, thought about it around 3 hours, then realized I had read the question wrongly).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E when the edges are undirected?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried D with seg tree, got a TLE at tc 9, any help would be appreciated

My submission

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D could be done even by persistent segment tree

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why in C using first n d-digits numbers in k-based numbers is right?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'll try to explain.

    Let us define each student's bus information(required answer) for all the d days in array info of size d where info[i] = bus that this particular student took in ith day

    Observation -> For two students to be friends this info array of both the students should be the same.

    Now we can form at max k^d combinations of busses and take n combinations from this set and assign each to a student so that there are no friends.

    So it's not necessary to take first n d-digits numbers in k-based numbers, rather we have to take n distinct d-digit numbers in k-based numbers

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

In problem C, Can someone please explain or give some references to why the code for generating first n d-digit permutations in the editorial generates the required permutations.

for (int i = 1; i < n; i ++) {
        for (int j = 0; j < d; j ++) ans[i][j] = ans[i - 1][j];
        for (int j = d - 1; j >= 0; j --){
            ans[i][j] = (ans[i][j] + 1) % k;
            if (ans[i][j]) break;
        }
    }

Thanks in advance.

→ Reply