By Vladosiya, history, 2 weeks ago,

1980A - Problem Generator

Tutorial
Solution

1980B - Choosing Cubes

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1980C - Sofia and the Lost Operations

Idea: senjougaharin Prepared by: Gornak40

Tutorial
Solution

1980D - GCD-sequence

Idea: myav Prepared by: myav

Tutorial
Solution

1980E - Permutation of Rows and Columns

Idea: senjougaharin Prepared by: senjougaharin

Tutorial
Solution

1980F1 - Field Division (easy version)

Tutorial
Solution

1980F2 - Field Division (hard version)

Tutorial
Solution

1980G - Yasya and the Mysterious Tree

Idea: Gornak40 Prepared by: Gornak40

Tutorial
Solution
• +56

 » 2 weeks ago, # |   +4 Why is system testing so slow these days?
•  » » 2 weeks ago, # ^ |   +8 Because there are so many people participating in contests
•  » » 13 days ago, # ^ | ← Rev. 2 →   +7 I guess it's due to the horrible 150+ tests of problem C... Most solutions took ~500ms on each test, which means that everyone who passed problem C(a large amount!) will take ~75 seconds to be judgedSometimes I wonder if it would be better to include anti-unordered data in the pretests. This might help avoid the pointless but time-consuming hack judging?
•  » » » 13 days ago, # ^ |   -8 I guess they shouldn't add all the the hacks to the main test cases. The C problem has 150 test cases but most of them are for Unordered Map. They can try ignoring similar purposed hacks by categorizing them or something.
•  » » » » 13 days ago, # ^ | ← Rev. 4 →   -8 Unordered map is constant time right, why is that giving TLEIs it because the constant is higher for the test case. Clarify if you can why this code gave TLE 263947136
•  » » » » » 13 days ago, # ^ |   +8 Yeah so the average case of an unordered map is O(1) for accessing data, but due to collisions the worst case for accessing data is O(N), so the solution becomes O(N^2) instead of O(N). You can read this article- https://codeforces.com/blog/entry/62393
•  » » » » » » 13 days ago, # ^ |   -8 Thanks
•  » » » » » 8 days ago, # ^ |   0 its because unordered_map uses hashing and in worst case hashing haa O(n) time complexity,thats why its giving tle. use map always in place of using unorderd_map
•  » » » » 13 days ago, # ^ |   -8 How does one get to know that a test is for unordered map?
•  » » » » » 13 days ago, # ^ |   0 Most of these hacks use a pretty standard generator, it is designed/works in a way that it hacks all the solutions using some form of a hash table, be it an unordered map ,unordered set or a python dictionary.
 » 2 weeks ago, # |   -8 C took 100 lines of code for me :(
•  » » 2 weeks ago, # ^ |   +1 It could be done in 20 lines ig
•  » » 13 days ago, # ^ |   +12 Here is a much simpler solution for Problem C. int n; cin>>n; int a[n],b[n]; read(a,n); read(b,n); int m; cin>>m; int d[m]; read(d,m); if(count(b,b+n,d[m-1])==0) no; map diff; for(int i=0;i
 » 13 days ago, # | ← Rev. 2 →   +1 E could be easily solved using set of sets: Solution Link
•  » » 13 days ago, # ^ |   0 Why does it work?
•  » » » 13 days ago, # ^ |   0 It is just different implementation of same logic as in editorial.
•  » » 12 days ago, # ^ |   0 bro we wrote literally the same code. :)
•  » » » 12 days ago, # ^ |   0 wait for the next div3 4 to participate again
•  » » » » 12 days ago, # ^ |   0 what you gonna do about it ? BOMB me ?? MOHAmmada LMAO
•  » » » » » 11 days ago, # ^ |   0 Be respectful bro...
•  » » » 12 days ago, # ^ | ← Rev. 3 →   -10 .
 » 13 days ago, # |   0 testcasesforces
 » 13 days ago, # |   0 can someone explain why only checking the rows is not enough in E.
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 For example consider the test case of 3×3 Matrix asA : 1 2 34 5 67 8 9B :2 3 14 5 67 8 9We cannot transform A to B using any row or column swaps
 » 13 days ago, # | ← Rev. 3 →   +8 F is Mike's idea :OBut I think you can't avoid sort so the time complexity can't be $\mathcal O(n)$.My sol for F:Find all corners. Remove all corners and run the algorithm for a second time to get a second group of corners.A fountain becomes a new corner (after one of the old corners is removed) if and only if: it is among the second group of corners; and it is covered by only one corner. A corner $(u,v)$ covers the range {$(x,y)|x\in[1,u],y\in[v,m]$}.A fountain becomes a new corner after removing the corner covers it.It's easy to calculate change of area now.264008397(Why $\{$ -> ${$)
