Блог пользователя nur_riyad

Автор nur_riyad, история, 6 лет назад, По-английски

### O(n^2) solution link

But if I just erase first three lines of that solution, then solution time changes from 4s+ to 1.2s why?

  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Just wait for the open hacking phase to finish. You will have your answer.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -39 Проголосовать: не нравится

I think the solution is relying on the third line #pragma GCC optimization ("unroll-loops"). I guess GCC will be able to optimize it so that it's only O(n) (or something similar in run time). I think this actually might be much harder to hack than expected.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I tried all 6 possible cases with first three line and found that this line "#pragma GCC optimize("Ofast") " must be included for soln to pass

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

It is fast because,

  • Code is branchless(CPU can easily predict what comes next)
  • AVX enables vector instruction, which in this case gives 4x boost by combining and calculating 4 ints at same time
  • Ofast also gives significant boost, but why idk
»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

I think the only solution to this is that if O(n) is expected, then make the time limit at most 0.8 second. It's 20 times slower than the intended solution.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I got TLE during the contest(using O(n^2) solution). But using your first 3 lines , it's accepted now.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

From what I see with this pragma code begins to use SSE instructions, so I assume it basically processes four values at a time

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

if i use those 3 lines every solution,, can i get advantage all time or not??

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

LoL, quite unexpected, but cool!
Turns out you can do order of 10^10 operations in a second on CodeForces servers.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

pragma added to default template....lol

Also, I wonder how many people lost score on this because of failing to break this....

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Also see this problem, the brute-force solution also passed using command-lines.

Command-lines do make your solution faster, it might pass $$$10^{10}$$$ operations within seconds, it's almost impossible to hack because it's about the basic-level optimization.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

i have also used the above concept but was getting tle then i read this blog and used those 3 lines but still i am getting tle

Your code here...
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,n,t,ans;string s;
    cin>>t;
    while(t--)
    {
        cin>>n;ans=0;cin>>s;
        int a[n+1],p[n+1];
        p[0]=0;
        for(i=1;i<=n;i++)
        {
        a[i]=s[i-1]-'0';
        //if(a[i]==1)
        //ans++;
        p[i]=p[i-1]+a[i];
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(i==j){
            if((p[i]-p[i-1])==i-j+1)
            ans++;}
 
        else if((j-i+1)==(p[j]-p[i-1])&&(i<j))
        ans++;
        }
        cout<<ans<<endl;
    }
}