Vovuh's blog

By Vovuh, history, 2 weeks ago, In English,

1133A - Middle of the Contest

Idea: MikeMirzayanov

Tutorial
Solution

1133B - Preparation for International Women's Day

Idea: MikeMirzayanov

Tutorial
Solution

1133C - Balanced Team

Idea: MikeMirzayanov

Tutorial
Solution

1133D - Zero Quantity Maximization

Idea: BledDest

Tutorial
Solution

1133E - K Balanced Teams

Idea: MikeMirzayanov

Tutorial
Solution

1133F1 - Spanning Tree with Maximum Degree

Idea: MikeMirzayanov

Tutorial
Solution

1133F2 - Spanning Tree with One Fixed Degree

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it  

»
2 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Explanation of f2 is copy-paste of f1, please fix it

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

F2 tutorial is missing (F1 has been repeated). Also, The problem F1 really should've been ahead of the problem E (if you want to sort the problems according to their difficulties).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Vovuh , F2 tutorial is missing

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can F2 be solved by finding articulation edges / bridges in the graph and as soon as we find bridge edge we merge them and after that we pick any random adjacent edges of vertex 1 so as to make its degree exactly d. and after make the whole tree connected using kruskal type algorithm? Here is my submission for reference of what i am talking. I am getting wrong answer on test 37. Pls tell if i am wrong. Thanks

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    The idea for F2 is that if we remove vertex 1 then the graph will be K components and if K > D there is NO answer otherwise we should connect this K components with D edges after that we can choose any MST of the remaining graph.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    hope this test case will help you to understand why you are getting wa :) 7 8 4 1 2 1 3 1 4 1 5 1 6 1 7 7 6 5 4

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Turns out that my solution for D with maps having long double keys passed. I checked the test cases and would suggest the problem setters to do the same too. From what it appears, the cases seem weird. I've linked a screenshot regarding my concerns.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why does this solution gets TLE whereas this solution gets Accepted?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D. 'numenator' is a typo.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov you Have Mistakenly provide E question tutorial in F question. Can you please explain 1133F2 — Spanning Tree with One Fixed Degree solution idea.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"How to do transitions from dpi,j? The first transition is pretty intuitive: just skip the i-th (0-indexed) student. Then we can set dp[i+1][j+1]:=max(dp[i+1][j+1],dp[i,j])."

i think it should be dp[i+1][j] as by skipping ith student we are not increasing size. MikeMirzayanov

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it's a typo. It should be dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also stumbled upon this, will wait for the clarification of right transition..

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      I'll will put the way I interpreted it.

      When you are in a given state (i , j) (where the students in [1,...,i] are the possible students you can use and 'j' is the maximum quantity of teams you can use) you have to take the best between pick or not the student 'i'.

      When you dont't pick student 'i' you will have to pick the solution for the case in which you have the students in [1,...,(i — 1)] as possible students to take and 'j' as the maximum quantity of teams you can use. This describe exactly what is in the state (i — 1 , j).

      When you pick student 'i' you have to see what is the best way to pick it. So you look at the states when you allow (j — 1) teams as maximum quantity of teams and students in [1,...,z] (with z <= i) as possible students (states of the form (z , j — 1) with z <= i). When you pick a state like that you could create a new team and put the maximum quantity of possible students (which are in [(z + 1),...,i]) in it to get a candidate for the state (i , j). But remember that you want the student 'i' to be in it. So you want to see only states (z , j — 1) (with z <= i) such that you could create a new team and put all students in [(z + 1),...,i] in it.

      With a good care this can be done in O(n*k): 51128813

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will fix F2 tutorial in a few hours. Please wait a bit.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, why we should ensure numerator is non-negative?

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

    We should treat fractions and as the same one.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