•  » » 13 days ago, # ^ |   0 Do you know why my code for F1 doesn't work?264033779
•  » » » 13 days ago, # ^ |   +1 You can't find corners correctly in this way.
•  » » » » 13 days ago, # ^ |   0 Can you please elaborate on what you mean? Thanks!
•  » » 13 days ago, # ^ |   0 the time complexity can't be O(n) Radix_Sort by ((int64_t)x << 32) | (INT32_MAX - y)
•  » » 13 days ago, # ^ |   +6 The most important thing was to explain that the part after sorting is linear. (and my memory so short that I forgot about sorting by the end of tutorial)
 » 13 days ago, # |   0 Can any one help me to understand problem c.? And send solution easly
•  » » 13 days ago, # ^ |   +5 Our goal is to find whether, given a list of sequential operations, an array could be translated into other or not.The only operations that matter here are when an element is changed between a[i] -> b[i]. We ensure all such operations (say, d_k) are actually present in d.Since d is also sequential, for any successful transformation, all d_k must be present at the end of d. As for a simple solution, kindly refer one from _Runtime__Terror_ a bit above in this discussion. Thanks.
 » 13 days ago, # | ← Rev. 2 →   0 why I have to remove a[i] in problem d? can someone pls explain with one example.
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 let b be an array and for each index i in b :b[i] = gcd(a[i],a[i+1]) .when you remove a[i] the array a changes => array b changes
 » 13 days ago, # |   +1 dang,how much longerr would the system testing go.
 » 13 days ago, # |   0 Can anyone tell me, in C, why dm must be present in b? I read the question 50 times, still didn't understood.
•  » » 13 days ago, # ^ |   0 if not , the (index) you apply dm at in the last operation will differ from b[index] as dm != b[t] for any (t) ( if dm is not present in b )
•  » » » 13 days ago, # ^ |   0 Thank You!
•  » » 13 days ago, # ^ |   0 since you have to apply all operations in the order they are given, then dm will always need to be applied last and there is no following operation that can replace it. Therefore it should appear in the final array
•  » » » 13 days ago, # ^ |   0 Thank You!!
 » 13 days ago, # |   +1 YES NO forces
 » 13 days ago, # |   0 Can someone explain why my submission 263986368 on problem c got a tle but something like this 263962017 didn't?
•  » » 13 days ago, # ^ | ← Rev. 3 →   0 same, now i just read that unordered_map with weak hash fxns can cause collisions in testcases and end up in O(n^2), it was safe to use normal map in this problem
•  » » » 13 days ago, # ^ |   0 Both solutions which I've mentioned use Hashmap.
 » 13 days ago, # |   0 used unordered map in Problem C and got TLE in system tests and delta changed to -ve.
 » 13 days ago, # |   0 Got hacked on C, i guess its newbie time
 » 13 days ago, # |   0 Need Help!! I am beginner, there are times when i feel my approach is correct based on my intuition but i fail to prove it why, in such cases what should i do, try implementing it in code or give some more time to prove my intuition?
 » 13 days ago, # | ← Rev. 2 →   0 problem d, solution 1 — 263972949 failed system test (TLE), solution 2 — 264171599 passed all the tests, code — same in both letter by letter, only difference — solution 1 submitted on Python3 while solution 2 submitted on PyPy3, result — got a "-1" in place of a "+"
 » 13 days ago, # |   +3 Problem C solved in C, coincidence or intentional?
 » 13 days ago, # | ← Rev. 3 →   0 Can someone explain why my submission 263980440 on problem C got TLE but this submission 264168646 didn't?
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 count in multiset is briefly O(n)
•  » » » 13 days ago, # ^ |   0 The time complexity of the count() operation in a multiset in C++ is O(log(n) + k), where n is the size of the multiset and k is the number of occurrences of the element being counted. I think TLE occurs when there is a testcase where k is very large.
•  » » » » 13 days ago, # ^ |   0 Yes, so effectively it is O(n). Got hacked for the same reason T_T
 » 13 days ago, # |   0 E can be done with Zobrist Hashing 264181127.
 » 13 days ago, # |   0 For problem E on the basis of the solution, at the end, after sorting both matrix A and B on the basis of rows as well as on the basis of columns, both should turn out to be equal then only our answer is YES. So to simplify my implementation i took the sum of each rows in A and in B in two vectors and finally after sorting checked if both come out to be same and i did same for the columns also, since the sum property should also satisfy since the numbers are unique but i am getting WA on test 2. Can anyone explain what's wrong with my given implementation. I am not able to think on which test case my implementation will fail. please help 264209981
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 unique numbers does not guarantee a unique sum. (1,4) snd (2,3) have the same sum value, it is bound to give you wrong answer.
 » 13 days ago, # |   0 came up with a wierd soln for E https://codeforces.com/blog/entry/130129
 » 13 days ago, # |   0 When I submitted problem 3 in the contest it showed accepted but right now it is showing TLE on test 10. Can anyone please explain why does this happen ? It has happened with me once before. (I am new to codeforces, so i don't know about all the rules)
