SlavicG's blog

Codeforces Round 886 (Div. 4)
By SlavicG, history, 16 months ago, In English

Hello Codeforces!

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 886 (Div. 4)! It starts on Jul/21/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: MikeMirzayanov, erekle, Bakry, Dominater069, Gheal, andrei_boaca, zwezdinv, sam571128, Sho, Wibo, Phantom_Performer, moonpie24, mafailure, Kalashnikov, SashaT9, Qualified, haochenkang, ZiadEl-Gafy, MADE_IN_HEAVEN, AdOjis485, qwexd, mkisic, Killever, sabbir-hasan-anik, peshkoff, donghoony!

And thanks to Vladosiya for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck to everyone!

UPD: Editorial is out!

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

Comments Comments (222)
| Write comment?
»
16 months ago, # |
  Vote: I like it +26 Vote: I do not like it

→ Reply
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i am so excited it is my first *out of competition contest :)

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a Newbie participant, I hope not to be Newbie again after this contest

→ Reply
»
16 months ago, # |
  Vote: I like it +16 Vote: I do not like it

As a tester, I would say this is a great Div. 4 Round.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you and your team!

    Best, Jelal

    → Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

As a tester, there will be a lot of wisdom bestowed upon you.

→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

As a Newbie participant, I hope to be Pupil after this contest

→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

My first unrated round! :)

→ Reply
»
16 months ago, # |
  Vote: I like it -23 Vote: I do not like it

As a gray participiant, I hope to be a LGM after this contest)

If you want to race

GL & HF

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Right, I feel like this has a good chance of coming true.

    → Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

By the way, what is the difficulty of this game

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Division 4 is the easiest division. It's aimed at people with a rating below 1400.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I only solved 3 of them what that means?, btw this is the first time I join a contest.

      → Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Excited! I hope i will do well in this round.

→ Reply
»
16 months ago, # |
  Vote: I like it +24 Vote: I do not like it

As a tester, please stop posting cringe unfunny memes

Also the problems are pretty good

→ Reply
»
16 months ago, # |
  Vote: I like it +22 Vote: I do not like it

official participant with highest rating

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to my first out of competition round!

→ Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will it not be better if you use specialist instead of pupil.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      no the newbie is refering that pupil is the highest rated color for Div.4

      → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Dattebayo

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First unrated contest

→ Reply
»
16 months ago, # |
  Vote: I like it -7 Vote: I do not like it

As a participant , I will test my speed through this contest

→ Reply
»
16 months ago, # |
  Vote: I like it +9 Vote: I do not like it

This is my first round as a TESTER. Wish you all the best & hope you will enjoy this round.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope to be Specialist after this contest

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach specialist after this contest!

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Well, it's practically not possible. But I get what you want to convey. Same here. Skill issue

    → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

After so many fuck ups DIV-4 is the only hope for me.

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for creating these! Fridays are a bit complicated for me in schedule but it's still fun to participate and continue to learn. Look forward to this contest!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited to become Newbie for the first time !

→ Reply
»
16 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Contests for all div 1,2,3,4 in the next 5 days...balanced, as all things should be

→ Reply
»
16 months ago, # |
  Vote: I like it +23 Vote: I do not like it

As a tester, it tasted like mother's cooking.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why only 120 minutes why note 135 minutes

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck to everyone

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to solve all problems!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hopefully i reach spec again after this

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope it be my last rated div 4 contest

→ Reply
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Alright, iron contest!!!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wait so Div. 4 is easier than Div. 3 (or Div. 2 (or Div. 1))? I thought the reverse, but seeing that this competition is rated for participants with rating $$$<1400$$$, and the previous one (with Vika) is for rating $$$<2000$$$ or something, I now think this round is gonna be easier..?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yes, that is correct. Div. 4 is easier than Div. 3 which is easier than Div. 2 which is easier than Div. 1.

    → Reply
