flamestorm's blog

Codeforces Round #803 (Div. 2) Editorial
By flamestorm, 11 months ago, In English

Thank you for participating in our contest! We hope you enjoyed it.

1698A - XOR Mixup

Hint
Solution
Implementation (C++)
Implementation (Python)

1698B - Rising Sand

Hint
Solution
Implementation (C++)
Implementation (Python)

1698C - 3SUM Closure

Hint
Solution
Implementation (C++)

1698D - Fixed Point Guessing

Hint
Solution
Implementation (C++)
Implementation (Python)

1698E - PermutationForces II

Hint 1
Hint 2
Hint 3
Solution
Implementation (C++)

1698F - Equal Reversal

Hint
Solution
Implementation (C++)

1698G - Long Binary String

Hint
Solution
Implementation (C++)
  • Vote: I like it
  • +54
  • Vote: I do not like it

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

Lighting fast editorial!

→ Reply
»
11 months ago, # |
  Vote: I like it +45 Vote: I do not like it

I felt, a huge difference in the difficulty of problems D and E.

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

One zero should be enough in C right? Since $$$0+0+a = a$$$ which is in the array.

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

Another speedforces round but problems were good, enjoyed solving them

→ Reply
»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

it's very cool that you can solve every problem in python. Respect to the authors!

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

Thanks for the fast editorial!!!

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

162104309 This is my python solution for D. It almost same with the c++ implementation.

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

I am quite new to problems like D. Can someone give me some tips on this type of question where you have to constantly take input and print . And if possible please share some questions to practice as well . Thank you in advance:)

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

How did a lot of people solve problem D? It looks very tricky to me.

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

    Same here.

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

    I don't know how other people solved it, but when I saw the number of questions <= 15, I thought that log2(1e4) == 14, so 80% is a binary search by my logic :)

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Yeah, but binary search decision function is tricky.

      → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    First of all, as the maximum numbers of queries you can ask it's 15, you know that this problem requires binary search.

    Secondly, for example if your query is 1-3, then you have to count the numbers that are in range 1-3 (if the problem returns you [1,4,5], then there is only one number in range 1-3 (1), at this point you can take the following conclusion:

    • If the count var is odd, then the number that is haven't been swapped is in that range (1-3) because it could not be swapped by any other number, if the count var would have been even, then both numbers could have swapped each other.

    I haven't explained myself very well but I hope now u understand better now the problem.

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

My solution for problem d on my machine does n't printing zero but it says that i am printing zero when i submit my code 162169758

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

    Run first test case on your machine Ur solution will return 0 as ans, actually same happend with me.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      My ans is 2 bro can you please debug it because i am not able to find any error

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

Wow i did not observe we can have any A[i] as answer saw n range was small and did brute force to find x of the previous array.

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

    I did same and when i had solution i think it was wrong and starting debugging my code. p.s : i did not see that there are multiple answers

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

Can anyone tell me what's the difference between cout.flush(); and fflush(stdout); ?

Used fflush(stdout); 162169561 : Idleness limit exceeded

Used cout.flush(); 162169654 : Accepted

Used fflush(stdout); removed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);162169729 : Accepted

I know we can simply use endl; but what's the difference between these two ?

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

    stdout and cout are not the same, though they are synced by default. By ios::sync_with_stdio(0), you break the sync, making them work separately. In other words, cout is not flushed with fflush(stdout).

    → Reply
»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

It was a great Contest!! Solved Interactive for the very first time.

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