•  » » 13 days ago, # ^ |   0 You got hacked. (your code failed system testing) This is probably because you used unordered_map or something in your code. See the note at the end on editorial for C
•  » » » 12 days ago, # ^ |   0 thanks
 » 13 days ago, # |   0 Video Editorial for Dhttps://youtu.be/O2-wL5OXyYc
 » 13 days ago, # |   0 When is contest rating generally updated after the contest and in how many days editorial of the contest come out?
 » 13 days ago, # |   0 Resources to learn trie?
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014This has a good explanation
•  » » » 13 days ago, # ^ |   +3 thanks bro
 » 13 days ago, # | ← Rev. 2 →   0 Can someone please tell me the mistakes in my solution to problem E (https://codeforces.com/contest/1980/submission/264239803)? I have used a simple sorting-based method.
 » 12 days ago, # |   -9 In problem F2 why the following code isn't giving TLE? What is time complexity of the loop for given problem ? for(int i = 1; i <= k; ++i){ auto e = a[i - 1]; if(ans[idx[e]] == 0)continue; int tot = total[i - 1]; int cr = cur[i - 1]; int lst = last[i - 1]; for(int j = i + 1; j <= k; ++j){ auto ee = a[j - 1]; if(cr > ee.y){ tot += (cr - 1) * (lst - ee.x); cr = ee.y; lst = ee.x; } if(ans[idx[ee]] == 1){ ans[idx[e]] = tot - total[j]; break; } } } 
•  » » 12 days ago, # ^ |   0 The complexity is k^2 which obviously TLEs for k <= 2*10^5
•  » » » 12 days ago, # ^ |   +3 That was accepted. But now I got it why. Because we are only checking points between corners the time complexity will be O(n).
 » 12 days ago, # |   0 D was talking about removing i-1 i or i+1 then why is it removing the from 0 to i or 0 to i-1 or 0 to i+1. If it is works the same then can someone explain me how?
 » 12 days ago, # |   0 In Problem E: Suppose for all those test cases which have the answer "YES", we are also asked to output the possible actions (not necessarily the minimum) in the form: i) r a b -> swap row a with b. ii) c a b -> swap column a with b. Then, what would the approach be for this one?
•  » » 12 days ago, # ^ |   0 Good idea! I still confused this way , which found a deatialed path to transform matrix B , from contest time to now.
 » 12 days ago, # |   0 Problem E is flexible and great mind!The Tuorial only introduce solved way.It's so upset>_<.Can Anyone explain that detailed the reason of way >_< ?
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 you can check mine it is relatively easy i first checked row wise. there i made a map for every row after sorting it and then checked for every sorted row in b if it existed in the original map. If it doesnt exist then no() else we check further .similarly for columns https://codeforces.com/contest/1980/submission/264333535 .
•  » » » 12 days ago, # ^ |   0 Thank you for your reply! I incline to figure out how transform A into B , such as proof. The tutorial is understood by me , but i still don't why , specifically.
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 I used multiset , which is slower than your way. I think your idea better than mine!
 » 12 days ago, # |   0 can someone explain the editorial code of C
