Stepavly's blog

By Stepavly, 12 months ago, translation, In English

All problems were created by MikeMirzayanov and developed by me (Stepavly) and Supermagzzz.

1462A - Favorite Sequence

Editorial
Solution

1462B - Last Year's Substring

Editorial
Solution

1462C - Unique Number

Editorial
Solution

1462D - Add to Neighbour and Remove

Problem authors: MikeMirzayanov, Supermagzzz, Stepavly.

Editorial
Solution

1462E1 - Close Tuples (easy version)

Editorial
Solution

1462E2 - Close Tuples (hard version)

Editorial
Solution

1462F - The Treasure of The Segments

Editorial
Solution
 
 
 
 
  • Vote: I like it
  • +127
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for quick editorial! Great contest too and interesting problems

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you!

»
12 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Felt more like a div4 but fun problems nonetheless. Cheers.

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

    Just because you can solve problems, doesn't make their worth less. For a beginner, these maybe are one of the toughest that they are facing.

»
12 months ago, # |
Rev. 3   Vote: I like it +35 Vote: I do not like it

Another solution for D using dynamic programming.

Let's consider $$$dp[i][k]$$$ — bool variable, that means "is it possible divide $$$a_1, a_2, ..., a_i$$$ on $$$k$$$ segments of equal sum".

Initially, $$$dp[0][0] = true$$$, others — $$$false$$$.

How to count $$$dp[i][k]$$$? If we can divide $$$a_1, ..., a_i$$$ on $$$k$$$ segments of equal sum, it means that this sum is $$$(a_1+...+a_i)/k$$$ (let's called it $$$s$$$)

So we need to find such $$$j$$$, that $$$a_j+...+a_i$$$ = $$$s$$$. We know that $$$a_i \geq 1$$$, so if this $$$j$$$ exists — it is only one. We can find this $$$j$$$ using binary search, or map with prefix sums, or just maintain $$$n$$$ pointers (one for each $$$k$$$), e.t.c

So if there is no such $$$j$$$, $$$dp[i][k] = false$$$. In other case $$$dp[i][k] = dp[j-1][k-1]$$$.

To find answer, we need to find maximal $$$k$$$ such that $$$dp[n][k] = true$$$. It means we can divide it on $$$k$$$ segments, so we need $$$n-k$$$ operations.

Code: 101285918

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

    I also thought the same approach, i just stored the index of first element of last partition. I think each will be visited only once.

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

    brilliant, thanks!

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

    can you please point out what is wrong with this logic: we need to check if we can divide the whole array into groups of sum s and print the minimum of the summation of their sizes. for finding sum s: let max element be M. first I check if for groups with sum equals max element(because their sum will atleast be equal to M ) if such a group is not found then i check for sum =M+a[i+1] then for M+a[i-1]; // here i denotes the index of M like this I check for all possible sums composed of substrings involving M and then print the minimum of their answer. LOGIC behind selecting all substring involving M: it is because in the final answer atleast groups with sum =M needs to be there(for minimum) if they exists . if thats not the case then groups with sum equals sum of substrings involving M need to be there . code

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

Bruh, problem C got a way easier solution. Just brute force result from $$$1$$$ to $$$123456789$$$ and then, store the result and just handle when $$$N>45$$$ and that is all. Oh, make sure also to use pragma optimizations and unrolling loops for this funny solution to pass. Here is my code. Or, you can play it safe and handle few more N's like I did in contest. Here is my second code.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Funny thing ikr..i played it safe for 40,41,...45..etc. Till 39 the answer fits in 1e6 so no TLE issues.

    C
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    or just go with all the permutations $$$O(9*9!)$$$ sub

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it +98 Vote: I do not like it

      Thank You

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

        is that n*n factorial :)

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

          nah. It's not n*n! actually. The implementation's worst calculation is 9^9, so I hacked it.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    I Don't know what's worse, my life or your code's indentation

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    there is also a faster way, we need to check all subsets of set {1,2,...,9} using something like bitmasks.
    this works with O(9 * 2^9)

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    There's another way around Click

    You can get solution in $$$O(1)$$$

    Edit: Mahfel have a look, this is far faster then $$$O(9*2^9)$$$

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      yes,you're definitely right.
      but copying 45 numbers in an array is kind of boring for me,what about you? :)

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

    Or you could just brute force over the subsets from 1 to 2 ^ 10 — 1 and check if the sum is of the digits is the same or not. If it is, then just take the min like this : 101355465

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

    You can check my code also i just store all possible answer in vector and print the element which is present at x-1 and also for x>45 our answer is always -1

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