»
16 months ago, # |
  Vote: I like it +46 Vote: I do not like it

It's been 3 minutes without Div4, I can't stop shaking and I'm having serious mental breakdowns. I woke up today trying to log into Div4 but the site was down, I had a big panic attack but I managed to calm down after a few hours. I couldn't go to school today, I'm so worried that I even took my father's gun from the shed, thinking about killing myself. I am nothing without Div4, it's my life, it's my destiny, without Div4 I wouldn't be able to do anything. Div4 is the best thing ever made and I can't shake the addiction, it's the best oj out there. I can't stop shaking and crying, I'm so worried. I spent all my time on Div4, got rating and contribution.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If Div4 has a million fans, then I am one of them. If Div4 has ten fans, then I am one of them. If Div4 has only one fan then that is me. If Div4 has no fans, then that means I am no longer on earth. If the world is against Div4, then I am against the world.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope i become a specilast again

→ Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Bruh, my browser is always being checked. What's wrong?

→ Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

div5

→ Reply
»
16 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem set is good. The statements are short and easy to understand. A good div4 round...

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

My first *out of competition :)

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first rated competition.

→ Reply
»
16 months ago, # |
  Vote: I like it +26 Vote: I do not like it

i spent like 35 minutes on problem H, just to realize that i misread the question. literacy issue ngl. very good problemset btw :D

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same on problem E, thinking c was just the sum of the borders and not the cardboard "behind" the image.

    → Reply
»
16 months ago, # |
  Vote: I like it +2 Vote: I do not like it

the first contest that I aked !!!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what was the upper bound for binary search of problem E?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    l = 0, r = 1e18.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No, the bound is around 1e9.

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      given w>=1 how can l be 0

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        it is actually doesn't matter, answer won't be 0 anyway

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why the upperbound cannot be 1e18 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            let's say n = 1 then c = (2 * w + a[0]) * (2 * w + a[0])

            since c up to 1e18, w can't be greater than ~5e8

            for example if we will take w = 6e8, it will be

            (2 * 6e8 + a[0]) * (2 * 6e8 + a[0]) = (1.2e9 + a[0]) * (1.2e9 + a[0]) > 1e18

            → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too couldn't figure it out at first. Then I started upper bound from 1 and kept on doubling it till it was less than my required value. After that used binary search

    → Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Div 4.5

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really enjoyed this round. Hope not getting hacked :/

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong here. I am pretty sure it's a graph problem(Last problem.)

My code
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're treating it as an directed graph.It is an undirected graph,add both the edges.

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Input:
1
3 2
2 1 1
3 1 2

Your Output:
NO

Correct Output:
YES

Explanation:
idx | pos
 1  |  3
 2  |  2
 3  |  1
    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me out in the "F" problem , i got stuck in the 6th testcase, like shouldn't the answer be 6 when the trap is placed at position "24" Help me out!

this is my approach

int32_t main() {
    int t;
    cin >> t;
    while (t--) {
       int n;
       cin>>n;
       vector<int>nums(n ,0);
       unordered_map<int , int>m;
       for(int i=0 ; i<n ; i++) 
       {
           cin>>nums[i];
       }
       int ans=INT_MIN;
       int pos=0;
       for(int i=0 ; i<n ; i++)
       {
            int temp=n;
            int x=0;
            while(temp--)
            {
                cout<<x<<"  ";
                m[x]++;
                if(x!=0) 
                {
                    if(m[x]>=ans)
                    {
                        ans=m[x];
                        pos=x;
                    }
                }
                x+=nums[i];
            }
            cout<<endl;
       }
       
       cout<<"answer :"<<ans<<endl;
       cout<<"pos :"<<pos<<endl;
    }

    return 0;
}
→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yo can someone pls help me out I dont get whats wrong with this code on problem 5. https://codeforces.me/contest/1850/submission/214926782

I tried to find the multiple that appeared the most, since that would catch the most frogs.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Input:
1
10
2 2 2 2 2 3 3 3 3 3