I didn't got the first claim of problem E that strength required is max ai-bi.Suppose a={5,1,2,3,4} b={1,2,3,4,5} still if s=1 a can be converted to b by these operations swap(a1,a2) swap(a2,a3) swap(a3,a4) swap(a4,a5),,then how is the claim true??

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

    you swap x and y instead of a_x and a_y

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

      my bad!!! I understood the problem incorrectly ;=(

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

Good problems, thanks for fast editorial

→ Reply
»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I don't think you need sortings for E, making its complexity linear. For the last part, we can just take whatever is left as long as it is at least a[i]-s. We just need to do it in a decreasing order in a[i].

→ Reply
»
11 months ago, # |
  Vote: I like it +29 Vote: I do not like it

flamestorm The time complexity for problem D is O(n + logn), not O(nlogn). You do only one binary search per test case, and the sum of lengths of all queried subarrays is at most n.

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Best Contest for me till date!! Great Tasks and Great Rating Changes as well. Thanks flamestorm and ScarletS

→ Reply
»
11 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Non-mathy interpretation for G:

First of all treat the corner case of the string having only one 1.

Let's use the string in the leftmost position possible. It's easy to prove that the best answer will have an operation there. Now, while there are more than 2 set positions, let's erase the second leftmost position that has some 1. To do that, just align the leftmost 1 from s with that position. I'll leave the proof of why that gives us the best answer as an exercise to the reader.

Obviously we can't do that because it'd be too slow. Then the solution is just realizing that that process can be rewritten as matrix multiplication mod 2, the idea is that after doing the first operation, we keep a window of bits just to the right of the first set bit and slide it to the right, erasing the first position with an operation if it is 1. After realizing that, we can simply use the Baby-step Giant-step algorithm to find the first occurrence of our target 100000000...

If you want another similar problem here's some problem from 2009 ICPC Brazilian Regionals. The statement is in portuguese and I don't know if it's translated somewhere, sorry for that.

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

    Could you please give a brief explanation on how the matrix multiplication works? I've got your first idea of how the greedy implementation will give the correct answer, but found it so hard to reduce the complexity. I've also searched for the definition of matrix multiplication on wiki and tried to figure it out myself but to no avail. Thanks so much for your attention.

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

Good C, it took me about 1 hour to guess the hidden conclusion :(

→ Reply
»
11 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Well,Here is my solution for problem E works in O(n) time
code
Consider to arrange a p[i] for each a[i] which satisfies

  1. $$$a[p[i]] - i <= s$$$

  2. for each b[i] is not -1 , $$$p[b[i]] = i$$$

Then we make b[p[i]] = i
It can be prove in the same way as the officical solution that it's the sufficient and necessary condition for making such a valid b.

So the answer is ways to arrange p[i].
Firstly if an x is valid to be set as p[i],it must be valid to be set as p[i+1].
So arrange p[i] from 1 to n.
if p[i] is arranged by condition 2, we ignore it.
else we count all the ways $$$all$$$ to arrange p[i] and mutiply our answer.
$$$all$$$ can be calculated during the implementation.

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

    I did this too. To me it's much more intuitive than binary search — a pure combinatoric approach.

    → Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why the same code about D,in GNU C++20 (64) will getTime limit exceeded on test 1,in GNU C++17 can get accept.

in GNU C++17 162184565 Time limit exceeded on test 1 and in GNU C++20 (64) 162184380 Accepted

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

First time solved 4 problems in cf div2 contest

→ Reply
»
11 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem F How to prove that those conditions mentioned in the solution are sufficient to determine if a can be turned into b ?

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Well, I think the complexity of the solution D is $$$O(n)$$$ rather than $$$O(n \log n)$$$. For the binary search here, the complexity is $$$\sum_i{n/2^i}$$$ which equals to $$$O(n)$$$ not $$$O(n\log n)$$$

plus: The solution is fixed now.

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

In the Rising Sand problem, if we take an array [2,2,2] as input and k=2, we can make it too tall by alternating increasing one of adjacent piles one at a time. 2 2 2 k=2, 2 3 3 -we take 2nd and 3rd element and perform operation, 3 4 3 -we take 1st and 2nd element and perform operation

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

    Too tall doesn't mean greater that adjacent elements, it means greater than the sum of the adjacent elements

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

      Sorry mate, realized it after 2min of posting the comment, but can't delete comment after 2 min :*)

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

Thanks for the fast editorial buddy:)

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

This is the best contest ever I've witnessed on codeforces, solving till D in a div 2 is something superb!! and it's my first time managing to do this!! Hats off for you guys! Please make lots of divs2 like this one.

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

I felt so dumb when I solved C after 1.5 hours :(

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

Thank you for the great round.

I went from only solving div. 4A to solving div. 2ABCD over the past two months; hopefully other fellow newbies can see similar improvements soon.

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

can anyone please explain the approach of problem C ?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Key Observations. 1)If the array contains more than 2 positive elements, then the array is not 3SUM-closed because if you take the summation of the 3 greatest positive numbers you won't get their sum in the array. 2) If the array contains more than 2 negative elements, then the array is not 3SUM-closed because if you take the summation of the 3 smallest negative numbers you won't get their sum in the array. 3) If the array contains more than one zeros, then you have to check only for one zero because, let the array is [0,0,a] then if you take 0+0+a=a, which is already present in the array. so finally your array only contains 1 zero (if present), and max 2 positive and 2 negative elements, which makes the array max of 5 sizes. you can check all triplets in O(N^3) for the array of max size 5. You can check my code for a better understanding. Code Link: https://codeforces.com/contest/1698/submission/162143985

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    This was kinda my thought process when solving (slightly different from the editorial):

    1) All 0s is an obvious YES

    2) One non-zero and the rest are 0s is also an obvious YES

    3) Can we have exactly two non-zeros while the rest are 0s? Only if the two non-zeros sum to 0, i.e., if you have x, -x, and the rest are 0s.

    (Note: if you sort the array, the above three cases are easy to check)

    4) What if we have three non-zeros? Let's consider their signs.

    4a) If we have three positive values, then their sum would be an even greater positive value, which doesn't exist in the array. This would be a NO.

    4b) Similarly, we can't have three negative values.

    4c) We could have at most two positive values and at most two negative values. But even with two positive values, we can't have any 0s then, since two positives plus 0 is a greater positive.

    4d) Similarly, if there are two negative values, then we can't have a 0.

    4e) Therefore, if there are at least three non-zeros, then we can have max 2 positives, max 2 negatives, and no 0s allowed at all. In other words, array size is max 4.

    Overall, my approach was to sort the array to quickly check cases 1, 2, and 3. That leaves Case 4, so first make sure the array size is max 4 (otherwise print NO). Once you're left with array size as max 4, you can simply brute force (I actually simplified this even further, but it's not necessary).

    The editorial suggests that sorting isn't required either. Simply save only the non-zero values when reading input. Then we can easily filter through the four cases with some counting, where the only remaining case is if we have at most four non-zeros (and no 0s), which we can brute force.

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

