fcspartakm's blog

Codeforces Round #451 (Div.2) Editorial
By fcspartakm, history, 7 years 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

Comments Comments (54)
| Write comment?
»
7 years ago, # |
  Vote: I like it +59 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Big integer types

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      → Reply
  • »
    »
    7 years 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 ;(

    → Reply
    • »
      »
      »
      7 years 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).

      → Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
7 years 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://mirror.codeforces.com/contest/898/submission/33309260

edit: It gives 2 on codechef as well.

→ Reply
  • »
    »
    7 years 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

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply
»
7 years 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 .

→ Reply
  • »
    »
    7 years 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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why E is so easy? :D

→ Reply
  • »
    »
    7 years 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://mirror.codeforces.com/contest/898/submission/33306957

    Thanks in advance

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Read my solution

      → Reply
      • »
        »
        »
        »
        7 years 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?

        → Reply
        • »
          »
          »
          »
          »
          7 years 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

          → Reply
  • »
    »
    7 years 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

    → Reply
»
7 years 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://mirror.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 ??

→ Reply
»
7 years 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).

→ Reply
»
7 years 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://mirror.codeforces.com/contest/898/submission/33305287

→ Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why in problem E we need a long long?

→ Reply
»
7 years 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...

→ Reply
»
7 years 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.

→ Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years 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.

→ Reply
»
7 years 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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

http://mirror.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.

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain problem F ?

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
7 years 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

→ Reply
»
7 years 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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add this editorial to contest dashboard.

→ Reply