•  » » 12 days ago, # ^ |   0 In my perspective , it's maybe complex for you. https://codeforces.com/contest/1980/submission/264339347 It's my submission. I hope this hopeful for you!
•  » » » 11 days ago, # ^ |   0 I Was confused because of the compare function because it's not bool but turned out it's just normal sorting
 » 12 days ago, # |   +5 Editorial code for C can also be hacked because qsort worst case is $O(n^2)$: https://codeforces.com/contest/1980/hacks/1033165 Code// Hacking quicksort solutions during competitions // Author: https://codeforces.com/profile/halyavin #include using namespace std; vector anti_sort(size_t n) { vector res(2 * n + 1); iota(res.begin(), res.end(), 0); for (size_t i = n; i-- > 0;) { swap(res[2 * i + 1], res[i + n]); } for (auto &x : res) x++; return res; } int main() { cin.tie(0)->sync_with_stdio(0); vector gen = anti_sort(2e5 / 2 - 1); int n = gen.size(); cout << "1\n" << n << '\n'; for (int i = 0; i < n; i++) { cout << gen[i] << " \n"[i == n - 1]; } for (int i = 0; i < n; i++) { cout << gen[i] << " \n"[i == n - 1]; } cout << n << '\n'; for (int i = 0; i < n; i++) { cout << gen[i] << " \n"[i == n - 1]; } } Unexpected verdict means that one of the solutions marked on Polygon as Correct can't pass this test. Vladosiya Gornak40
 » 12 days ago, # |   0 I have no ideas why I got wrong answer on problem G: https://codeforces.com/contest/1980/submission/264341580. My solution is the same as editorial.
 » 12 days ago, # |   0
 » 11 days ago, # |   0 Can somebody explain why it doesn't give TLE? I tried fixing each using rowswap and colswap and checked in the end if both matrices are equal or not. Submission
 » 11 days ago, # |   0 I am calculating that same sum of row and columns present in the array B or notI am unable to find where it is failing. Can you tell some test case where it fail.
•  » » 11 days ago, # ^ |   0 I don't think sum is an ideal hashing method. 1 2 3 1 2 3 6 4 5 1 2 3 5 6 4 Read YES, expected NO.Hope it helps:)
 » 10 days ago, # |   0 why it is giving wrong answer for problem D.
 » 10 days ago, # | ← Rev. 2 →   -8 Can anyone help why my code for 1980G - Yasya and the Mysterious Tree is not working?264619004264609607I am happy if any of the above two works.
 » 10 days ago, # | ← Rev. 2 →   0 in problem E I have reached till a point that I want to check if one vector is a permutation of another and all of them must be shifted the same amount is this correct or just give up
 » 8 days ago, # |   +12 A O(nm) solution for E that uses xor hashes:
 » 5 days ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } In G why do you need to remove the x[a] first in order to get the result?
»
3 days ago, # |
0

can anyone point out what went wrong in my code problem c ;

# include <bits/stdc++.h>

using namespace std; int original[210101] ; int found[210101] ; int diffs[210101] ; int modifier[210101] ; int main() { int t ; cin >> t ; while (t--) { int n ; cin >> n ; for (int i = 0 ; i < n ; i++) cin >> original[i] ; ///// int j = 0 ; for (int i = 0 ; i < n ; i++) { cin >> found[i] ; if (original[i] != found[i]) { diffs[j] = found[i] ; j++ ; } }

int m ;
cin >> m ;
for (int i = 0 ; i < m ;i++)
cin >> modifier[i] ;
/////////
int hero = 0 ;
for (int i = 0 ; i < n ; i++)
{
if (found[i]==modifier[m-1])
{
hero++ ;
break ;
}

}
sort(modifier , modifier+m) ;
sort (diffs , diffs + j) ;
int k = 0 ;

if (hero==0)
cout << "nO" << endl ;
else
{
for (int i = 0 ; i < m ; i++)
{
if (modifier[i]==diffs[k])
k++ ;
if (k==j)
break ;
}
if (k==j)
cout << "YES" << endl ;
else
cout << "NO" << endl ;
}

}
return 0;

}

 » 36 hours ago, # |   0 Did someone solve problem G using Centroid Decomposition?
 » 32 hours ago, # |   0 Solved E via union find, was way more intuitive for me, but basically the same concept as AC.Submision: 265923059 https://codeforces.com/contest/1980/submission/265923059