SlavicG's blog

By SlavicG, history, 3 years 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, moonpieXXIV, mafailure, MagnusCarlsen321_alt, JuicyGrape, Qualified, haochenkang, ZiadEl-Gafy, MADE_IN_HEAVEN, AdOjis485, qwexd, mkisic, SmartCoder, 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

| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

My first unrated round! :)

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Finally Div:4 after long time. I think because Div.4 it's easy to reach pupil .

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

By the way, what is the difficulty of this game

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

official participant with highest rating

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Looking forward to my first out of competition round!

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Dattebayo

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

First unrated contest

»
3 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

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

»
3 years ago, hide # |
 
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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hoping to reach specialist after this contest!

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, hide # |
 
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!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Excited to become Newbie for the first time !

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why only 120 minutes why note 135 minutes

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Waiting....

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Good luck to everyone

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello everybody!

I wish you all good luck! I would like to become a student (green). I hope that the competition will be interesting.

Best, Jelal

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hoping to solve all problems!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hopefully i reach spec again after this

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope it be my last rated div 4 contest

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Alright, iron contest!!!

»
3 years ago, hide # |
 
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 $$$ \lt 1400$$$, and the previous one (with Vika) is for rating $$$ \lt 2000$$$ or something, I now think this round is gonna be easier..?

»
3 years ago, hide # |
 
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.

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope i become a specilast again

»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

div5

»
3 years ago, hide # |
 
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...

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

My first *out of competition :)

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My first rated competition.

»
3 years ago, hide # |
 
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

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

the first contest that I aked !!!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Div 4.5

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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;
}

»
3 years ago, hide # |
 
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://mirror.codeforces.com/contest/1850/submission/214926782

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

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
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

  • »
    »
    3 years ago, hide # ^ |
    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)
»
3 years ago, hide # |
 
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)?

  • »
    »
    3 years ago, hide # ^ |
     
    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

    • »
      »
      »
      3 years ago, hide # ^ |
       
      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;

»
3 years ago, hide # |
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;

}

  • »
    »
    3 years ago, hide # ^ |
    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}$$$ ?

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

We want div-4 contest more often as beginer

»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

best div 4 contest ever

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, hide # |
 
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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thanx Man i Really enjoy this Round

»
3 years ago, hide # |
 
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 :(

»
3 years ago, hide # |
 
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.

  • »
    »
    3 years ago, hide # ^ |
     
    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

  • »
    »
    3 years ago, hide # ^ |
     
    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)

»
3 years ago, hide # |
 
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();
	}
}
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    there might be overflow in your mathematical expressions

  • »
    »
    3 years ago, hide # ^ |
     
    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]));
    }
    
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        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;
        }
        
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        use __int128 instead

  • »
    »
    3 years ago, hide # ^ |
     
    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

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I don't think using double is a good idea

    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        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

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        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://mirror.codeforces.com/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://mirror.codeforces.com/contest/1850/submission/214927321

  • »
    »
    3 years ago, hide # ^ |
    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
    
»
3 years ago, hide # |
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.

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is Carrot working for anyone?

»
3 years ago, hide # |
 
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....

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

editorial?

»
3 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

why this is an invalid input for F?: https://mirror.codeforces.com/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?

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My G got hacked (TL). Is it because of Python defaultdict? https://mirror.codeforces.com/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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      What should I ideally do?

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
»
3 years ago, hide # |
 
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

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone hack my G or H?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My first AK contest on Codeforces!

»
3 years ago, hide # |
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.

  • »
    »
    3 years ago, hide # ^ |
    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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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.

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
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");
»
3 years ago, hide # |
 
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 ?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    If you have $$$ \lt 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.

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
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://mirror.codeforces.com/contest/1850/submission/214910960

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why my rating didn't change after this contest?

mesanu flamestorm

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope to reach pupil after this contest

»
3 years ago, hide # |
 
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!

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
 
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";
  }
}
  • »
    »
    3 years ago, hide # ^ |
     
    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$$$.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      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

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        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.

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            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.

»
3 years ago, hide # |
 
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

  • »
    »
    3 years ago, hide # ^ |
     
    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().

»
3 years ago, hide # |
 
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?

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
3 years ago, hide # |
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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why this contest showing unrated?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

me waiting for system test and rating changes

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

study time

»
3 years ago, hide # |
 
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

»
3 years ago, hide # |
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.

»
3 years ago, hide # |
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 -_-|

»
3 years ago, hide # |
 
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 (:

»
3 years ago, hide # |
 
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 ?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

thanks to this contest i got to specialist :D

»
3 years ago, hide # |
 
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://mirror.codeforces.com/contest/1850/submission/215091151

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

im going crazy, literally same thing

Pleasse help someone

»
3 years ago, hide # |
 
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??

»
3 years ago, hide # |
 
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??

»
3 years ago, hide # |
 
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)

  • »
    »
    3 years ago, hide # ^ |
     
    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)

»
3 years ago, hide # |
 
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

  • »
    »
    3 years ago, hide # ^ |
     
    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.

»
2 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

Nice contest.