Your Output:
5

Correct Output:
10

    Explanation: You can place a trap at position $$$6$$$ to catch all frogs.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I am new to Code forces, can you explain these 2 points in little bit more detail please?

  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)

  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    After the contest, the participants have 12 hours to "hack" any target solution, this means they can submit a test case where they think the target solution will fail (of course still within the problem bounds). If successful the hack is added to a pool of tests that will later be applied to all solutions (all successful hacks are applied to all solutions), so in the end you have accepted solutions that have passed every valid test.

    Edit:Div3, Div4 don't give points for hacking.

    Old (mistake, only Div1, Div2)
    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it so dumb to take too much time for the E (divide first would be the more suitable name for the problem)?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it's not dumb. Dumb is that i was using quadratic formula to solve for 'w' and in the end couldn't submit because for some reason it wasn't working for very large inputs

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the same approach. You took int for some variables. change that —

      long double x=4*n , y=0, z=0;

      And typecast your output-

      cout << (long long) ans << endl;

      → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I couldn't solve E what's wrong here?

void solve(){ ll n; long long c; cin >> n >> c; vector arr(n, 0); ff(i, 0, n) cin >> arr[i];

ll sum = 0;
ll ss = 0;
ff(i, 0, n) ss += (arr[i] * arr[i]), sum += arr[i];

ll sq = sqrtl((sum * sum) - n * (ss - c));
cout << (sq - sum) / (2 * n) << nl;
return;

}

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it fails because of sqrtl, I had the same issue as well, find the square root by binary search. Also, if you are solving it by the quadratic formula, shouldn't it be $$$w=\frac{-4\cdot sum+\sqrt{16\cdot sum^{2} - 16\cdot n\cdot \left ( ss - c \right )}}{8\cdot n}$$$ ?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is what i did lmao and i really struggled with big numbers, ended up using double

      → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will overflow long long.

    Suppose n=1e5, c=1e18 and all inputs are 1. then n*(ss-c) will be approx. 1e5 *(1e18-1e5) almost equal to 1e24.

    → Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

We want div-4 contest more often as beginer

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

