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

Автор sebi420p, история, 4 года назад, По-английски

Hello, everyone.

I am organizing my first contest and I would really appreciate your feedback. All the details about the contest are on the sign-up page. A rough estimate of the difficulties of the tasks would be [800-2000]. Solutions are accepted only in C++. Feel free to ask any questions in the comment section or via a private talk.

UPD1: I added java, C and python.

UPD2: Thank you for attending and congratulations to everybody! I am eager to hear your impressions.

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

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

If its through hackkerank, why only cpp?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    Agreed, all the infrastructure is there for you to allow Java + other languages, so why the arbitrary restriction?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

    I am not experienced enough to set proper time/memory limits for other languages. Better safe than sorry.

    UPD1: I added java, C and python.

    UPD2: I tried my best to set adequate time/memory limits

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Hey, I have a doubt in the first question. We have been given an array of speed and we choose two horses for a race in such a way that the absolute difference between their speed is as small as possible. Then we need two return an array of index of horses which wins the race. Is my understanding correct??

      If it is correct, then consider this test case: N = 6 speed = [90, 92, 93, 95, 96, 98] Currently, least difference is 1 so we select the pairs (92,93),(95,96) for the first two selection. For the third race, we select the pair(90,98). Hence, my answer is (3,5,6). The editorial code answer is (2,4,6).

      Can you tell me where I am going wrong??

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Now i realize that i wasn't clear enough with the statement. In your example you should first take care of the horse with the speed 90 and pair it with the horse 92.

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

what are the prizes?

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

Good questions. In 3rd question, why my Binary indexed tree approach gives TLE? Question MySolution

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

Interesting problems bro. Hope you organise these contests regularly :)

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Good idea for E, I really forgot that the bits were just being flipped. I think the time complexity can be improved though. Instead of a Fenwick tree, just a simple set<pair<int, int>> can be used to store the endpoints of continuous segments of ones. To find which segment containing some index, just find the segment with the closest left endpoint to that index, and check if the right endpoint is on the right of that endpoint.

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

Nice problems,very well balanced in my opinion. Just one question, what would be the approximate ratings of each of the problems according to codeforces standard? TIA.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Quite hard to tell. The only thing that I can say is that according to plenty of participants problem B was harder than problem C.

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

I am very sorry but i am stuggling with B question in this contest for hours, i am unable to find the mistake in my code (i am ashamed of this), please help me . Code is here ----->

#include <bits/stdc++.h>
#define int long long
#define MAX 1000000
#define deb(x) cout << #x << "=" << x << endl;
using namespace std;

vector<int> phi(MAX + 5);

signed main() {
    phi[1] = 1;
    for (int i = 2; i <= MAX; i++) {
        phi[i] = i;
    }
    for (int i = 2; i * i <= MAX; i++) {
        if (phi[i] == i) {
            phi[i] = i - 1;
            for (int j = i + i; j <= MAX; j += i) {
                phi[j] -= (phi[j]/i);
            }
        }
    }

    int sum = 0;
    for (int i = 1; i <= MAX; i++) {
        sum += phi[i];
        phi[i] = sum;
        phi[i] = (2LL * phi[i]) - 1;
    }

    int q, ans = 0;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int temp = phi[n];
        ans += temp;
    }
    cout << ans;

    return 0;
}

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Change int ans to long long ans, and long long sum too. And phi to vector of long long as well.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just changed the evaluation of phi(all but 1 cases got accepted) and then updated MAX. It got accepted. ModifiedCode. BTW how to format code as it is in comments?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Glad you got it accepted. There is an option called

    Spoiler
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    While calculating the phi array, why you only iterated till $$$\sqrt{MAX}$$$ tho? What about the prime bigger than $$$\sqrt{MAX}$$$? Their phi value will be itself minus 1 and seem like you did not update that.

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

I am getting wrong answer in 4 test cases for problem B( GCD Table ), can someone help me ? . Link to my code