The formulas in the Editorial of Problem E1 do not reflect the formulas used in the Code.

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

    Yes, I think so.

    They mistakenly wrote $$$\frac{cnt[x]\times cnt[x]\times cnt[x]}{6}$$$ instead of $$${cnt[x] \choose 3} = \frac{cnt[x]\times (cnt[x] - 1)\times (cnt[x] - 2)}{6}$$$ and $$$\frac{cnt[x]\times cnt[x]}{2}$$$ instead of $$${cnt[x] \choose 2} = \frac{cnt[x]\times (cnt[x] - 1)}{2}$$$

»
12 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Who told you to look on the internet? during the contest

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      Who has forbidden you to look on the internet? During the contest?

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

        Reasonable difficulty parameters of div 3.....

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          I am not talking about the difficulty parameters of div3. I am talking about the fact you mentioned: "You can't look through the internet during the contest". There is no rule against using google/prewritten code in codeforces. You may even consider "googling" a special skill for CP :D

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

I have one small doubt , during the contest I used printf for printing output and I got 4 WAs and after contest I submitted same solution by using cout and it got accepted.Why so?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Don't mix cout with printf when you are using fastIO, printf is faster so, it might output the result before the cout does.

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

      Ohh,thanks . I will never forget this in my life.

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please help me with this solution of F, 101358483 I am basically trying to count the number of elements that will be good with one element

I am using a set to get the number of elements good with it before that element and upper_bound to get the number of elements after that element.

So, I get the number of elements good with any element and store the maximum of it And therefore the answer is n- (the number calculated above) Any help will be highly appreciated.:)

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

In problem F — The Treasure of The Segments, how do we make sure that the i-th start segment and the i-th end segment (which we use to calculate the current value) — both these start and end points belong to the same segment? Isn't the hypothesis that we iterate over all segments. But in many cases, when sorting the start and end points separately, it should violate the hypothesis that the i-th segment is being considered.

e.g. (1, 2), (3, 7), (4, 5), (6, 9), (8, 10)

Left endpoints in sorted order : 1 {belongs to 1st segment}, 3 {2}, 4 {3}, 6 {4}, 8 {5}

Right endpoints in sorted order : 2 {1}, 5{3rd segment and NOT 2nd}, 7 {3}, 9 {4}, 10 {5}

Even if it is true that the cases for l > R and r < L are handled separately, I cannot understand how calculating these half-values for the same position in sorted order ensures reaching the optimal answer.

Edit: Looks like I didn't read the editorial code carefully. We are considering the i-th segment only (by iterating over the original vector of pairs v). Thanks to both the gentlemen who replied.

???

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

    We can say if a segment $$$(a,b)$$$ coincides with segment $$$(c,d)$$$, then $$$c<=b$$$ (vice versa may not be true). So, for a particular segment $$$(a,b)$$$ we can find all those segments whose $$$start<=b.$$$

    In the above picture if I calculate such segments for red segment, I'll get $$$5$$$ such segments (including the red segment itself).Now, we have to remove such segments in which $$$end<a$$$ because such segments (segment $$$1$$$ in this example) will surely be included in the above ans but in actual they don't intersect with red segment. Thus, we get $$$5-1=4$$$ segments intersecting with red segment (including itself).

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

      I fail to see how this answers my question. Please note that I had solved this question, just without sorting the two arrays independently. That's my issue — how can you ignore that you're not considering the same segment anymore? It's been bothering me a lot and I'm sure it's something silly that I'm missing. Thanks nevertheless.

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

        It isn't necessary that $$$i^{th}$$$ index of both the arrays after sorting belong to same segment. The proof above still remains valid.

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

      Your explanation using Inclusion-Exclusion is much rich than editorials explanation. I was able to solve it by your explanation. Thanks a lot.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    For each segment, we are calculating the number of segments that end before the current one starts and the number of segments that start after the current one ends. Now, think a minute and see that these two values will never have a common value.

    Lets say current segment starts at L and ends at R
    1) All segments that end before L will have start and end both less than L. 
    2) All segments that start after R will have start and end both greater than R.
    
    So, you can see these two can never have a common because first value has [l,r] less than L and second value has [l, r] greater than R. They can never intersect.
    
»
12 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

PROBLEM E

Please help my code is showing wrong answer on test 80 in test 2 can anyone tell me a case where my code is failing thanks in advance !!

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

I had a slightly different approach to D using more of an analytical/brute force method.