@Vovuh How is ur editorial of F2 different from this? . Aren't they same?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2 D, Why does use of unordered_map gives a TLE but normal map works fine ? Solution 51071398 gives TLE with unordered_map but this 51071641 gets Accepted with map

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

    unordered_map has O(1) complexity on average, but input can be engineered so that it take O(n) collisions for each access. Read more about it here.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do problem C using binary search?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the array in ascending order. For every element in the array (let it be arr) find how many elements satisfy  ≥ arri and  ≤ arri + 5. Take maximum length of all such ranges. See this code for the implementation.

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem D we can prevent precision error by using BigDecimal for example in java, the largest fraction is 1000000000 / 999999999 = 1.000000001000000001000000001, the numbers after the 1. well represent the rounding we will use inside the BigDecimal class, 51105537

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In E. Why can't we just simply use two pointers. My idea is to sort this array then use two pointers as below a[n+1] = 2e9; for(int l = 1, r = 1; l <= r && r <= n+1;) { if(a[r] — a[l] <= 5) r++; else{ len[m++] = r-l; l = r; } } sort(len, len+m, greater()); for(int i = 0; i < k; ++i) ans += len[i]; But I get wrong answer on test 25. Can some one help me?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This example can help you: 10 1 11 9 8 7 6 5 5 5 5 5

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone Explain me Problem B solution ? I am not able to understand it.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to count the number of (di, dj) pairs such that di + dj is divisible by k. In other words, (di + dj) % k == 0. If you expand the modulo, you get ((di % k) + (dj % k)) % k == 0. Note here that we don't care about the di and dj values themselves, we only care about di%k and dj%k. Another observation is that for ((di % k) + (dj % k)) % k == 0 to hold true, (di % k) + (dj % k) must equal k. So, for some di, dj%k must be equal to k-(di%k) for (di,dj) to be a valid pair. For example, if k = 3, values whose mod with 3 equals 1 can only pair with values whose mod with 3 equals 2.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please explain

      And for any other remainder i from 1 to ⌊k2⌋ the number of pairs of boxes is min(cnti,cntk−i−1).

      So, if we sum up all these values, the answer is this sum multiplied by two (because we have to print the number of boxes, not pairs).

»
12 days ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

DP in editorial for E is something different from its definition.

In that solution we just skip intermediate students (i, i + cnt_i), but in this case dp[i + z][j + 1] (z = 1 ... cnt_i — 1) is not increased as it should be.

Consider following example: n=3, k=1 a[] = 1 1 1

Then editorial code outputs: dp[i][j]=

0 0 
0 0 
0 0 
0 3

But by definition dp[1][1] = dp[2][1] = 1, because we form one team from these students.

Can someone please explain what dp[i][j] really stands for?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dp(i,j) means are are we considering ith student or not, if we consider ith student number of teams will increase by 1.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can E be solved using divide and conquer after sorting?

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    no the idea of E is that if i take a number i will avoid the binary search on all other numbers which the condition (less than five is met) but what if i didn't take this number and took two of the numbers which i avoided it might produce a better answer that's why you have to try every thing using dynamic programming a simple knapsack will do

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me why this solution got TLE my submission

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone know the name of the algorithm which is used to solve question B.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no algorithm , just logic .

    what i used is the face that (a[i] + a[j] ) % mod = (a[i] % mod + a[j] % mod ) % mod .

    store them in map and count answer for each pairs .

»
10 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

the solution of e is very clever

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why the maximum number of students is possible only when there are exactly k teams as written in the solution for E?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

f2 is missing!

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain in problem D,why we have to make the numerator non-negative and if numerator is zero, why we have to make the denominator non-negative? I am a newbie, Thanks in advance.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution for F1 https://codeforces.com/contest/1133/submission/51458164 is giving correct output on my computer but I am getting wrong answer on codeforces. I am not able to understand the reason. Can anyone help me out ?

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

    I saw your code and ran it on ideone. It works fine on ideone. So I submitted it just to be sure and got WA, just as you got. Then I noticed the size of the vector you allocated in the bfs function. It should be n+1. I got AC after changing it. https://codeforces.com/contest/1133/submission/51472660 This is the AC code. Only the size is changed, nothing else. It worked on your machine and ideone probably because it allowed out of bound call, and luckily there was no garbage value in that memory.