flamestorm's blog

Codeforces Round #827 (Div. 4) Editorial
By flamestorm, 14 months ago, In English

Thanks for participating!

1742A - Sum

Idea: flamestorm

Tutorial
Solution

1742B - Increasing

Idea: mesanu

Tutorial
Solution

1742C - Stripes

Idea: flamestorm

Tutorial
Bonus
Solution

1742D - Coprime

Idea: badlad, SlavicG

Tutorial
Solution

1742E - Scuza

Idea: mesanu

Tutorial
Solution

1742F - Smaller

Idea: SlavicG

Tutorial
Solution

1742G - Orray

Idea: SlavicG

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

Comments Comments (60)
| Write comment?
»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

B was just a few lines with the help of STL :D (Submission: 176051852)

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

    Nice!

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

    Or

    int n;
cin >> n;
vector<int> a(n);
for(auto &x : a) cin >> x;
cout << (set<int>(a.begin(), a.end()).size()==a.size()?"YES":"NO") << '\n';

    which I find even simpler.

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

    But the complexity of your algorithm being O(n*log(n))?? It can easily be solved using O(n) using maps. The logic is simple if any number is present more than once then it is impossible to rearrange in increasing order Here is mine: Submission 177430404

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

      complexity of insertion in map is O(log N).

      While in the worst case, the time complexity of insertion in an unordered_map is O(N). So in worst case your solution is O(N*N) not O(N).

      On the other hand if you used map it would be O(NlogN)

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

    I know your solution is correct but here he elaborates to us the idea of the problem not just the solution. great respect

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