Similar to the reasoning presented in the posted solution, the sum of the overall array will always stay the same, meaning that the original value of each part of the array will be preserved either as an individual number in the final array or as a component of another number in the final array.

As such, it can be seen that the number at an index of 1 must always be included in the final array in some form, allowing for an iterative solution over the array to be created.

Iterating over all values i from 1 to n and keeping the cumulative sum sum of each number that was iterated upon to represent one "fixed" value in the final array, this sum can then be validated by iterating over the remainder of the array. When iterating over the remainder of the array, keep a sum cSum of numbers that have already been reached. If that sum is equal to the sum of the fixed window, reset cSum to 0 and continue and if it is greater than the sum, then break from the iteration since that means it doesn't work. Store the number of times cSum was equal to sum.

Finally, take the maximum number of times that cSum was reset through all iterations, add 1 to signify the initial reset at the end of the first window, and subtract from n for the final answer.

This solution would run with an O(n2) time complexity in its worst-case.

Code: 101330471

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

Why is time limit for E1 2 secs but time limit for E2 4 secs?

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C can be done by bruteforcing all $$$2^9$$$ possible numbers of different (non null) digits that are the smallest in lexicographical ordering for that set of digits, since the solution must satisfy this constraint.

Example

»
12 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Here's a fairly simple $$$O(n \log(an))$$$ solution for D: 101370002

It can also be optimized to just $$$O(n \log n)$$$.

Also quick note, I'm still seeing Russian in the English title of this post ("Разбор").

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

    can you please explain it a lit bit? Thanks!

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

      He already explained in his stream

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Sure! I actually didn't explain this in my stream (I came up with it after my stream).

      Let's say the sum of the array is $$$s$$$ and we want to know whether we can end up with a final array of length $$$len$$$ with all equal elements. Then we need to cut the array up into $$$len$$$ subarrays, each with sum $$$\frac{s}{len}$$$.

      If we compute the prefix sums of the $$$a_i$$$, this means we'll need to find one prefix sum matching each of $$$\displaystyle \frac{1}{len} \cdot s, \frac{2}{len} \cdot s, \dots, \frac{len}{len} \cdot s$$$. Since $$$a_i > 0$$$ we really just need $$$len$$$ different prefix sums that are divisible by $$$\displaystyle \frac{s}{len}$$$.

      If we have a particular prefix sum $$$p$$$, what values of $$$len$$$ does it work for? It turns out we take $$$\displaystyle x = \frac{s}{\gcd(s, p)}$$$ and then we want all multiples of $$$x$$$. (For example if $$$p = \frac{3}{5} s$$$ then $$$x = 5$$$.)

      We compute GCDs, generate all these counts, and then do a sieve-style summation to cover all multiples, and we're done.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        To get to $$$n \log n$$$, notice that the bottleneck is computing the GCDs which takes $$$\log(an)$$$ time each iteration: 101370002. However we only care about the value of $$$g$$$ when $$$\displaystyle len = \frac{s}{g} \leq n$$$, or namely when $$$\displaystyle g \geq \frac{s}{n}$$$. So we can stop our GCD algorithm once we go below $$$\displaystyle \frac{s}{n}$$$, which means it only takes $$$\log n$$$ time.

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

        neal can you tell what exactly does x signify. I understand that if i can divide sum into x parts than it is possible to divide it into all divisors of x parts as well. for example if we can divide sum into 4 parts we can also divide it into 2 parts as well, just by clubbing the two parts into one.

        So instead of taking all multiples of x should not we take divisors of x?

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

I am trying to grasp on what case this submission (101340630) for problem D is failing. According to the editorial, a check to verify if k is the answer can be implemented greedily. In the above implementation, i try to pick the min-element in the original array and add it to min(left-element, right-element) before deleting that min-element. Is that theory wrong?

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

    Yes, example 5 6 2 6 3 gives the wrong solution(or 3 6 2 6 5 depending on your code). The answer is 3, but greedy will give 4 for one of these inputs.

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

https://codeforces.com/contest/1462/submission/101325108 Please tell me what i did wrong as i think i have applied the same thing as mentioned in the editorial.

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

Thank You!

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

