Educational Codeforces Round 130 Editorial
source link: http://codeforces.com/blog/entry/103835
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Educational Codeforces Round 130 Editorial
14 hours ago, # | BledDest has made the task "awoo's favorite problem" :| kinda weired. |
-
I prepared it and made the title a reference to this banger comment.
14 hours ago, # | Could any tell me why my approach to solving C is giving WA? https://codeforces.com/contest/1697/submission/160346935 My approach: => 1. Because we don't have ac or ca operations.
=> 2. Make s[i]=='b' and t[i]=='c' to s[i]='c' and t[i]='c' using bc operation via two pointer approach
=> 3. Finally you can remove characters which are equal i.e; s[i]==t[i] At this moment, we have all c's matched in both s and t Now we can match a's and b's using ab operation
|
14 hours ago, # | Is this code correct? Gives AC but just because of a single else break; it got hacked during contest. My rank went down from 2000 to 8k+. Had solved C in 14 mins. This shit hurts! Just missed a single else statement. 160439872 |
13 hours ago, # | can anyone please explain problem C ? |
13 hours ago, # | F's idea was brilliant. It's not hard to recognize it as a 2-sat problem, but I got stuck with "is $$$a_i$$$ equal to $$$x$$$?" and can't come up with the idea presented in the solution. Great problems overall. Thanks sir. |
13 hours ago, # | In the ask_character function, can we not directly input a char instead of inputting a string and then returning its first charachter? Asking cause I seen a string being inputted in someone else's submission too |
-
Reading a char can be awkward as you have to be careful about spaces / EOL. Reading a string makes it more reliable and simpler (and probably has close to no impact on performance due to small string optimisations).
12 hours ago, # | Can someone tell me how test #3 in problem B is generated? All other tests are fine, but test #3 alone seems to be quite an adversary to the dual-pivot quicksort which is used for the built-in primitive array sorting in java. What's more curious is that the built-in sorting algorithm switches to heap sort if it is too slow. I also tried to make a bad array for a bit via local machine and custom invocation, but it wasn't successful at all. |
Checkout my approach for Problem C: [AC code] -> 160454978
In contest -> (Did a super silly mistake in updating Fenwick tree, due to which I got a SILLY WA in contest!) Idea: I went backwards in string s, and checked if the characters mismatch, if it does, print "NO" if it's an 'a', as it cannot be swapped, else find the nearest 'b' or 'c' (pos) accordingly using set, and also check if there exists any other character between the current s[i] and the found pos, if it does, print "NO", else swap them, and move on (update the pos and fenwick tree as well)...In the end, just check if strings are equal... Time complexity: ~ O(N(log(N)) |
12 hours ago, # | C has two pointer and dp tag, can anyone explain how can we use two pointer and dp in c? |
for problem E Im using this fact that size of each component is at most 4 and use this to solve problem with another way One can prove or disprove this؟؟ |
-
I had just figured this out. It is entirely dependent on the 1st condition. Consider fixing the distance, and imagining the diamond of points around a given point equal to that distance. You can see that for two given points, if they are not on the same diagonal (same x + y or x — y), there can be at most two intersections of such diamonds and therefore at most two points that are equidistant to both of them, thus the max size is at most 4 if two are not on same diagonal. Obviously we cannot get more than 2 points all equidistant to each other that are on same diagonal. Lastly, you can find construction showing size 4 set is possible, therefore max size is 4.
11 hours ago, # | C is a very strange problem. Let me describe my method. We can replace "ab" with "ba", and replace "bc" with "cb". Firstly, the number of 'a', 'b' and 'c' must be equal in string $$$s$$$ and $$$t$$$. And if we remove 'b' from $$$s$$$ and $$$t$$$, the remaining string $$$s'$$$ and $$$t'$$$ should also be the same. This is because we can't change the relative positions of 'a' and 'c'. So lets extract all 'b' in $$$s$$$ and $$$t$$$. They must match one by one like this:
For a matched pair of 'b', where $$$s_i=t_j=$$$'b'.
The check can be done using prefix sum. |
11 hours ago, # | I don't put that much time into doing Codeforces contests — I am not professionally involved with programming, it is more like a hobby for me. But anyhow, I had been initially very pleased (since I am only a Newbie) during the contest when I had my solutions to A, B and C accepted. But then, during the hacking period, my solution to B was hacked. So, I was curious about what mistake I made. And now that I see the "official" solution to B described as merely "sorting the array and doing prefix sums" — which is what I did — my guess (which seems consistent with other comments) is that apparently by using one of the standard python built-in sort functions ("sorted"), it led to my solution exceeding the time limit. If that is indeed truly what happened (and maybe it wasn't?), that seems to suggest a significant problem on the Codeforces end in setting the time limits. |
-
Input/output time seems to be critical in your case. Refer to my submissions or https://codeforces.com/blog/entry/83441
-
Thanks! I very much appreciate learning the true explanation. As an outsider to these issues, I do find it interesting that on Leetcode, whose contests I regularly participate in, this — i.e., the slowness of Python in terms of input/output — doesn't appear to be much of an issue. Yes, there are times when Python's slowness does mean that a Python solution will not pass, in comparison to, e.g., a C++ solution. But I don't recall those differences being attributed to input/output issues (and thus they were not correctable by changing how participants using Python coded their input/output).
Anyhow, thanks again for teaching me how to try to avoid this issue in future Codeforces contests. It is certainly interesting and surprising, at least to me, to learn about this being an issue.
-
I think my solution for E is simpler and more intuitive ( I think it might be because I observed that the maximum number of points colored the same is 4 ) I'll copy my comment from the other post (sorry if you read it there too ^_^): Just did problem E. Awesome problem! First I noticed that the sizes of equal distance groups can only be 4 at most. Then I noticed that you just need to keep a list of all points of minimum distance from you. Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other. Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups. From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different]. dp size is n*n*2. Don't yet know its rating, but might be the highest rated problem I solved! The way I found the groups is easy. After adding point X itself to the list of points with minimum distance from X (for convenience), to be part of a group, all the neighbors (with minimum distance) must have the exact same set of neighbors! if and only if one of them isn't — you are not part of a group. this was a simply O(n) for loop. And this is not dfs as I'm only looking at neighbors! Code |
9 hours ago, # | Thank you sigma problemsetters for pretests in E! I really love submitting, getting AC on the last 7 minuites, FSTing, fixing it with one if statement in 2 minutes 33 seconds! It is obvious to me that if a problem includes case analysis the pretests should exclude specifically one case so you feel like an idiot! ORZ ORZ ORZ problemsetters. I liked the problem, it is just painful to perform like a 2520, getting +154, FSTing and realizing that if that was in the testcases, you had time to correct it. |
4 hours ago, # | include<bits/stdc++.h>using namespace std; void init_code() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int main() { init_code(); int n,q; cin>>n>>q; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } sort(arr,arr+n); int x,y; while(q--) { cin>>x>>y; int ans[x]; int j=0; int sum=0; for(int i=n-x;i<n;i++) { ans[j]=arr[i]; if(j<y) { sum=sum+ans[j]; } j++; } cout<<sum<<endl; } return 0; } Can anyone tell why this is giving TLE?? |
4 hours ago, # | Could Problem F be solved if k is 1e5? |
2 hours ago, # | Submission C Plz help me to debug this I am swapping the char when its not same |
75 minutes ago, # | why?????
|
67 minutes ago, # | Can anyone explain C i still don't get it |
-
go through each character one by one.
- if s[i] == t[i] ---> it's fine, leave it and go to next character.
else, string can be changed only if (s[i] == 'a'and t[i] == 'b') or (s[i] == 'b' and t[i] == 'c'). for any other combination you can't arrive to t.
now let's take eg: s[i] == 'a' and t[i] == 'b', now I found nearest 'b' that is mispalced in s, let it be at index j.
key point to note is there shouldn't be any 'c' between index i and j, because if there is 'c' in between you can't swap 'a' and 'b'. If there is no 'c' then you can simply write s[i] = 'b' and s[j] = 'a'
I checked if there is any c in between by prefix sum method and I maintained a que for a,b,c seperately which has misplaced indexes of a,b,c respectively and took out first indexes of a and b ques, if i could swap them both.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK