fcspartakm's blog

By fcspartakm, history, 6 months ago, translation, ,

•
• +51
•

 » 6 months ago, # |   +59 Is there any solution for F without using hashing/probabilistic approaches?
•  » » 6 months ago, # ^ |   0 Big integer types
•  » » » 6 months ago, # ^ |   +11 That should be TLE as it is O(n^2)
•  » » 6 months ago, # ^ |   +5 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 ;(
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » 6 months ago, # ^ | ← Rev. 2 →   +10 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.
 » 6 months ago, # | ← Rev. 3 →   +1 How many people used 'exgcd' in 898B ? ...
•  » » 6 months ago, # ^ |   0 I used it,but failed
•  » » » 6 months ago, # ^ |   0 After the contest I realized that I was thiking too much...
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 so do I...I though brute force will get TLE btw somenoe know how to solve by exgcd?
•  » » » » » 6 months ago, # ^ |   +8 you can check my submission
•  » » » » » » 6 months ago, # ^ |   +1 Nice and clean code dude (y)
•  » » 6 months ago, # ^ |   0 I used and got AC.
•  » » » 6 months ago, # ^ |   0 I exceed time limited at 40th test,,,,,,
•  » » 6 months ago, # ^ |   0 +1 takes me quite a time to code...
•  » » » 6 months ago, # ^ |   0 me too.
•  » » 6 months ago, # ^ |   0 I used and accepted the problem
•  » » 6 months ago, # ^ | ← Rev. 2 →   0
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 i pondered over a dp solution too much and constantly got NZEC(stack overflow) didn't realise that it would work out so easily
•  » » 6 months ago, # ^ |   0 I used it, my solution in Python — http://codeforces.com/contest/898/submission/33300359
 » 6 months ago, # | ← Rev. 2 →   0 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.
•  » » 6 months ago, # ^ |   +3 you have declared "s" twice , and there can be more bugs in your code. on my machine it gives 0 as output
•  » » » 6 months ago, # ^ |   0 I understand that's a wrong practice but shouldn't change the output as the one inside main must be considered.
 » 6 months ago, # |   +15 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 .
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 Why E is so easy? :D
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +1
•  » » » » 6 months ago, # ^ |   0 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?
•  » » » » » 6 months ago, # ^ |   0 you are right is the same idea but i can't fibd the bug
•  » » 6 months ago, # ^ |   +2 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
•  » » » 6 months ago, # ^ |   +1 Same lesson learned
 » 6 months ago, # | ← Rev. 8 →   0 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 ??
•  » » 6 months ago, # ^ |   +1 The Linked submission is marked as correct...?
•  » » » 6 months ago, # ^ |   0 srry my mistake copy pasted some other link. now it's ohk .
•  » » 6 months ago, # ^ |   +1 I think there is extra space after 2
•  » » » 6 months ago, # ^ |   0 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
•  » » 6 months ago, # ^ |   0
 » 6 months ago, # |   +11 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).
 » 6 months ago, # |   0 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
 » 6 months ago, # | ← Rev. 2 →   0 Solution of D without set : Sliding window question :) Using Hashing :)http://codeforces.com/contest/898/submission/33305287
•  » » 6 months ago, # ^ |   +1 Your hashing can be called identity hashing :D
 » 6 months ago, # |   0 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?
•  » » 6 months ago, # ^ |   +1 Do not erase from the set inside the loop in case iterator pointing to undefined value after the change.
 » 6 months ago, # |   +1 Why in problem E we need a long long?
 » 6 months ago, # |   +14 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...
 » 6 months ago, # |   +4 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.
 » 6 months ago, # | ← Rev. 2 →   +1 How to proof solution of problem D? Why just turn off current alarm is right?
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +7 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.
•  » » 6 months ago, # ^ |   0 Does this help?
 » 6 months ago, # |   +7 Can someone explain me_ 898F — Restoring the Expression_ .Could not understand a word in editorial.thanks in advance
 » 6 months ago, # | ← Rev. 2 →   0 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.
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I've checked for all pretests on different platforms, it's only failing in CFjudge for 2nd one.
•  » » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   +6 Can someone please explain problem F ?
 » 6 months ago, # |   +6 In F problem what are we trying to hash in the editorial?
 » 6 months ago, # |   0 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; } 
 » 6 months ago, # |   +3 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
 » 6 months ago, # |   0 Help Post, Why my solution was getting WA? Problem My Solution. Why WA Plz Help me. To Find Out Plz.
 » 4 months ago, # | ← Rev. 2 →   0 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.