I got WA in D , can anyone prove why my idea is incorrect? Every time I check whether all the elements are equal or not, if they are equal just print the current number of operation else pick the smallest element and add it to the smallest neighbour and increase operation count by 1, my sub link:- https://codeforces.com/contest/1462/submission/101310473

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

      ??

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        I answered to this exact question in the link I pasted, anyway this is the answer. Example 5 6 2 6 3 gives the wrong solution(or 3 6 2 6 5 depending on your code). The answer is 3, but greedy will give 4 for one of these inputs.

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

          OMG! got it, when they have equal values in both sides it fails to choose optimally

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

            Not true. Reason is that greed will just fail. :)

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

    I did the same in the contest like an idiot without thinking. Simply put, it's wrong. Adding the smallest to the one of it's neighbouring elements seems to work, but there is no way that it should work.
    Eg. {9, 1, 5, 3, 2}

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

Another solution for problem B:

Lets create a $$$DP[idx][idx2][state]$$$. $$$idx=$$$prefix of first string, $$$idx2=$$$prefix of second string, $$$state=0,1,2$$$. Transition is to check if $$$s[idx]=t[idx2]$$$ where $$$s$$$ is the first string and $$$t="2020"$$$. If $$$state=1$$$, change it to $$$2$$$. Because $$$state=0$$$ means that we didn't delete anything, state=1 means we are currently deleting, $$$state=2$$$ means we are not allowed to delete anymore. And another transition depending on the state. If state is equal to $$$0$$$, then it will turn $$$1$$$ as you are forced to delete that number. If state equals to $$$1$$$, you will keep deleting. Otherwise, you have nothing to do and you didn't find an answer. I hope you liked my overkill solution!

Warning, bad indented code
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E2

For those who are looking how to calculate for a NcR % mod for huge N and R , for E2.

#define mod 1000000007
const int MAXN = 200000;
int fact[MAXN];
int ifac[MAXN];

int ncr(int n, int r) {
    if( n < r or r < 0 )
        return 0;
    return fact[n]*(ifac[r] * ifac[n-r] %mod) %mod;
}

int power( int x, int y ) {
    int a = 1;
    for( ; y>0; y>>=1, x=x*x%mod )
        if( y&1 )
            a = a*x %mod;
    return a;
}

void preNCR() {
    fact[0] = 1;
    for( int i=1; i<MAXN; ++i )
        fact[i] = fact[i-1]*i %mod;
    ifac[MAXN-1] = power(fact[MAXN-1], mod - 2) %mod;
    for( int i=MAXN-1; i>=1; --i )
        ifac[i-1] = ifac[i]*i %mod;
}

just call the preNCR() in main().

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

What is wrong in this? Problem 2 101403407

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You should consider two more cases: - when string begins with "2020" - when string ends with "2020"

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

What's wrong with my solution of E2? link

Upd. Wow! I find the problem! AC.

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

Thanks a lot for the contest and the editorial learnt many things from this round!

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

Why does my solution for 1462F give a TLE in pypy3 but gets accepted with python3? https://codeforces.com/contest/1462/submission/101417012

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

can anyone explain whats wrong with my solution for E1 ``` public static void solve1() {

int n = in.nextInt();
    int[] arr = new int[n + 1];

    for (int i = 0; i < n; i++) {
        int x = in.nextInt();
        arr[x] = arr[x] + 1;
    }
    int ans = 0;
    for (int i = 2; i < n; i++) {
        ans += arr[i - 1] * arr[i] * arr[i + 1];
    }
    for (int i = 1; i < n; i++) {
        ans += arr[i] * (arr[i] - 1) / 2 * arr[i + 1];
    }
    for (int i = 2; i <= n; i++) {
        ans += arr[i - 1] * arr[i] * (arr[i] - 1) / 2;
    }
    for (int i = 2; i < n; i++) {
        ans += arr[i - 1] * arr[i + 1] * (arr[i + 1] - 1) / 2;
    }
    for (int i = 2; i < n; i++) {
        ans += arr[i + 1] * arr[i - 1] * (arr[i - 1] - 1) / 2;
    }
    for (int i = 1; i <= n; i++) {
        ans += arr[i] * (arr[i] - 1) * (arr[i] - 2) / 6;
    }
    System.out.println(ans);
}

} ```Is it something related to the data type this solution is not passing or 5th pretest

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

can someone tell me why is this giving wrong answer probelm:b https://codeforces.com/contest/1462/submission/101418146

»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I don't know if this the right place to post. But I am wrongly penalized for Problem D submission. I got this message:

Attention! __ Your solution 101339246 for the problem 1462D significantly coincides with solutions liar_liar/101292392, Alan612/101305989, concoction/101323219, aditrip/101327012, shalinjain349/101329688, abd_U1/101339246. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. __

Proof that coincidence in code(Problem D,round 693) occurred because of using public code from GeeksforGeeks before the start of the round.

