### flamestorm's blog

By flamestorm, 6 months ago,

Thanks for participating!

1742A - Sum

Idea: flamestorm

Tutorial
Solution

1742B - Increasing

Idea: mesanu

Tutorial
Solution

1742C - Stripes

Idea: flamestorm

Tutorial
Bonus
Solution

1742D - Coprime

Tutorial
Solution

1742E - Scuza

Idea: mesanu

Tutorial
Solution

1742F - Smaller

Idea: SlavicG

Tutorial
Solution

1742G - Orray

Idea: SlavicG

Tutorial
Solution
• +58

 » 6 months ago, # |   +7 B was just a few lines with the help of STL :D (Submission: 176051852)
•  » » 6 months ago, # ^ |   0 Nice!
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Or int n; cin >> n; vector a(n); for(auto &x : a) cin >> x; cout << (set(a.begin(), a.end()).size()==a.size()?"YES":"NO") << '\n'; which I find even simpler.
•  » » 5 months ago, # ^ | ← Rev. 3 →   -8 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
 » 6 months ago, # | ← Rev. 2 →   0 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
•  » » 6 months ago, # ^ |   0 Look at the title,some horizontal rows have been painted red, and some vertical columns have been painted blue.
•  » » » 6 months ago, # ^ |   +1 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 :'(
•  » » » » 6 months ago, # ^ |   0 me too!!
•  » » » 6 months ago, # ^ |   0 now i understand,thx,i ignore the difference between "some" and "all"
•  » » 6 months ago, # ^ |   +9 Consider this caseBBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRRAnswer : 'R' Output : 'B'
•  » » » 6 months ago, # ^ |   0 some horizontal rows have been painted red, and some vertical columns have been painted blue
•  » » » » 6 months ago, # ^ |   0 some horizontal rows have been painted red, and some vertical columns have been painted blue,it means not all points of a color are painted horizontal or vertical,so the case is legal
•  » » » 6 months ago, # ^ |   0 thank u :) now i understand!
•  » » 6 months ago, # ^ |   0 I was also coding like that.. like R, B in both direction but it was failing.175991481. and at last I was that logic in given test cases.... and cracked it... this was not given anywhere in question 176049904
•  » » 6 months ago, # ^ |   0 During the contest, I thought that the rows and columns it said refer to the rows and columns in the sample...
 » 6 months ago, # |   0 I have the same logic for problem C as mentioned in the tutorial but it fails on tc 2, My submission is https://codeforces.com/contest/1742/submission/176081297 . Could anyone please take a look at why this is failing.
•  » » 6 months ago, # ^ |   0 your logic is correct but when you are checking rows ch should be only R and while checking column ch should only be B. ****this**** is the corner case.
 » 6 months ago, # |   +13 for problem C, many of us missed this case :( BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB BBBBBBBB RRRRRRRRAnswer : 'R' Output : 'B'
•  » » 6 months ago, # ^ |   0 Oh damn!! thanks a lot!!
•  » » 6 months ago, # ^ |   0 Thank you
•  » » 6 months ago, # ^ |   0 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?????
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 6 months ago, # ^ |   0 Can you explain this testcase?? This would be really helpful. Even i have a doubt in the question
 » 6 months ago, # |   0 why is my 176088793 getting WA on 11 (problem D)
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 I got TLE in problem E. My submission is 176039360 . How can I improve this?
•  » » 6 months ago, # ^ |   +3 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
•  » » » 5 months ago, # ^ |   0 Hello Bro, can you tell we why we have subtracted prefmax.begin() in the upper bound function?
•  » » » » 5 months ago, # ^ |   0 Upper bound function returns an iterator. But I need the index of the array. That is why I need to subtract the initial address of the array so that I can find the index. To know more and learn more about this you can follow this.
•  » » » » » 5 months ago, # ^ |   0 thank you very much bro :)
•  » » 6 months ago, # ^ |   0 use binary search for finding the element. Time complexity will be better in that case. Since the time complexity of the binary search is O(log N) and that of linear search is O(N). Also, you can apply binary search since your lower array is non decreasing one.
•  » » 6 months ago, # ^ |   0 try to learn about binary search and Upper_bound function.... That would help you to solve these types of query related problems in a feazeble time...
•  » » 6 months ago, # ^ |   0 inspite of brute_force you should use binary_search
 » 6 months ago, # |   0 I got TLE on Problem D. Not sure why. How can I improve this solution
