Taha1506's blog

By Taha1506, history, 3 years ago, In English

Sorry for putting this rather techincal problem in codeforces but I didn't find any other place to post it on. I am having problem connecting to codeforces via a browser and I am getting the message 'This site can’t be reached'. This problem appears in a very strange manner that I don't get it for some days I do nothing special it disappears itself and after a few days again I can't connect without doing anything specific :( . Another strange situation is that it is completely fine using python request.get('https://mirror.codeforces.com') and I am getting response 200. I have tried the browsers google chrome and microsoft edge and the result is same in both browsers.(It is always fine with a vpn connecting to almost all the countries. Any ideas why this strange situation is happening? (I can't compete in contest well because it will make the internet speed extremely small). Thanks!

Full text and comments »

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

By Taha1506, history, 3 years ago, In English

Can anyone suggest a good string hashing template to use? I had a look at katcl's one and it was complicated also tourist didn't have any string hashing algorithm on his github. I tried to implement it myself but I was not very good with c++ syntax to be able to write it my self. So any suggestions?

Full text and comments »

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

By Taha1506, history, 3 years ago, In English

Hi!. In a recent contest I needed to sort a container of form vector<pair<pair<int, int>, int> > and the container only contained not-negative integers I needed two functionality:

1.The vector is sorted by second element of the first element of the outer pair.

2.The pair {{0, 0}, 0} is always at the beginning.

so I used the sort function with comparator as follows:

sort(summary.begin(), summary.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
        return a.first.second < b.first.second;
    });

Where summary is the vector I want to sort. I got wrong answer in the half of the test cases and I didn't really know why. Then I replaced it with the following code and It magically worked!

sort(summary.begin(), summary.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
        if (a.first.second == b.first.second) {
            return a < b;
        } else {
            return a.first.second < b.first.second;
        }
    });

Any idea on what's going on? I thought it was because of not guranteeing that {{0, 0}, 0} is at first but by trying some cases it was always at the first. The statement of the problem is in persian so I will translate it and put it here as soon as I can if it is not really clear from the sort that where I am wrong.

Full text and comments »

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

By Taha1506, history, 3 years ago, In English

I was looking at the segment tree template of tourist. It doesn't have any operation for find the k'th zero or k'th one. So I wondered if is it possible to the with the current template without changing it. My question is : Is it possible to use find last and find first operations to find the k'th zero or one? I mean just using the current template to answer that kind of queries.Any ideas? If not what is the best ways to implement it for the current template so that we don't have to change the code a lot each time.

You can see the template of tourist here .

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

Hi!I was wondering wheter participating from iran to hashcode is forbidden or not.I don't see any rules in the site but there is no Country named iran in the registeration should I just pick a random country and participate?

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

I was solving This problem and submitted 106080441.I am getting runtime errors on test 4.The codeforces diagnoser says it is because it is of integer overflow I changed everything to long long but it gives me again the same error.Can anyone say Whats wrong with my code please?Thanks.

Edit:Ok I got it I should have checked lx<a.size();

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

I need to add some flags to compiler to avoid overflow or other stupid mistakes but I can't do it.I searched the methods in the net to find a solution for Clion but since I was very new to programming so I didn't understand well.Can anyone explain please?

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

I was studing cp-algorithem web and I was trying to come up with 0-1 BFS by my self.I came up with the following algorithm:

We run a DSU to all edges with weight $$$0$$$ after that we come up with some components now for each edge with weight $$$1$$$ instead of adding edges between the original vertices $$$u,v$$$ we add edges between their leaders then apply a BFS to the leaders(with source vertex being the leader vertex of our source-vertex) only then the length of the path between $$$u$$$ and some source-vertex $$$v$$$ will be the length between leader of $$$v,u$$$.

This is probably not new.But I was wondering if this is faster or slower than the actual 0-1 BFS in CP?In terms of time complexity it is worse than the actual 0-1 BFS but since in competetive programming we are dealing with small numbers $$$\alpha (m,n)$$$ may be treated as a constant.Any idea on how to test this?

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

Some time ago someone told me that when your choices are quite dependent to each other then using dp will be a great idea having this in mind it helped me to come up with the dp idea in a lot of problems in the first place.Yesterday I saw a problem that had dp solution see the link .I wasn't able to recognize it is a dp problem until the end of the contest.But a yellow coder seeing the problem in the first place told that it is a standard dp problem.So my question is how to recognize "Standard dp" problems?Can anyone tell me what property of the problem makes it a standard dp problem?Thanks in advance.

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

Does anyone know how can I make a certain part of code always appear in Clion.And also how can I save a file as a template so that it appears without rewriting it?I searched the net but didn't see anything.

I got the solution to create templates Thanks to the comments.Now the only problem remaing is the following how can I make a part of code always appear when oppening a new file.More precisly I wan't this part always appear:

inclue <bits/stdc++.h>

using namespace std; int main(){ ios::sync_with_stido(false): cin.tie(nullptr);

return 0;

}

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

Is it considered A cheating if I use another person's implemention for a data structure instead of designing one by myself?

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

In today's contest I used (1<<k) to denote $$$2^k$$$ but.It turned out that (1<<k) won't generate long long values so I got time limit exceeded in test three.Then I decide to implement power using multiply and return both the power and the number itself but it take more amount of code and I used to spend many time debugging it.Any suggestions?

Full text and comments »

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

By Taha1506, history, 4 years ago, In English

Solving some problems I saw that I really need a template for modular arithmetic to avid long time spending on them. so I created it.But each time using it I had to copy paste it from the original part.Recently I saw a stream from twitch in which he just wrote segtree and the whole segment tree structure appeared.How can I do this in far manager?I searched the net but things were really complex so I decided to ask here.

Full text and comments »

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