Here is the link

This code was last updated on 9th May,2020

It's very clear that KpartitionsPossible function is similar in the following codes including mine:

101339246(My submission) 101292392 101305989 101323219 101327012 101329688

I am wrongly accused because of MOSS,I think this evidence is conclusive.

Round Details — Round 690 Div.3

Please give the change in rating I deserve! :)

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

"Attention!

Your solution 101277221 for the problem 1462B significantly coincides with solutions soham_mittal/101273272, complexroots/101277221. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

This was such a direct question which just involved some if/else statements checks. Also I used Python and this could be the reason for two or more similar answers. I have NOT done any violation or any illegal activity.

What do I do now?

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

Problem C can be solved using the Dynamic Programming Subset sum problem. We can have digits for our number from subset {1,2,3,4,5,6,7,8,9} and the sum needed is given as input, we can find all the subsets with given sum among them we will choose the smallest subset, sort the digits, and form our answer using these digits which will be the smallest number.

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

Thank you for great contest!

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Very Interesting problems!!

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

in problem F how the output of this test case 1

4

1 2

2 3

3 5

4 5

it should be 2 right? correct me if i am wrong

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

    It should be 1 because we can provide the required property with the 3rd segment by deleting only the 1st segment.

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

Can anyone please explain the following piece of code of Ques E2(Hard version). This is being used to calculate the combination value and fac is the array already having all the factorial values. MOD=10^9 +7

(fac[n] * pow(fac[n — k], MOD — 2, MOD) * pow(fac[k], MOD — 2, MOD)) % MOD

How is nCr being calculated from this. What is the role of pow in this??

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

Can someone check my code and tell me why I'm getting TLE on problem E2?

https://codeforces.com/contest/1462/submission/101501537

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

Why is my O(NLogN) solution for problem E1 is getting TLE in test case 12 https://codeforces.com/contest/1462/submission/101481405

Help !

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

Could anyone please explain briefly what the editorial for problem D says? I didn't understand, what it says.

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

    I also didn't understand the editorial, so I had to struggle initially.

    If we have to make all elements equal, we have to equally divide the sum of the elements of the array into the elements. This can only be achieved through the factors of the sum of the elements of the array. Hence, at this point , it is clear that the factors of the sum can be the only possible value of the final elements of the array.

    Now, we can calculate the factors and store them in a vector. Next we iterate the factors and for each factor, we try to achieve an array of the factors. For this, for each factor, take a variable sum and iterate from 1 to N of the array, adding the elements to the sum variable until the value exceeds the factor that we have taken into consideration. If the value exceeds, we break out of the loop and continue checking other factors. If it doesn't exceed, we check if the sum is equal to the factor or not. If it is equal, we store the number of steps and update answer with minimum of answer and the steps. We keep on repeating this for all the factors and print the answer at the end.

    This is my solution. I think you can understand from it, if you are stuck. Please let me know, if you have any doubts, I will try my best to clear it.

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

Please help me with my solution of E2

Here is my approach: 101597737 It is giving the wrong answer on test 3 and I am not able to find what's wrong. Please help.

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

I am confused between E1 an E2 if E1 is lower version of E2 then why solution of E2 without mod is not passing E1 it is giving wrong answer on test case 5 can anyone explain this ?

my submission of E1 converted from E2 101642503

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

    You are using mod operator while evaluating Factorial , nCr , invfact

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

      below is code without mod operation it won't even paas sample test cases

      #include<bits/stdc++.h>
      #define rep(i,n) for(int i = 0; i < (n); ++i)
      #define drep(i,n) for(int i=n-1 ; i > =0; i--)
      #define all(a) a.begin(),a.end()
      #define pb push_back
      using namespace std;
      typedef long long int ll;
      const int N = 300500;
      const int mod = 1000000007;
      
              
       ll C(ll n ,ll k)
       {
           
           ll ans =1;
           if(k >n-k)
           k=n-k;
       
           for(ll i=1; i<=k;i++)
           ans*=(n-i+1),ans/=i;
       
           return ans;
       } 
      
      void solve(){
      
          ll n,m,k,ans=0;
          cin>>n;
          m=3;
          k=2;
          vector<ll> v(n);
          for(ll i=0;i<n;i++)
              cin>>v[i];
          sort(all(v));
          for (ll i = 0; i < n; i++) {
              ll l = i + 1;
              ll r = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin();
              ans = (ans + C(r - l, m - 1));
          }
              
          cout<<ans<<"\n";
       
      
      
      
      
      }
      int main(){
       
          //#ifndef ONLINE_JUDGE
          //freopen("input.txt","r",stdin);
          //freopen("output.txt","w",stdout);
          //#endif
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout.precision(10);
          cout << fixed;
      
          int _;
          cin>>_;
          while(_--)solve();
      }
      
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E2 :
invFact[i] = fast_pow(fact[i], mod — 2);
why we use (mod-2) anyone answer please....

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

    $$$a^{m-2} \equiv a^{-1}$$$ mod $$$m$$$ if $$$m$$$ is a prime number

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

