Number_72's blog

By Number_72, history, 16 months ago, In English

Hello CodeForces. I've been trying to solve this problem (505C - Mr. Kitayuta, the Treasure Hunter) for the last hour but I hit a roadblock. Here's my submission: 212193996

It uses the idea of the editorial but somehow fails testcase 5. The expected output is 16790 but my code outputs 16791.

Thanks for your interest...

Full text and comments »

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

By Number_72, history, 17 months ago, In English
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define vi vector<int> 
#define inf 2e18
#define spc " ";
template <class T>
void print(T obj) {
    std::cout << "{";
    for (auto it=obj.begin();it != obj.end();++it){
        std::cout << *it;
        if (next(it) != obj.end()) std::cout << " ";
    } 
    std::cout << "}\n";  
}
void printarr(int* p1,int* p2) {
    std::cout << "{";
    for (int* ptr = p1;ptr<p2;ptr++) {
        std::cout << *ptr;
        if (ptr+1 != p2) std::cout << " ";
    }
    std::cout << "}\n";
}   
#define debug(X) std::cout << #X << " = ";print(X); 
#define debugarr(A,SZ) std::cout << #A << " = ";printarr(A+1,A+SZ+1);
#define debugint(x) std::cout << #x << " = " << x << endl;
int MOD = 1e9+7;
int mul(int x, int y){return ((x % MOD) * (y % MOD)) % MOD;}
int add(int x, int y){return ((x%MOD)+(y%MOD))%MOD;}

void solve() {
    int n,m;
    cin >> n >> m;
    int grid[n+1][m+1];
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) cin >> grid[i][j];
    }
    set<int> progs[n+1][m+1];
    queue<pair<pair<int,int>,int>> q;
    q.push({{1,1},grid[1][1]});
    vi dx = {1,0};
    vi dy = {0,1};
    while (q.size()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int d = q.front().second;
        q.pop();
        for (int i=0;i<2;i++) {
            int gx = x+dx[i];
            int gy = y+dy[i];
            int gd = d+grid[gx][gy];
            if (gx > n || gy > m) continue;
            if (!progs[gx][gy].count(gd)) {
                progs[gx][gy].insert(gd);
                q.push({{gx,gy},gd});
            }
        }
    }
    cout << ((progs[n][m].count(0))?"YES\n":"NO\n");
}    
 
signed main()
{   
    #ifdef Local
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0);cin.tie(0);std::cout.tie(0);
    int tc = 1;
    cin >> tc;
    while (tc--){ 
        //std::cout << "TEST " << cs << ":" << endl;
        solve();
    }
}

Hello Codeforces, I have submitted the code above to the problem: 1695C - Zero Path My solution got TLE but I am a bit confused with the time complexity. Can you help me?

Full text and comments »

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

By Number_72, history, 18 months ago, In English

Hello Codeforces, I am currently planning on improving my graph theory and data structure knowledge over the next month so I am looking for some resources available for them. For graph theory I know a lot of resources namely youtube playlists of some channels like William Fiset. I would like to learn some of your favourite resources for Data Structures (SegTrees,BITs etc.) and Graph Theory Algorithms. I do have an abundance of problemsets for both topics so I only need a good, comprehensive tutorial for them like some books or a long playlist or sth. I appreciate all responses so please do not hesitate to share your personal favorites.

Full text and comments »

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

By Number_72, history, 18 months ago, In English

Hello Codeforces, today I was solving this problem:1822G1 - Magic Triples (Easy Version). I wrote a very simple brute force solution. here is my code:

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define vi vector<int> 
#define inf 2e18
#define endl '\n'
#define int long long
#define F(xxx,yyy,zzz) for (int xxx=yyy;xxx<zzz;xxx++)
int MOD = 1000000007;
int mul(int x, int y){
    return ((x % MOD) * (y % MOD)) % MOD;
}
int add(int x, int y){
    return ((x%MOD)+(y%MOD))%MOD;
}
int exp(int x, int y){
    int ans = 1;
    while (y){
        if (y % 2) ans = mul(ans, x);
        x = mul(x, x);
        y /= 2;
    }
    return ans;
}
int divide(int x, int y){
    return mul(x, exp(y, MOD - 2));
}
using namespace std;