Problem C,When I judge the horizontal and vertical directions of a color,my submission-->175928516, I can't pass the test. But when I only judge the corresponding direction of a color, it passed,my submission-->176020169 Can someone tell me why

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

    Look at the title,some horizontal rows have been painted red, and some vertical columns have been painted blue.

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

      I also didn't read it properly costed me more than an hour to cause it took more than 15 mins to run on pretests :'(

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

    Consider this case

    BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

    Answer : 'R' Output : 'B'

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

for problem C, many of us missed this case :(

BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRR

Answer : 'R' Output : 'B'

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

    I think the answer should be R, as it has the occurrence 8 consecutive times in a row. Please tell, why are there so many messages related to this?????

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

      Because many of us just checked whether the entire row is same color rather than checking entire row is Red Or Not. This also follow for column also.

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

why is my 176088793 getting WA on 11 (problem D)

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

    when the input array is 2 6 10 15 your output is 0 because when you reach 6 the gcd will be 1 but actually there is no coprime number between 6 , 10 , 15 but it is true that their gcd is 1 The correct output should be 5 by taking 2 and 15

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

I got TLE in problem E. My submission is 176039360 . How can I improve this?

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

    As per your solution I suggest you to have a read on Time Complexity Analysis It would be helpful for you to understand why your code is getting TLE

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

I got TLE on Problem D. Not sure why. How can I improve this solution

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

    Instead of keeping track of every index , you can consider the values of the array elements , that can go up to only 10^3 . Now , if you run two for loops , then time taken O(10^3*10^3) and for T=10 test cases , O(10*10^3*10^3) = O(10^7) [neglecting time complexity for __gcd(a,b) stl ].

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

Video Editorial for Chinese：

Bilibili

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

I think there is an easier way to implement the algorithm in G's tutorial. 176054281

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

Weak pretest in problem F.

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

sadly, i misread the "OR" as "XOR" and failed to ak

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

flamestorm is the solution of bonus of problem C like this :

we go through each row except the ones with full red then check whether if a column is painted blue whether it is painted red in any of the previous rows and if a column is painted red whether it is painted blue in any of the previous rows and if a column is white whether it is painted blue in any of the previous rows; If any of these three happens then input grid is invalid otherwise valid

Is it correct ?

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

Hey flamestorm,

In problem C, the valid input must contain exactly one of theses situations:

1- Have one or more rows full of R's

2- Have one or more columns full of B's

otherwise, the input is invalid

Is it correct ?

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

    Well, those are a part of the conditions, but there seems to be more invalid cases to consider. The following is one example.

    .B.BB...
.B.BB...
.B.BB...
RBRRBRRR
RBRBRRRR
.B.BB...
.B.BB...
.B.BB...
    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I don't see any reason of downvoting him , he made a correct point.Maybe he has bad record in past in terms of commenting & posting but that doesn't have any relation with this,And why am I saying this? I am saying this because we all make mistakes in life ,doesn't mean we can't move forward

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

I got TLE in F question for Test Case #2, any ideas/hints how can I improve the code? submission

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

In problem D I have gotten wrong answer on test 24 on an invalid test int the statement they said that n must be greater than 2 but I have had wrong answer on a test with n=1 so please rejudge the problem SlavicG , mesanu , flamestorm please do something 175973439 .

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

In $$$C$$$, why didn't they put $$$n$$$ and $$$m$$$ $$$(1$$$ $$$\le$$$ $$$n,m$$$ $$$\le$$$ $$$1000)$$$ or something like that?

I think when $$$n=m=8$$$ problem is more like Div.4 $$$B$$$ problem, this could make problem $$$C$$$ little harder, just as hard as a Div.4 $$$C$$$ should be.

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

    I don't think constraints matter at all in C ,n,m<=1000 doesn't make any difference in solution

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

      In some solutions it actually does matter.

      Example: 175929785 from ltunjic

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

        how does it matter? you can just create RRRRR....RRRR string just by appending R m times

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

          Right, but I still think problem would be little harder for beginners.

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

In Problem B, the checker log is telling me that I gave a wrong answer in test case #2 while my answer is the same as the output. As you can see in the submission, the 25th token is correct. Am I missing something? 176210112

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

    Your code is dereferencing the value of $$$a[n]$$$. This is undefined behaviour, and may have caused a WA any moment.

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

I faced some issue in the coprime problem. can anyone please identify the flaw in the code. Thanks in advance.

Your code here...
#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
    if(a==0){
        return b;
    }
    if(b==0){
        return a;
    }
    if(a==b){
        return a;
    }
    if(a>b){
        return gcd(a-b,b);
    }
    return gcd(a,b-a);
}

bool isCoPrime(int a, int b){
    if(gcd(a,b)==1){
        return true;
    }
    return false;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int j=n-1,i=n-1;
        bool found=false;
        int ans=0;
        while(i>=0){
            if(isCoPrime(arr[j],arr[i])){
                found=true;
                ans=i+j+2;
                break;
            }
            i--;
        }
        if(found){
            cout<<ans<<endl;
        }
        else{
            cout<<"-1\n";
        }
    }
    return 0;
}
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are not moving j.

    while(i>=0){ if(isCoPrime(arr[j],arr[i])){ found=true; ans=i+j+2; break; } i--; }

    In this loop you are not decreasing j.this approach is wrong according to me if you try with two loop then it will show TLE. see Editorial.

    check for: 1 2 3 6 according to your code ans should be 4 but real ans is 6 because 2 and 3 are coPrime so, 2*3 = 6.

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

Have a problem with G

176665365

but the test is really huge and I can catch the problem/

Maybe someone has the idea?

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

great！！！

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

Can anyone tell me what i'm ddoing wrong for problem G. Here is my submission i'd

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

In problem D (Coprime) , would anyone help me to understand that how its time comlexity becomes O(a2i (logai+n))

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

I guess I didn't understand F correctly...

The is the 10th test:

1
5
2 1 bb
1 2 b
2 3 b
1 2 c
2 3 bcdbweakpretests

Official answer is:

YES

YES

YES

YES

YES.

Why it isn't:

YES

NO

YES

NO

YES?

UPD: solved it

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

trash round

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

192675897 My code shows wrong in the 10th word. But I can't see the 10th word. It finished after the 6th. How can I find all test examples?

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

Can someone please explain B solution in Java?

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

In problem 1742D, I am getting my 1st test(5th array) wrong which is 31 instead of 10, also i don't know why 10 is the answer for the fifth array, as 15 and 16 are coprime also.

→ Reply