•  » » 6 months ago, # ^ |   0 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 ].
•  » » 6 months ago, # ^ |   0 Handle duplicates and number 1. Since if 1 is present then gcd with any element will be (1,N)=1 and also do not find gcd of the smaller index. Only find gcd if the index sum of elements is greater than that of previous sum(store sum of index). My solution: Problem D
•  » » » 6 months ago, # ^ |   0 Thanks it helped me
 » 6 months ago, # |   +5 Video Editorial for Chinese：Bilibili
•  » » 6 months ago, # ^ |   0 Is that Chinese youtube?
•  » » » 6 months ago, # ^ |   0 YES，and better than YouTube
 » 6 months ago, # |   0
 » 6 months ago, # |   +6 I think there is an easier way to implement the algorithm in G's tutorial. 176054281
 » 6 months ago, # |   +4 Weak pretest in problem F.
•  » » 6 months ago, # ^ |   0 Yeah, got an overflow error. I think that should have been accounted for in pretests.
 » 6 months ago, # | ← Rev. 2 →   0 Thank you for such a great contest and for a great editorial
 » 6 months ago, # | ← Rev. 3 →   0 I got wrong on Problem E. Not sure why. How can I improve this 176044919
•  » » 6 months ago, # ^ |   0 try to think about it by easiest way like if u want way how i solve itjust store in array call freq what is biggest number until now in i and after it prefix the main array and BS about it answer in freq array example 1 2 1 5 freq >> 1 2 2 5 arr>> 1 3 4 9 u will BS about query in freq array by ur way and handle it , after that output the matchable index from arr
•  » » » 6 months ago, # ^ |   0 thx,i will try.
 » 6 months ago, # | ← Rev. 4 →   0 I am getting the Wrong answer for F on test case 2 .. my submission- hereplz someone help me out ::) I got my mistake
 » 6 months ago, # | ← Rev. 5 →   0 **Just Simple G qn solution.** **nathing try to sort an array by the maximum **OR**.** code: ll num=0; bool cmp(ll x,ll y) { return ((num | x ) > (num | y) ); } void solve() { num=0; ll n; cin>>n; ll v[n]; for(ll i=0;i> v[i]; for(ll i=0;i
•  » » 6 months ago, # ^ |   0 can u explain a bit more please! :)
 » 6 months ago, # |   0 sadly, i misread the "OR" as "XOR" and failed to ak
•  » » 6 months ago, # ^ |   0 oh bad luck
•  » » » 6 months ago, # ^ |   0 it's more like oh bad concentration
 » 6 months ago, # | ← Rev. 2 →   0 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 validIs it correct ?
 » 6 months ago, # | ← Rev. 2 →   0 Hey flamestorm,In problem C, the valid input must contain exactly one of theses situations:1- Have one or more rows full of R's2- Have one or more columns full of B'sotherwise, the input is invalid Is it correct ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -6 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... 
•  » » » 6 months ago, # ^ |   +1 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
 » 6 months ago, # |   0 I got TLE in F question for Test Case #2, any ideas/hints how can I improve the code? submission
•  » » 6 months ago, # ^ |   0 You need to save the count of every character, as k can be 10^5 every time and there are 10^5 queries the size of the string can exceed 10^10. You can check out my submission : https://codeforces.com/contest/1742/submission/175994173
 » 6 months ago, # |   0 can anybody help with the error in my code (Submission :176138148)
 » 6 months ago, # | ← Rev. 2 →   0 Is there any solution to solve D. Coprime better than O(E*E) where E is the maximum possible element. Can it be solved in O(N)?
 » 6 months ago, # |   0 The solution of problem E is implemented very nicely. Thanks for the editorial.
•  » » 5 months ago, # ^ |   0 Hello Bro, can you tell we why we have subtracted prefmax.begin() in the upper bound function?
 » 6 months ago, # |   0 problems D has some bugs. see https://codeforces.com/blog/entry/107979