For problem E1, my approach is sort the array and iterate through it, binary searching, for each element, the most distant element satisfying the constraint. If we are at index i and find that the index j > i is the one we are searching for, than the number of triples beginning with minimum element v[i] will be (j-i-1) + [(j-1)-i-1] + ... + [(i+2)-i-1] = [j + (j-1) + ... + (i+2)] — i*(j-i-1) — (j-i-1) = (j+i+2)*(j-i-1))/2 — (i+1)*(j-i-1). Doing it for each i in [1..n] should solve the problem. But it gives wrong answer in the test 4: Code

It seems to be counting more than once something. But I can't see where it happens. Can somebody help, please ?

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

Problem E has $$$\mathcal{O}(n \log n)$$$ solution, which doesn't use, that elements are in $$$[1, n]$$$. Let's sort our array, and calculate number of possible subsets if minimal element in subset is $$$a_i$$$. Let $$$l$$$ be max index, such that $$$a_l \leqslant a_i + k$$$, let $$$x$$$ be numbers equal to $$$a_i$$$ in range $$$[i, l]$$$ in array, and $$$M$$$ is number of other numbers in this range. So if in chosen subarray $$$a_i$$$ is minimal value, then all subarray is in this range. So number of possibilities to choose this subarray is $$$\sum_{i=1}^x C^i_x \cdot C^{m - i}_M$$$, where $$$C^k_n$$$ is number of possibilities to choose $$$k$$$ elements from $$$n$$$ elements, also known as binomial coefficient which can be easily find as $$$C^k_n = \dfrac{n!}{(n - k)!k!}$$$. If we precalculate factorials, and numbers, that is inverse modulo $$$10^9 + 7$$$ to factorials, we can calculate $$$C^k_n$$$ for $$$\mathcal{O}(1)$$$(Warning: if $$$k < 0$$$ or $$$k > n$$$ we must return 0). Because $$$a$$$ is sorted, we can find $$$l$$$ using two pointers technique and calculate $$$x$$$ for $$$\mathcal{O}(n)$$$ total. Because sum of $$$x$$$ is $$$n$$$ it will be $$$\mathcal{O}(n)$$$ time and $$$\mathcal{O}(n \log n)$$$ time to sort array. We can precalculate factorials and inverse factorials for $$$O(n \log A)$$$ using binary pow or extended gcd. Also we can calculate inverse factorials for $$$\mathcal{O}(n)$$$ using linear sieve technique which described here, but it is not necessary. Space complexity is $$$\mathcal{O}(n)$$$

Submission, which can help to understand solution: https://codeforces.com/contest/1462/submission/103030183

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

Couldn't wrap my head around the code for inverse factorial

invFact[i] = fast_pow(fact[i], mod - 2);

Then finally, this helped:

https://blogarithms.github.io/articles/2019-01/fermats-theorem

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

1462C — Unique Number i find that this question can be interpreted as the coin change problem, so here instead of just counting the possible number's sum ,we need to store them too, where the numbers set will be from 1 to 9,in descending order, so after getting all the possible numbers in form of strings ,we can sort the string based on number by converting them to integer

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

For C, I have used the brute force to calculate sum of all subsets of set {1,2,3,4,5,6,7,8,9} and the subset with the minimum length is our answer just sort the minimum length subset and print its element. Time complexity is O(t*2^9).MY code ->

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

I have followed a similar approach to the editorial solution of problem D.I am unable to understand why am getting TLE. Here is the link to my submission https://codeforces.com/contest/1462/submission/116474509 Never mind was a silly error

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

Can someone please explain to me why Last Year's Substring has a DP tag as I'm unable to find any DP-based solution?

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

Can anyone tell what is wrong with problem E2 submission 120341826.

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

can problem E1 be solved by binary search for any largest elements in a tuple of the current element?

i've tried the new observation but i failed :(

thanks if anyone can point me out

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

in E1 why nc3 will not work ?