### fcspartakm's blog

By fcspartakm, history, 5 years ago, translation,  Tutorial of Codeforces Round #451 (Div. 2) div2, 451, Comments (65)
 » Is there any solution for F without using hashing/probabilistic approaches?
•  » » Big integer types
•  » » » That should be TLE as it is O(n^2)
•  » » Well, you can get 100% right answer by brute-force checking after the hashes match, and that allows the hash to be wrong a few times, because then you still won't get a TL... ofc that still uses probabilities ;(
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Yeah, that's indeed the actual (and almost never used) Rabin-Karp algorithm. First time that I used it (with the O(n) check each time hash collisions occurred).
•  » » 5 years ago, # ^ | ← Rev. 2 →   We can delete some variants (if len1==len2 and len3=len1+1, then 1st digit in third number is to be 1, if len1==len2==len3 then first digit in first number + first digit in second nubmer is to be not bigger than first digit in third number and so on (look at my code to find more dependencies)). Then we should check the other situations. Just iterate in our strings (like long arithmetic) and try to get third number. If we can do it, just print the answer. I'm not sure, if this approach is good, but it can pass all the tests. Also I can't prove it, but it so obviously that too many combinations (len1, len2, len3) is not considered in this solution. This is my solution and sorry for my bad English.
 » 5 years ago, # | ← Rev. 3 →   How many people used 'exgcd' in 898B ? ...
•  » » I used it,but failed
•  » » » After the contest I realized that I was thiking too much...
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   so do I...I though brute force will get TLE btw somenoe know how to solve by exgcd?
•  » » » » » you can check my submission
•  » » » » » » Nice and clean code dude (y)
•  » » I used and got AC.
•  » » » I exceed time limited at 40th test,,,,,,
•  » » +1 takes me quite a time to code...
•  » » » me too.
•  » » I used and accepted the problem
•  » » 5 years ago, # ^ | ← Rev. 2 →
•  » » 5 years ago, # ^ | ← Rev. 2 →   i pondered over a dp solution too much and constantly got NZEC(stack overflow) didn't realise that it would work out so easily
•  » » I used it, my solution in Python — http://codeforces.com/contest/898/submission/33300359
 » 5 years ago, # | ← Rev. 2 →   For problem E. My code gives correct input on my system but wrong on codeforces. for 1st test case on my system it gives 2 as output. On server it's giving 0. http://codeforces.com/contest/898/submission/33309260edit: It gives 2 on codechef as well.
•  » » you have declared "s" twice , and there can be more bugs in your code. on my machine it gives 0 as output
•  » » » I understand that's a wrong practice but shouldn't change the output as the one inside main must be considered.
 » An alternative solution for E: let f(x) be the minimum number of operations needed to make x a square number, and let g(x) be the minimum number of operations needed to make x a non-square number. We can sort the input array a using the following comparator: a[i] <= a[j] if and only if f(a[i])-g(a[i]) <= f(a[j])-g(a[j]). Then, in the optimal solution, the first n/2 smallest numbers in the resulting order will be transformed to square numbers while the remaining n/2 largest numbers will be transformed into non-square numbers, so the result is (sum i=1 to n/2: f(a[i])) + (sum i=n/2+1 to n: g(a[i])) for the sorted (using mentioned above comparator) array a .
•  » » My solution here[submission:33309059] uses a greedy, sort for min distance to square, then claculate the first half as squares and the other as non-square sort for min distance for non-square and sum like before but in reversed orderthe solution is the minimun of the two previous
 » Why E is so easy? :D
•  » » I wrote a pretty easy solution, but it gives WA on testcase 13? Plz can u tell me my mistake?- http://codeforces.com/contest/898/submission/33306957Thanks in advance
•  » » » In the first place you don't need double, they bring bugs. You can just put the sqrt into an integer. Then you see if the sqrt(a[i])*sqrt(a[i]) == a[i] it means that a[i] is a perfect square otherwise it's not.
•  » » »
•  » » » » Yeah, double can bring precision issues,but i took care of that by adding a safe offset of 0.01. Our idea was the same, so what is the bug in my code though?
•  » » » » » you are right is the same idea but i can't fibd the bug
•  » » I wish I would have seen it during the contest. Spend the entire time trying to solve D but couldn't get it to pass. Lesson Learnt-Read all the problems atleast once during the contest
•  » » » Same lesson learned
 » 5 years ago, # | ← Rev. 8 →   problem C. why is my output wrong for the first test case http://codeforces.com/contest/898/submission/33310053my output : 2 ivan 100123 masha 100123 jury output:2masha 100123 ivan 100123 In the question it is mentioned that we can output in any arbitary order.update: found the mistake .My code was printing an extra space in first line of the output .But i have a doubt like the judging code should have ignored such things ??
•  » » The Linked submission is marked as correct...?
•  » » » srry my mistake copy pasted some other link. now it's ohk .
•  » » I think there is extra space after 2
•  » » » Thank you so much Minhazul_Islam ,will be careful from now onwards but will the judging code check those extra spaces ??? ac code just removed the space after 2 link: http://codeforces.com/contest/898/submission/33320542
•  » »
 » Can someone elaborate the solution of F? I am not very comfortable with hashing plus the language of the author is a bit rusty(sry).
 » my code got tle on 5th pretest while many other similar solutions passed. Is the problem due to use of map in my code?? link to code : http://codeforces.com/contest/898/submission/33297374
 » 5 years ago, # | ← Rev. 2 →   Solution of D without set : Sliding window question :) Using Hashing :)http://codeforces.com/contest/898/submission/33305287