GOOD

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

Can anyone tell me which case am I missing? It was failing the 5th pretest. 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >>t;
    int cas=0;
    while(t--){
        cas++;
        int n,k;
        cin >>n;
        int pos=0,neg=0;
        vector<int> v;
        ll sum=0;
        for(int i=0;i<n;i++){
            int inp;
            cin >>inp;
            v.push_back(inp);
            if(inp<0)
                neg++;
            else if(inp>0)
                pos++;
            sum+=inp;
        }
        if((pos>1||neg>1)&&(pos+neg<n))
            cout<<"NO"<<endl;
        else if(n==3&&((v[0]+v[1]+v[2])==v[0]||(v[0]+v[1]+v[2])==v[1]||(v[0]+v[1]+v[2])==v[2]))
            cout<<"YES"<<endl;
        else if(n==3)
            cout<<"NO"<<endl;
        else if(n==4){
            for(int i=0;i<n;i++){
                ll ss=sum-v[i];
                int flag=0;
                for(int j=0;j<n;j++){
                    if(ss==v[j])
                    flag++;
                }
                if(!flag){
                    cout<<"NO"<<endl;
                    break;
                }
                if(i==3)
                    cout<<"YES"<<endl;
            }
        }
        else if(pos>2||neg>2)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

Thank you!

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

    When the array size > 4 and it contains zeros (your 1st condition (pos >1 || neg>1 && (pos+neg<n)) won't execute, in this case, you are printing "YES" that's why you are getting WA on test 5. Ex; if array=[0,0,0,-2,3] in this case you are printing "YES". but the right answer would be "NO". You can refer to my code for this case. Code Link: https://codeforces.com/contest/1698/submission/162143985

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

      Ohh yes! Got it. Thank you so much!!

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

      My code is also failing on the same test case i think , can u plz let me know whats wrong in it . Link to my submission — https://codeforces.com/contest/1698/problem/C (im including 2 zeroes in the array) example->n=5,a=[0 0 0 -2 3] o/p-YES and n=4,a=[0 0 -2 3] o/p-NO Here when i degub my vector , it contains same elements 0 0 -2 3 ,but still giving me wrong answer , i dont know why , it would be great help if u can respond to this : )

      → Reply
»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Well, can anyone explain more about problem G? How is multiply and mod defined in GF(2)?

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

how to test interactive solutions in the local environment?

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

    Write your own judge and use input/output piping.

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

      we have to provide input for the fixed query our program will be making right?

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

        Look at the input of an interactive problem in systest. Writing a judge being fed that input is usually a good idea.

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

    For simple basic testing, you can write down your own array on paper that fits the requirements of the problem. When your program asks queries, consult your array and answer honestly. Observe whether your program eventually gets the correct answer, asks the queries that you expect it to ask (binary searching), etc.

    Obviously, this is impractical for large comprehensive testing, but as with any other problem, you would need to write a separate program to deal with that. The bad news is that an interactive problem would require an interactive tester, so the testing program would be more complicated than simply generating test cases. The good news is that the interactive tester should easily identify whether your answers are correct or not (which is often difficult for non-interactive problems). In any case, it's questionable on whether this is worth your time and effort in a contest setting if you are reasonably confident in your solution already, since you could instead be focusing on other problems instead.

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

      hm right!! writing interactive tester according to every interactive problem you face in contest is time consuming.

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

can anyone tell me a testcase where my solution for problem C is wrong? my submission 162205607

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

    I believe the issue is with the case where mp[0] == 0 and n == 4. Your for loop only checks two sums: (a[0] + a[1] + a[2]) and (a[1] + a[2] + a[3]), but there are four possible triples. You can have an array that passes both of these sums but fails one of the other two sums that aren't checked.

    For example, consider the array [3, 1, -1, -2]. The two sums you check are (3 + 1 — 1) = 3 and (1 — 1 — 2) = -2, which both pass. But the sums (3 + 1 — 2) = 2 and (3 — 1 — 2) = 0 should result in NO. Your submission doesn't check these and seems to say YES.

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

      Yes I don't know why I was checking only consecutive numbers. Really thankful for the help though.

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

I have a question about E problem. It is said that the minimum strength needed is max(a_i — b_i). However when the a is [1, 2, 7, 4, 3, 6, 5] and the b is [1, 2, 3, 4, 5, 6, 7], it only need strength 2.First, we swap 5 and 7, then the a changed to [1, 2, 5, 4, 3, 6, 7]. Second, we swap 3 and 5, then the a changed to [1, 2, 3, 4, 5, 6, 7]. It is 2 not 4

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

    In the $$$i$$$-th move you pick two integers $$$x$$$ and $$$y$$$ such that $$$i \leq x \leq y \leq min(i + s, n)$$$.

    If the strength is two, you can swap 5 and 7 in the 5th move, and swap 3 and 5 in the 3rd move. But you have to process the moves in order (1st move, 2nd move, ...). For this example, you swap 3 and 7 in the 3rd move and swap 5 and 7 in the 5th move, making the required strength 4.

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

      thank you. I misunderstanding problem. I think in i-th move I can pick x and y such that x >=i and abs(y — x) <= s. thanks again

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

C was nice but annyoing. I liked the problems.

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

In problem D,can anyone explain how this line works:

" We claim that if this count is odd, then the subarray contains the fixed point; otherwise, it does not"

UPD:understood

→ Reply
»
11 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Otherwise, it can be shown that there must exist some subarray with equal endpoints that contains b1 followed by b2, so we can reverse it.

Show it then?

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

    It's just a pigeon hole principle. Consider all elements that are adjacent to elements equal to a1 (=b1) and note that we have a pair of same value on a right side.

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

    Thank you for asking this.

    To me this is the hardest part of this problem, and the author just left it as an exercise to the readers. What.

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

    Like in the editorial, assume array $$$a$$$ starts with $$$b_1, a_2, ...$$$ where $$$a_2 != b_2$$$.

    Consider the array $$$a$$$ where there is some consecutive $$$b_1, b_2$$$:

    $$$b_1, a_2, a_3, ..., a_n, b_1, b_2, y_1, y_2, ..., y_k$$$.

    Here, $$$a_2, ..., a_n$$$ is the sequence elements between the two $$$b_1$$$s and $$$y_1, y_2, ..., y_k$$$ is the rest of $$$a$$$ until the end of the array. Now consider the sets $$$A = \{a_2, ..., a_n\}$$$ and $$$Y = \{b_2, y_1, ..., y_k\}$$$ and suppose they are disjoint.

    Then all elements next to $$$b_2$$$ are either $$$b_1$$$ or in $$$Y$$$. Also, all elements in Y are only next to elements in $$$Y$$$.

    So the array b must be $$$b_1, b_2$$$ followed by some permutation of elements of Y. So if $$$A$$$ and $$$Y$$$ are disjoint then $$$A$$$ must be empty, which is a contradiction.

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

F is amazing, tho wish I didn't face undefined behaviour and spend 2h debugging it :noo:

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

Unable to see why my solution is failing for problem C: https://codeforces.com/contest/1698/submission/162286028

Update: I missed some cases. Accepted here https://codeforces.com/contest/1698/submission/162287499

→ Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My E solution with time $$$O(n)$$$:162292830

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

problem E: If possible Anybody can explain me with example solution of problem E I tried hard but not able to get it.

when a[i]-b[i]>s then ans=0; i understand this but i did not understand how to count ways to rearrange

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

Can any one help me with verdict Idleness limit exceeded in D , I have not solved much of interactive problems

link to my solution ... Any help is appreciated

→ Reply
»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

In Problem E let strength s = 2 a = [1 6 2 4 3 5] b = [1 2 3 4 5 6]

when i = 1 we swap 4 with 6 a = [1 4 2 6 3 5] b = [1 2 3 4 5 6]

when i = 2 we swap 4 with 2 a = [1 2 4 6 3 5] b = [1 2 3 4 5 6]

when i = 3 we swap 3 with 4 a = [1 2 3 6 4 5] b = [1 2 3 4 5 6]

when i = 4 we swap 4 with 6 a = [1 2 3 4 6 5] b = [1 2 3 4 5 6]

when i = 5 we swap 5 with 6 a = [1 2 3 4 5 6] b = [1 2 3 4 5 6]

when i = 6 we swap 6 with 6 a = [1 2 3 4 5 6] b = [1 2 3 4 5 6]

According to editorial minimum strength required is 4 as a2-b2 = 4 which will be max but here strength 2 is enough.

What am I missing?

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

    When i = 1, you can only swap elements between 1 and 3. The range is from i to min(i + s, n) for the ith swap.

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

Thanks for the great problem set. For problem F, how can we prove this statement:

Otherwise, it can be shown that there must exist some subarray with equal endpoints that contains b1 followed by b2, so we can reverse it.

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

    for example,

    a = 13...12...

    b = 12........

    we can understand array a and array b as different eulerian path of same graph. "12..." of a is shorter than "12........" of b. but, both start with "12". To satisfy this length condition, eulerian path of b must go "13..." part of a

    Do you think my thoughts are valid?

    → Reply
»
11 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Can anyone please help me in problem C ? I am getting wrong answer on test 12.

#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int arr[n];
        int pos = 0, neg = 0, zeros = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            if (arr[i] == 0)
            {
                zeros++;
            }
            if (arr[i] > 0)
            {
                pos++;
            }
            if (arr[i] < 0)
            {
                neg++;
            }
        }
        sort(arr, arr + n);
        if (pos >= 3 || neg >= 3)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 2 && neg == 2)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[n - 1] == -arr[0] && arr[n - 2] == -arr[1])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 2 && neg == 1)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[0] == -arr[n - 1] || arr[0] == -arr[n - 2])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 1 && neg == 2)
        {
            if (zeros > 0)
            {
                cout << "NO" << endl;
                continue;
            }
            else
            {
                if (arr[n - 1] == -arr[0] || arr[n - 1] == -arr[1])
                {
                    cout << "YES" << endl;
                    continue;
                }
                else
                {
                    cout << "NO" << endl;
                    continue;
                }
            }
        }
        if (pos == 2 && neg == 0)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 0 && neg == 2)
        {
            cout << "NO" << endl;
            continue;
        }
        if (pos == 1 && neg == 0)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 0 && neg == 1)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 0 && neg == 0)
        {
            cout << "YES" << endl;
            continue;
        }
        if (pos == 1 && neg == 1)
        {
            if (arr[n - 1] == -arr[0])
            {
                cout << "YES" << endl;
                continue;
            }
            else
            {
                cout << "NO" << endl;
                continue;
            }
        }
    }
    return 0;
}
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When pos and neg are both 2, your submission checks if (arr[n — 1] == -arr[0] && arr[n — 2] == -arr[1]). While the second condition is required for YES-instances (can be proven), the first condition is not. For example, the array [-2, -2, 2, 6] does not satisfy the first condition (so your submission would say NO), but it should actually answer YES.

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

