kazuya's blog

By kazuya, 4 years ago, In English

Let mod be $$$10^9 + 9$$$. I want to calculate X % mod where $$$ X = ((a/b)^ n -1 )/(a/b - 1)$$$. I know inverse modulo of number N with respect to mod is $$$N^{mod-2}$$$. Also $$$n$$$ is very large so I cannot iterate and add the sum by each term ( I cannot sum the terms $$$1 + (a/b)^1 + (a/b)^2 .. (a/b)^{n-1} $$$). Please help, I was trying to solve this problem. 963A - Знакопеременная сумма

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By kazuya, history, 4 years ago, In English

I was solving this problem 1202B - You Are Given a Decimal String... and I got some idea about it but the time complexity for my algorithm was O(10^8) and since time limit mentioned was 2 sec I didn't implement it and decided to look at the editorial, in which author mentioned this : But, it will work only in C++, since the language is fast and 2⋅10^8 basic operations are executed in less than 0.5 seconds. Can someone explain this? (as far as I know up to 10^6 operations can be done in 1 second, so for 2 seconds ~ 2*10^6, right ?).

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By kazuya, history, 4 years ago, In English

This is a short code which I wrote and it only printed '1' and not "Hello World" but when I did typecasting in if statement i.e if((int) it->second.size() > x) then it worked completely fine. Now if typecasting is the solution then why this line always works " for (int i=0;i < v.size(); i++) ". Please can anyone explain this behaviour ?

Your code here...
#include<bits/stdc++.h>
using namespace std;


int main()
{
    map<int,set<int>> m;
    m[0].insert(1);
    
    int x = -1;
    for(auto it=m.begin();it!=m.end();it++)
    {
        cout<<it->second.size()<<endl;  
        if(it->second.size() > x)
        cout<<"Hello World"<<endl;
    }
}

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By kazuya, history, 4 years ago, In English

1355D - Игра с массивом Solving the problem is easy by observation but can anyone explain the case when Petya will loose i.e for S<2n mathematically?

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it