fcspartakm's blog

By fcspartakm, history, 9 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +51
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it +59 Vote: I do not like it

Is there any solution for F without using hashing/probabilistic approaches?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Big integer types

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      That should be TLE as it is O(n^2)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 ;(

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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).

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

»
9 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

How many people used 'exgcd' in 898B ? ...

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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/33309260

edit: It gives 2 on codechef as well.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you have declared "s" twice , and there can be more bugs in your code. on my machine it gives 0 as output

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand that's a wrong practice but shouldn't change the output as the one inside main must be considered.

»
9 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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 .

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 order

    the solution is the minimun of the two previous

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why E is so easy? :D

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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/33306957

    Thanks in advance

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you are right is the same idea but i can't fibd the bug

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Same lesson learned

»
9 months ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

problem C. why is my output wrong for the first test case http://codeforces.com/contest/898/submission/33310053

my output :

2

ivan 100123

masha 100123

jury output:

2

masha 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 ??

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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).

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Solution of D without set : Sliding window question :) Using Hashing :)

http://codeforces.com/contest/898/submission/33305287

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Your hashing can be called identity hashing :D

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Do not erase from the set inside the loop in case iterator pointing to undefined value after the change.

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why in problem E we need a long long?

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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...

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

»
9 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How to proof solution of problem D? Why just turn off current alarm is right?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Can someone explain me_ 898F — Restoring the Expression_ .Could not understand a word in editorial.thanks in advance

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I've checked for all pretests on different platforms, it's only failing in CFjudge for 2nd one.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello . My submission for 898F gives error on Test Case 19.

http://codeforces.com/contest/898/submission/33383748

I'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.

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain problem F ?

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

In F problem what are we trying to hash in the editorial?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem c whether to use map or multimap i am using map for insertion but to the input

2

ivan 2 00123 16

ivan 2 00123 25

i 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<string,vector<string> >::iterator it = mymap.begin(); it != it1; it++) {
            std::cout << it->first << " " <<it->second << std::endl;
        }
        
            
            
            
            
            
            
    return 0;  
}
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Help Post, Why my solution was getting WA? Problem My Solution. Why WA Plz Help me. To Find Out Plz.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add this editorial to contest dashboard.