•  » » 6 months ago, # ^ |   0 I cannot believe it
 » 6 months ago, # | ← Rev. 2 →   0 Problem D. Who knows, why this solution is wrong? (fails on 11th test, see submission).176022793
•  » » 6 months ago, # ^ |   0 Basic idea: gcd(a1, a2, a3) = gcd(a1, gcd(a2, a3)); so I find first number from the right, for which gcd([number, …, an]) = 1, and then find first ai from right, for which gcd(number, ai)=1.
•  » » 5 months ago, # ^ |   0 Take a look at Ticket 16350 from CF Stress for a counter example.
 » 6 months ago, # |   0 I can't understand the concept of the problem "F" solution. Can anyone explain me??
 » 6 months ago, # |   0 The empty line between each test case of problem C cost me 50 minutes. Since the input box has different colored stripes for any two consecutive inputs, there was no need for that empty line. I thought reading the input section is a waste of few seconds. I should have read the input section carefully.
 » 6 months ago, # |   0 176168579 Please help I am getting WA on test 10 in problem F but I think that my output is correct
•  » » 6 months ago, # ^ |   0 me wa in tc10 too, read statement carefully: Alperen has two strings, s and t which are both initially equal to "a". Just add 2 lines mp1['a']++, mp2['a']++ your AC code: https://codeforces.com/contest/1742/submission/176174906
•  » » » 6 months ago, # ^ |   0 Got this now. Thanks
 » 6 months ago, # |   +4 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 .
•  » » 6 months ago, # ^ |   0 Help him pleez
•  » » 6 months ago, # ^ |   +1 Help him, he deserves achieving pupil :(
• »
»
6 months ago, # ^ |
+1

Agree

# Help_Rida

•  » » 6 months ago, # ^ |   +1 that is not fair, please help him .
•  » » 6 months ago, # ^ |   +1 it is unfair not to rejudge his submission
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 totaly agreeeehiz frendz need mental aid
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 I don't think constraints matter at all in C ,n,m<=1000 doesn't make any difference in solution
•  » » » 6 months ago, # ^ |   0 In some solutions it actually does matter.Example: 175929785 from ltunjic
•  » » » » 6 months ago, # ^ |   0 how does it matter? you can just create RRRRR....RRRR string just by appending R m times
•  » » » » » 6 months ago, # ^ |   0 Right, but I still think problem would be little harder for beginners.
•  » » » » » » 4 months ago, # ^ |   0 Using n,m<=1e3 . Even a O(n^2) solution can pass ,still the approach will remain same
 » 6 months ago, # | ← Rev. 2 →   0 Hey [user:flamestorm]I submitted the solution of D during contest time. During the contest it got AC but after system test it is still in queue. Why so? It's not also counted in my solution. It just got skipped. What is the reason for that? [submission:176039715]
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   -8 Your code is dereferencing the value of $a[n]$. This is undefined behaviour, and may have caused a WA any moment.
•  » » 5 months ago, # ^ |   0 bro why already decide the size of your array , and after initialization you made mistake , that's why you are getting WA , before solving these problems just recall//revisit on the basics of c++ , and then solve problems ,good luck
 » 6 months ago, # | ← Rev. 2 →   0 Can dp be used in problem E?
•  » » 5 months ago, # ^ |   0 it's basic question we can't use dp because the range of question is 10^9 where array limit is only about 10^6 or you can use map to save previous element but searching in map complexity is log n where we can search for the same in input in same complexity with binary search. so dp can only increase your space complexity and code complexity so yeah dp can be use in problem e but its useless to use it. This is my thinking maybe i am wrong.
 » 6 months ago, # |   0 In problem-G for test second test case :input : 5 1 2 3 4 5 5 my_outupt: 5 5 2 5 4 3 1prefix or of input: [5, 5, 7, 7, 7, 7, 7]prefix or of myout:[5, 5, 7, 7, 7, 7, 7]isn't it a correct output. jurys output: 5 2 1 3 4 5 5 with prefix_or: [5, 7, 7, 7, 7, 7, 7]if my output is not correct then for input : 5,2 the accepted output is 5,2 with prefix_or [5,7] and [5,7] . so what is the problem actually wants . could any one please help? Thank you.
 » 5 months ago, # |   0 anyone please explain 4 solution
 » 5 months ago, # |   0 can anyone help me i don't know what i'm doing wrong here 176423898 in question c stripes
 » 5 months ago, # | ← Rev. 2 →   0 I solved C by getting the 8x8 array as a string input line by line and querying each line of input. For example, if a line is equal to 'R' 8 times as in "RRRRRRRR", then the last stripe painted was red, i.e R. Because if there's even one row of full red paint, it becomes futile for the column to ever be the last stripe painted. Here is my solution reference (C#): 176457546
 » 5 months ago, # |   0 I faced some issue in the coprime problem. can anyone please identify the flaw in the code. Thanks in advance. Your code here... #include 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 arr(n); for(int i=0;i>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<