best div 4 contest ever

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Wow. That was nice contest. Overall, good problemset.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Problem Set. It seems that the difficulty difference between Div3 and Div4 is much higher than Div3 and Div2.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanx Man i Really enjoy this Round

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good round, was too scared to implement dfs for H and ended up staring at it for 1 hour :(

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the solution for G? My solution was to project all the points onto {1,0}{1,1}... all the directions. Group them into bins based on if they landed at the same point (after correcting for length of points), and then adding n choose 2 from each of those bins to ans. However, I got some error that I couldn't figure out if was due floating point inaccuracies or because my solution was wrong / nonsense.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x , y , x-y , x + y If one is the same, it's a pair

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need floats here

    Find points count on each existing line

    vertical[y] += 1
horizontal[x] += 1
diagonal1[x + y] += 1
diagonal2[x - y] += 1

    Then iterate over all of them and add C(n, 2) to the result (where n is count of points on current line)

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Why do you add $$$\binom{n}{2}$$$?

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Because he had studied combinatorics in school. (It's just a joke..)

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because it's a count of all different pairs on that line.

        Also forgot to mention that you need to multiply the result by 2 (to count reverse too)

        → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Coders, I have done the problem E, with a linear approach, which was very slow and then i thought about binary search but some test cases passed and some not. Please can someone advice on what is wrong with this code below ?

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

void solve() {
	int n;
	long long c;
	cin >> n >> c;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int l = 0;
	int r = 1e9;
	int w = 0;
	while (l <= r) {
		w = l + (r - l) / 2;
		long long sum = 0;
		for (int i = 0; i < n; i++) {
			sum += ((2*w + a[i])*(2*w + a[i]));
		}
		if (sum == c) {
			break;
		} else if (sum < c) {
			l = w+1;
		} else {
			r = w-1;
		}
	}
	cout << w << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there might be overflow in your mathematical expressions

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there is an overflow 

    for (int i = 0; i < n; i++) {
	sum += ((2*w + a[i])*(2*w + a[i]));
}
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, it is definitely an overflow issue. It passed with long double instead of long long.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        yeah it passed because of long double has 80 bits.

        but better to use __int128 instead, because there can be some unexpected values while dealing with doubles

        another way u could write something like 

        for (int i = 0; i < n; i++) {
	sum += ((2*w + a[i])*(2*w + a[i]));
        if(sum > c)break;
}
        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        use __int128 instead

        → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use the Quadratic equation :> ps: don't use long long but double instead TvT

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think using double is a good idea

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why double accepted, but long long overflow, in statements said w is integer, i tried long long cause thought roots = (-b-+sqrt(D))/2*a too should be integer but its rounded.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I don't think double will get AC, he probably mean long double

        it AC because long double has 80 bits, meanwhile long long has 64 bits

        upd: I was wrong, double got AC, may be double can hold more than long long, but sometimes it cost accuracy.I believe in this problem better to use __int128

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 5   Vote: I like it +1 Vote: I do not like it

        also (x1+2w)^2 + ... + (xn+2w)^2 = c

        c = x1^2 + 4x1w+(4w)^2 ...

        c-=(x1^2 + x2^2 + ... )

        new_c = 4x1w+4x2w+..+4w^2+...(n times)

        c = 4w(x1+x2+...+wn)

        godamn i got it now i did c/=4

        then nw^2 + w(x1+x2+x3...) — c = 0

        and its exceeded in long long but accepted double

        but i can make c/=(n*4) cause 4x1+4x2+4x3... (n times) and (4w^2+..) n times

        and it's accepted long long

        https://codeforces.me/contest/1850/submission/214943996

        upd: seems like (w(x1+x2+x3...+xn))%n doesnt have to be 0 but it's accepted

        Can someone explain why it's have to be 0

        this should be accepted cause gcd should return at least n

        https://codeforces.me/contest/1850/submission/214927321

        → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    Input:
1
10 90
1 1 1 1 1 1 1 1 1 1
Output:
1
    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Amazing contest!. Problems were clear and easy to understand. Difficulty was a bit easier than normal Div4, but great problems nonetheless. Thanks a lot SlavicG mesanu flamestorm and all testers.

→ Reply
»
16 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Worst experience , either you make your platform better or just don't rate the contest, total time waste

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Carrot working for anyone?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I've never seen a predictor working for a contest with a hacking phase

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the problem E like how the answer of 1st test case is 1

thanks....

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial?

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why this is an invalid input for F?: https://codeforces.me/contest/1850/hacks/931609/test I think because the output is bigger than 256 kb, but what to do if I want to test the limits?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one cannot see others hacking test cases, and if you are talking about the test case you wanted to try is large then you can write a code to generate that test case and submit that code.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My G got hacked (TL). Is it because of Python defaultdict? https://codeforces.me/contest/1850/submission/214881069

def solve():

ways = 0
n = int(input())

# read n points

xm = defaultdict(int)
ym = defaultdict(int)
sm = defaultdict(int)
dm = defaultdict(int)
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x, y))
    xm[x]+=1
    ym[y]+=1
    sm[x+y]+=1
    dm[x-y]+=1

for x,y in points:
    ways += xm[x] - 1
    ways += ym[y] - 1
    ways += sm[x+y] - 1
    ways += dm[x-y] - 1



return ways
→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/1850/submission/214941507 Can anybody explain why am I getting TLE for problem F, isn't harmonic series nlogn?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your approach is not harmonic. The countertest is n = 2*1e5 and all array elements are 1.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What should I ideally do?

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        keep frequency map. and increase it by count of each number in array. rather than doing it for every element individually.

        code
        → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems the only codeforces contest with highest participation and with highest problem a solver

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sadly, many people see problem A, if it's difficult, they don't submit ,and hence don't participate. In this contest, A was too easy, thus almost everyone submitted, and participation flooded.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone hack my G or H?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    G, I don't think so. Many Gs were hacked which used unordered_map. Since you used regular map, it won't be hacked, acc to me.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      no I didn't use regular map , I used unordered_map

      scroll up and you will find :

      #define map unordered_map

      but I think it still won't be hacked because I have hash struct passed

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "#define map unordered_map" ohh didn't see this. "but I think it still won't be hacked because I have hash struct passed", then it would be safe ig. GG

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you tell me why map works but unordered map doesn't?

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Unordered map takes O(n) avg time complexity to insert n items. But for certain inputs, it can take O(n^2). Thus, solutions using Unordered_map can be hacked by putting in those specific inputs.

            Refer to this blog bro, for more details- https://codeforces.me/blog/entry/62393

            → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first AK contest on Codeforces!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I used binary search for problem-E but it has some error which I am unable to figure out. Can anyone please help me find error in my binary search logic for my submission 214950555. ? edit : when i set r = 1e10 the sample test-cases passed but on submission it fails again on some test case.

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You need to handle overflow for both multiplication and summation. Better to calculate the sum like this: sum+=(a[i]+2*w)^2 and check if sum > c.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply.

      But it should not overflow as I have taken unsigned long long. also on codeforces custom invocation it did not show any overflow errors. also the code works when i set r = 1e10.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        4*n*m*m would definitely overflow. It’s roughly around 10^23. Put some debug print and check how your binary search behaves for larger n.

        → Reply
»
16 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Me trying to solve problem E be like: photo-2023-07-21-19-46-30
gimme smileys

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me where did i wrong in this code

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    d = [[] for i in range(2 * n)];
    check = [False for i in range(2 * n)];
    checkpos = [-1e18] * (2 * n);
    def dfs(val, u):
        check[u] = True;
        checkpos[u] = val;
        res = True;
        #print(u, val)
        #print(u);
        for v in d[u]:
            #print(v[0], v[1]);
            if(checkpos[v[0]] != -1e18 and checkpos[v[0]] != val + v[1]):
                return False;
            if(check[v[0]] == False):
                #print(u, v);    
                res = res and dfs(val + v[1], v[0]);
        return res;
    def dfscheck(val, u):
        check[u] = True;
        res = True;
        for v in d[u]:
            if(not checkpos[v[0]] - checkpos[u] == v[1]):
                return False;
            if(check[v[0]] == False):
                res = res and dfscheck(val + v[1], v[0]); 
        return res;
    def dfsclear(u):
        check[u] = False;
        for v in d[u]:
            if(check[v[0]] == True):
                dfsclear(v[0]);
    ans = True;
    for i in range(m):
        a, b, dis = list(map(int, input().split()));
        d[a].append((b, dis));
        d[b].append((a, -dis));
    for i in range(1, n + 1):
        if(check[i] == False):
            ans = ans and dfs(0, i);
            dfsclear(i);
            ans = ans and dfscheck(0, i);
    print("YES" if ans else "NO");
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think this code gets RE because the maximum recursion depth has been exceeded in some testcases. Python's maximum recursion depth is 1000, and you can extend the number using

    import sys
sys.setrecursionlimit(300000)

    however, I got memory limit exceeded this time... https://codeforces.me/contest/1850/submission/214955478

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if I haven't solved 5 problems in 5 contests am I unrated for this contest ?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If you have $$$< 1400$$$ rating, you are always rated in Div. 4.

    If you want to appear on the official leaderboard (i.e. standings, when "show unofficial" is off), you need to do what you stated. This does not affect if the contest is rated or not.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why am I getting wrong answers for large test-cases Solution

→ Reply
»
16 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Can someone explain how this $$$\mathcal{O}(n)$$$ solution gets TL? I mean, the constant must be big because of using unordered_maps but still... Is it the case?

https://codeforces.me/contest/1850/submission/214910960

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It's not about the constant, single unordered_map operation takes $$$\mathcal{O}(n)$$$ in worst case. See this

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Didn't know this lol... Thanks for the source!

      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my rating didn't change after this contest?

mesanu flamestorm

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to reach pupil after this contest

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Download some rating prediction extensions. You'll know your rating change during and after contest, before the official release.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw in some people's code of 5th problem, they have used __int128, i am seeing it first time, i want to know how this works!

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    __int128 is a type with 128 bits, ranging from $$$[-2^{127}, 2^{127}-1]$$$;

    while int is a type with 32 bits, ranging from $$$[-2^{31}, 2^{31}-1]$$$.

    You need use a special way to read and write __int128 which you can see in their code.

    In most cases, You can use it like int or long long. But in some STL function, it can't work.

    I found there is a article that may help you.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, can anyone explain why my solution gives a TLE on test 9 when it has the same time complexity as the editorial O(log(n)) and almost the same code.

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

#define mii             map<int,int>
#define test            int t; cin>>t; while(t--)
#define io             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)


int32_t main(){
  io ; test{

    int n;
    cin >> n;
    int a[n];
    mii cnt;
    for (int i = 0; i < n; i++){
      cin >> a[i];
    }
    sort(a, a + n);
    for (int i = 0; i < n;i++){
      if(a[i]>n)
        break;
      for (int j = a[i]; j <= n; j+=a[i]){
        cnt[j]++;
      }
    }
    int mx = 0;
    for(auto x:cnt){
      if(x.second>mx){
        mx = x.second;
      }
    }
    cout << mx << "\n";
  }
}
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This issue with this kind of a naive approach was explained here before, in the worst case if all frogs have a hop length of at most $$$1$$$ the time complexity of this code isn't harmonic series $$$O(nlogn)$$$, but rather $$$O(n^2)$$$, because you are going to iterate $$$n$$$ times over all elements of an array of length $$$n$$$.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain why in the second loop we increment the counter by the value of i , I still don't understand how that works

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If by the second loop you mean this nested loop:

        for (int j = a[i]; j <= n; j+=a[i])

        this basically simulates leaps of a frog, all frogs start at an integer point 0 on a coordinate line, after the first jump frog i will be at a position a[i], then after a second jump at a position 2 * a[i] and so on.

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          where did j=a[i] and j+=a[i] , in the second loop come from

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            • In this problem we are asked to place a trap at some integer coordinate that lies inside (ends included) a segment $$$[1;n]$$$ so that we maximize the amount of frogs caught.
            • Finding the answer to this problem is the same as counting for each point in a $$$[1;n]$$$ range the amount of distinct frogs that are going to visit that point and then taking the maximum amount.
            • A straightforward way to do that is to simulate the leaping process of each frog.
            • Knowing that at the beginning each frog sits at a point with a coordinate $$$0$$$ and knowing a hop length of each frog we can simulate a frog hopping from 0 with a for loop
               for (int j = a[i]; j <= n; j+=a[i])

            We start at a position of a frog i after its first jump (j = a[i]) and then the frog keeps hopping with its hop length a[i], increasing its position after each jump (j+=a[i]), as mentioned before.

            → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry,may I ask a stupid problem? Why is it different between the rank I see in "common standing"and "friend standing". I am sure that its both "only show official". Thx

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In common standings, all the participant's world rank will be visible. Whereas, in friends standings, you can see your rank in your friend list, and ranks of your other friends in your friend list, and their world rank in bracket().

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was my first contest ever. I solved three of them but didn't get any rating. Can someone please explain?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, nobody got the rating changes now, but we're waiting for them to be updated. So, you need to wait(i don't know how much)till you get your rating.

    → Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In this contest can my E be WA, G be TL?

My submission in E in contest: 214829184. I don't know how it's passed pretests. In code wrongly I did: x = s[i] + 2 * md + 1 and printed l but x should be s[i] + 2 * md and printed l — 1. Like this code: 214997775 which I submitted after contest. Please let me know if it's hackable.

My submission in G in contest: 214869824. Can it be TL or ML? It passed pretests with 1668 ms 76900 KB(Time limit is 2s). After contest I optimized it (removed set) and passed pretests with 904 ms 39300 KB(214997753). Please let me know it's hackable.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this contest showing unrated?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will show rated, but we have to wait until we get the new ratings.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

me waiting for system test and rating changes

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem E, to use quadratic equation, it's not necessary to use int128. It's ok to use long double to store, and convert it back to long long at last. Submission. Note that I defined ll as long double

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why this contest wasn't ranked for me?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to wait, usually 2-3 days after contest for the rating changes

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

study time

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

dayum, i got hacked on F and G because i using unordered_map, lesson learned haha

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Does anyone have an idea why would my submission get WA2 on C even though it previously got AC in the contest 214793463 ?

I don't have any undefined behavior nor do I see any other error.

Thanks.

UPD: I found the bug, turned out I had an j instead of an i somewhere but it's weird it somehow passed the pretests during the contest.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

(sighed) i got T again on an easy greedy preblem due to using the Arrays.sort()214808599...Sometimes i really cant tell the difference between using Arrays.sort() or Collections.sort()215048831 ,let alone passing the pretest -_-|

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sometimes problems are good in their own sense but often we make it more beautiful the way we approach problems. This is for G, I was thinking about the rotation of the axis by 45 degrees and then come to the conclusion that the coordinates after rotation of (x, y) are ((x + y)/sqrt(2), (-x + y)/sqrt(2)). So, I just have to store x+y and -x+y values in a map. We can also think of it as a straight line which is a more direct way but I felt this good (:

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why I use "map<int,int>"could pass G, but use "unordered_map<int, int>" couldn't pass it ?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explaine how Wrapper function works? This is my hacked submission: https://codeforces.me/contest/1850/submission/214906792. And then i fixed it by Wrapper function which make my submisson accept https://codeforces.me/contest/1850/submission/214984466 *sorry for bad english

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it allows for you to define a custom hashing function, which makes it less likely to be hacked by anti hashing tests

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks to this contest i got to specialist :D

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding Maths solution for E problem

Why I get compilation error for this solution: https://codeforces.me/contest/1850/submission/215091151

but this other solution works: https://codeforces.me/contest/1850/submission/214911845

im going crazy, literally same thing

Pleasse help someone

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Although I participated in my first-ever contest and I did solve 3 questions in quick time, why is there no change in my rating?

Could anyone please let me know about this??

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You just upsolved three problems. Upsolved meaning, you have solved those three problems after the contest has ended. if u had solved those three problems during the allocated contest period, then you definitely would have got some positive delta.

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to register on codeforces.com/contests.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, "You can also use the quadratic formula, but be careful about implementation of square root and precision issues."" so how can I be careful about the square root and precision??

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use long double (if you are using C++)

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello can anyone tell me problem F topic (I know it will be number theory but witch concept in number theory should I learn to solve it)

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1/1 + 1/2 + ... + 1/n = O(ln n). That's why standart colution is O(n log n) but NOT O(n^2)

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey I am a newbie, why this contest as unrated for me? According to this statement "take part in at least five rated rounds (and solve at least one problem in each of them)" they marked as unrated for me

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The ratings are rolled back. The system is filtering out the cheaters. It will give the ratings back after checking in a few hours.

    → Reply
»
11 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Nice contest.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In G I get TLE when using unordered_map but Accepted when changing it to map. I thought the access time was faster when using unordered_map, then how come the program is slower with unordered_map?

https://codeforces.me/contest/1850/submission/239099614

→ Reply