•  » » Your hashing can be called identity hashing :D
 » 33320897 I have used a list of a structure node to do the C-Phone Numbers problem. It is a clumsy method but I believe it will work for some test cases. It is running perfectly in my system but giving runtime error Exit code is -1073741819 in codeforces' ide. Could anyone help me out here?
•  » » Do not erase from the set inside the loop in case iterator pointing to undefined value after the change.
 » Why in problem E we need a long long?
 » Come on guys.. Problem E was actually the easiest one.. I know I should have read all the problems first but... E is just.. straight up bad(no offense).. it isn't suited to be an E question and this caused a lot of rating spikes...
 » I am not aware about the concept of hashing. I can not understand the solution to the problem F. The editorial says, "At first we should calculate "hash" by big prime module from the given string, and the base must be equal to 10 because we work with numbers. We can use prime module about 1015, if we will use multiple of long longs by module with help of long doubles."I don't understand this.
 » 5 years ago, # | ← Rev. 2 →   How to proof solution of problem D? Why just turn off current alarm is right?
•  » » Let's process from left to right. If we come to an alarm that would give us k alarms in the interval (i — m, i], then we must turn it off or there will be too many alarms in the interval. The only other option is to turn off alarms preemptively, that is, before we're forced to. But it is optimal to turn off alarms as late in the day as possible, because these will affect the most intervals in the future.
 » Can anyone please explain the solution idea for problem F and it's complexity. I have read the editorial several times, but can't understand it properly. Thanks in advance.
•  » » Does this help?
 » Can someone explain me_ 898F — Restoring the Expression_ .Could not understand a word in editorial.thanks in advance
 » 5 years ago, # | ← Rev. 2 →   My submission for C(here) is taking too much memory for 2nd test case and therefore exiting, but I don't understand why is that happening for n=3? In other IDE's it's hardly taking 3000kb but here its 198836 KB.
•  » » I think memory isnt the problem, because if it were Codeforces would say Memory Limit Exceeded instead of Runtime Error. I suggest u check your code for errors since its probably the problem here
•  » » » 5 years ago, # ^ | ← Rev. 2 →   I've checked for all pretests on different platforms, it's only failing in CFjudge for 2nd one.
•  » » » » Sorry i took so long to answer. Anyway, i think the problem with your code is that u are erasing from s[i.second] and iterating over it the same time.After s[i.second].erase(k); the iterator k is invalidated so u shouldnt erase from the set while iterating over it. Check this page out for more details on erase. But basically u should erase after the 'for' not while it's executing.Another thing, i think it should be erase(j) because k is a subtring of j
 » Hello . My submission for 898F gives error on Test Case 19.http://codeforces.com/contest/898/submission/33383748I'm using the Hash Function, where I'm using 2 prime numbers as given in the array prim[], and I'm using base 10. What is the possible problem in my code. Please help.
 » Can someone please explain problem F ?
 » In F problem what are we trying to hash in the editorial?
 » in problem c whether to use map or multimap i am using map for insertion but to the input 2ivan 2 00123 16ivan 2 00123 25i gettig the output like this ivan [00123 16, 00123 25 , 25 ]  while(n--){ getline(cin,str); k=0,flag=0,g=0,sflag=0; for (i = 0; i < str.length(); i++) { /* code */ if(str[i]==' '&&flag<2){if(flag==0)name=str.substr(k,i);flag+=1;k=i+1;} else if(str[i]==' '||str[i+1]=='\n'){if(str[i+1]=='\n') temp=str.substr(k,i+1); else temp=str.substr(k,i);mymap[name].pb(temp);k=i+1;} // if(mymap[name].size()==3) {sflag=1;break;} } // if(sflag) break; // std::cout << name << std::endl; } // std::cout << mymap.size() << std::endl; auto it1 = mymap.end(); // it1--; for (std::map >::iterator it = mymap.begin(); it != it1; it++) { std::cout << it->first << " " <second << std::endl; } return 0; } 
 » I have solved problem 898F-Restoring the Expression just now and I want to share my idea for this problem with the community.The key idea or observation for this problem is — Let a+b=c. and length of a,b,c is x,y,z respectively. Then z-max(x,y) will always either 0 or 1. It means the maximum number between a and b must have length z or z-1 otherwise we can't obtain c by adding a and b.After this observation now you can check for every possible length of c from 1 to n (where n is the length of the given input string) and from the length of c now you can calculate length of b and c and check whether the a+b=c property is present for the current substrings of the given string. Hashing is the only way to do this check in O(1) complexity. Overall complexity of this solution id O(n).Here is my submission 33521860
 » Help Post, Why my solution was getting WA? Problem My Solution. Why WA Plz Help me. To Find Out Plz.
 » 4 years ago, # | ← Rev. 2 →   Problem F I understand that the only way to compare it, it's using hashing. In fact, in the virtual contest, I thought about it. But the problem I've encountered was how to decided the size of the prime number. I thought about some very small prime numbers, see that it didn't work, and stop thinking about it. Is there any further explanation about hashing that could help me solve problems like this in the future? Maybe something with more theory, that helps me prove what I'm doing is right. Thanks in advance.