void solve(){
    int n;
    cin >> n;
    int a[n+1];
    for (int i=1;i<=n;i++) cin >> a[i];
    sort(a+1,a+n+1);
    unordered_map<int,int> cnt;
    for (int i=1;i<=n;i++) cnt[a[i]]++;
    unordered_map<int,int> cnt2 = cnt;
    int ans = 0;
    for (int i=1;i<=n;i++) {
        if (cnt[a[i]]) {
            for (int b=2;a[i]*b*b<=a[n];b++) {
                ans+= cnt[a[i]]*cnt[a[i]*b]*cnt[a[i]*b*b];
            }
            cnt[a[i]] = 0;
        }
    }
    for (int i=1;i<=n;i++) {
        ans+= max(0ll,(cnt2[a[i]])*(cnt2[a[i]]-1)*(cnt2[a[i]]-2));
        cnt2[a[i]] = 0;
    }
    cout << ans << endl;
}   

signed main()
{
    #ifdef Local
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin >> tc;
    while (tc--)solve();
}

I estimated that this algorithm would make at most 2e8 operations in total but it gets TLE on TC 14. N goes upto 2e5 and the elements of A go upto 1e6 so b would iterate upto at most 1e3. So I am a bit confused. I reckon it has something to do with the unordered map but I am not sure. I would be happy if someone pointed out the mistake.

Full text and comments »

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

By Number_72, history, 19 months ago, In English

Hello Codeforces, I am a 15 year old high school student that works hard to improve, after reaching Cyan with 4 months of practice, going on for another 2 months without much improvement and a 2.5 month break, I have just reached Expert after around 9 months. I would like to learn what difficulty range I should study from and what resources would be most beneficial in your opinion. Thank you in advance.

Full text and comments »

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

By Number_72, history, 22 months ago, In English

Hello Codeforces, yesterday I have submitted various solutions for problem C. Although I have estimated my time and memory complexity to be O(n log n) I was surprised to see that it gave time limit exceeded, can you help me? 188111812

Full text and comments »

Tags tle
  • Vote: I like it
  • +1
  • Vote: I do not like it

By Number_72, history, 23 months ago, In English

Hello Codeforces, today is the last day for middle school national olympiad of informatics and as to support a beloved companion, I am writing this blog, we expect all your best wishes! nicecoder37

Full text and comments »

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

By Number_72, history, 2 years ago, In English

Hi, I am a high school student trying to improve in order to compete in the IOI. Yesterday, after 4 months of practice, I have become a specialist on codeforces. Now that I have somewhat got used to how I should practice constructive and greedy algorithms, I have a question for you. What topics should I focus on studying next? By topics I mean stuff like graphs,dp (etc.). Please assist me with your knowledge. Thank you in advance.

Full text and comments »

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

By Number_72, history, 2 years ago, In English

Hello, I am a student from Turkey who wants to improve in order to compete in IOI. I have reached green after 2,5 months of learning but I have a big question on my mind. What should I priortise to reach specialist? I humbly request your advise. Good day to everyone.

Full text and comments »

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

By Number_72, history, 2 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Number_72, history, 2 years ago, In English

Hello everybody, recently I have been studying graphs and trees and have acquired basic graphs knowledge such as BFS,DFS,Prim's Algorithm for MST, Topological Sort and DSU. But I feel like I am not following a very good syllabus since I study whatever I encounter in problems rated 1500-1600 or so. I would be very happy if anyone helped me by providing a curriculum or a playlist or something like that. Thank you very much for your attention. If interested, Number_72 use this link to check out my recent submissions. There are about a dozen accepted graph questions. Thank you.

Full text and comments »

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

By Number_72, history, 2 years ago, In English

Hello everyone, I am a beginner coder who works hard to improve. Recently, I have noticed that I need to solve more binary search questions to improve. So I filtered the problemset with binary search and set the difficulty range to 1400-1500. But, most problems only use binary search algorithm to only improve the time complexity. Could anyone suggest a resource that I could use just to improve my binary search? Thank you for your interest.

Full text and comments »

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