How -1 -1 -2 2 this one answer is "no" If we add indices 2,3,4 our sum is -1 which exists in the array.

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

    for all distinct i j k this should be true

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

    But if u add indices 1,2,3 sum is -4 which doesn't exist in the array. U have to check all possibilities.

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

I think the complexity in problem F should be $$$O(n^2)$$$ because you can find equal endpoints around $$$b_1,b_2$$$ in $$$O(n)$$$

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

what's wrong with my solution for problem C — https://codeforces.com/contest/1698/submission/162852723

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

    the ok condition should be outside the loop starting from l = 0 to l = a.size()

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

For the second task, we just needed to count the numbers that are greater than the sum of two neighbors, and if k is not equal to 1, then the answer will display the number of such numbers, otherwise, if n — 2 is greater than zero, then the answer is n — 1 is divisible by two, otherwise the answer is simply n divided by two : :

ll n, k;
cin >> n >> k;
vector < ll > a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
ll m = 0, d = 0;
for (int i = 1; i < n-1; i++) {
    if (a[i] > a[i+1] + a[i-1]) m++;
}
if (k != 1) cout << m << endl;
else {
    if (n - 2 != 0) cout << (n - 1) / 2 << endl;
    else cout << n / 2 << endl;
}
→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the Solution in Python!

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

Can someone please explain E?? I'm a newbie... :,)

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

I was having trouble solving problem C; somehow, I got AC, but can someone help point out the mistake in my other submission? Thanks in Advance.

Right Solution : 172603818

Wrong Solution : 172602039

Basically, it is failing for the test cases of type {(one -ve) (some zero) (one +ve)};

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

    Take a look at Ticket 16178 from CF Stress for a counter example.

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

      hey[user:variety-jones], Thanks for helping me out, the mistake was so trivial — I was iterating over the wrong array (I guess I have to change my "making every array named as arr " habit). But I am shocked even with the wrong array name, in my correct submission, it got AC, I guess after neglecting the wrong cases, the original array and the transformed array both remain the same.

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

I don't understand why we need to have a maximum of two zeroes. If the whole array is made up of zeroes, wouldn't we need at least 3 zeroes in order to have 3 distinct indices?

→ Reply