•  » » 2 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Have a problem with G176665365but the test is really huge and I can catch the problem/Maybe someone has the idea?
 » 5 months ago, # |   0 Hey can anyone explain me this one-liner python code for 1742B? for s in[*open(0)][2::2]:print('YNEOS'[len(a:=s.split())>len({*a})::2]) 
•  » » 5 months ago, # ^ |   0 Ok I think I got it![*open(0)] : here 0 is file descriptor for stdin. So every line of stdin is put into list.[2::2] : Probably just taking the array of n into consideration.'YNEOS'[0::2] = YES 'YNEOS'[1::2] = NO, so if the condition len(a:=s.split())>len({*a}) is true then NO else YES.The condition itself is comparing the length of input array and set of the array elements (by {*a}). If all the array elements are unique then the condition is false, hence YES. But if there is repeating elements in the array, then the length of the set becomes less than the length of array, hence NO.
»
5 months ago, # |
0

D. Coprime：

# include

using namespace std; int gcd(int a,int b){ if(b == 0) return a; return gcd(b,a%b); } int main(){ int t; cin >> t; while(t--){ int n; int a[200005]; cin >>n; for(int i =1; i <= n; i++){ cin >> a[i]; } int c =a[1]; for(int i =2; i <= n; i++){ c = gcd(c, a[i]); } if(c!=1){ cout << -1<<endl; continue; } c = a[n]; int ans =0; for(int i =n-1; i >= 1; i--){ c = gcd(c, a[i]); if (c==1){ for(int j = n; j >= i+1;j--){ if(gcd(a[i],a[j])==1){ ans = i+j; break; } } } if(ans!=0)break; } cout << ans<< endl; }

return 0;


} Who can help me?Why my test 1 is wrong?

 » 5 months ago, # |   0 D, why am I getting TLE in 4th Test case? 176940826
 » 5 months ago, # | ← Rev. 3 →   0 can anyone please help me in debugging this code for problem C, i am not getting the correct output at one of the testcases.my submission : 177701574 https://codeforces.com/contest/1742/submission/177701574
•  » » 5 months ago, # ^ |   0 Take a look at Ticket 16377 from CF Stress for a counter example.
•  » » » 5 months ago, # ^ |   0 Thanks i modified a little but still i m getting error at one of the newtestcase new submission :https://codeforces.com/contest/1742/submission/178271786
•  » » » » 5 months ago, # ^ |   0 Well, you can always purchase a subscription if you need more help. Your new submission fails on Ticket 16379
•  » » » » » 5 months ago, # ^ |   0 Okay, thanks i didnt know about it
 » 4 months ago, # |   0 cant Problem E be done in this way ?We first calculate the upper bound of each K in the array a Then ans = prefix_sum[location of upper_bound of K — 1]Please help me if I am getting something wrong
 » 4 months ago, # |   0 great！！！
 » 3 months ago, # |   0 Can anyone tell me what i'm ddoing wrong for problem G. Here is my submission i'd
 » 2 months ago, # |   0 In problem D (Coprime) , would anyone help me to understand that how its time comlexity becomes O(a2i (logai+n))
 » 2 months ago, # | ← Rev. 2 →   0 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:YESYESYESYESYES.Why it isn't:YESNOYESNOYES?UPD: solved it
 » 2 months ago, # |   0 trash round
 » 7 weeks ago, # |   0 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?
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16727 from CF Stress for a counter example.