Educational Codeforces Round 173 [Rated for Div. 2]

5 weeks ago, # ^ |

← Rev. 2 →

-12

→ Reply

MKasirloo

5 weeks ago, # |

Wrong answer on test 4...

→ Reply

sandbag

5 weeks ago, # |

Can anyone prove a bound for problem D? I just did yolo n=1000 and was surprised it passed lol

→ Reply

5 weeks ago, # ^ |

I have a proof for 50 x 50 bound, but unfortunately it gets TLE

→ Reply

TeletubiGaim33

5 weeks ago, # ^ |

It just worked for me. Cool I guess, but still hate the problem If you care: 298307075

→ Reply

5 weeks ago, # ^ |

How did you do it?

→ Reply

TeletubiGaim33

5 weeks ago, # ^ |

The only difference between our implementations as far as i can tell is that i use __gcd(a,b) to find the gcd and break after finding the furthest r for each l [l, l+50].

→ Reply

mridul1809

5 weeks ago, # ^ |

1000? I kept getting TLE for 100, 70 and 50

It got accepted with 20 at the end.

→ Reply

vermish77

5 weeks ago, # |

+16

wtf is test 4 of problem C :-(

→ Reply

nkxyzxy

5 weeks ago, # ^ |

I know right

→ Reply

kauan.fank

5 weeks ago, # ^ |

← Rev. 3 →

test if it works for this input

-1 10 -1

-1 1 10 1 -1

→ Reply

vermish77

5 weeks ago, # ^ |

← Rev. 2 →

5
-1 0 8 9 10 
6
-1 0 1 10 11 12

I got this as the answer, I think this is correct

→ Reply

suryansh0_0

5 weeks ago, # ^ |

-1 0 8 9 10

-1 0 1 10 11 12

me tooo but idk test 4

→ Reply

kauan.fank

5 weeks ago, # ^ |

yeah, that's right, that was the input that was giving me WA, I got accepted after fixing that. Doesn't matter too much now as it is already possible to see the input that give the wrong answer on the submission.

→ Reply

vermish77

5 weeks ago, # ^ |

Got the mistake, was making a very bad algorithmic error in case of counting only 1s and -1s cases, I am just surprised that it didn't got WA on test 2

→ Reply

daud04

5 weeks ago, # ^ |

← Rev. 2 →

When you are adding numbers with the Different one, you can only add an subarray that is adjacent to the Different number from both side. (it was my approach that got wa on 4)

→ Reply

nkxyzxy

5 weeks ago, # ^ |

I took that into account, I think, still getting WA on 4. Can someone please take a look? 298297481

→ Reply

_gajju

5 weeks ago, # ^ |

i also got the same issue but finally got accepted

→ Reply

dhananjay.chimnani

5 weeks ago, # ^ |

← Rev. 2 →

You can take 2 cases:

case-1: Subarrays to the left and right of x which do not contain x.

case-2: Subarrays that contain x.

For case-1, apply the kadane algorithm to get the maximum and minimum subarray sum. As the array is made of -1 and 1, all the numbers between this maximum and minimum value will be a part of our answer.

For case-2, calculate the maximum and minimum subarray sum to the left of x and to the right of x. Now we have two ranges, [minleft,maxleft] and [minright,maxright]. Therefore all our sums lie in the range [minleft + minright + x, maxleft + maxright + x]. Again as our array is made of -1 and 1, all the sums lying between the two values will be a part of our answer.

→ Reply

nkxyzxy

5 weeks ago, # ^ |

I think I get it now, I was using a silly assumption to get the lower and upper bounds for case 1 (max consecutive -1's and +1's), rather than using Kadane's algorithm. Thanks.

→ Reply

dhananjay.chimnani

5 weeks ago, # ^ |

Yes even I did the same during contest. I saw most people got a WA on the fourth testcase. I think everyone made this error.

→ Reply

utk7rsh

5 weeks ago, # ^ |

case-2 as you described, max and min subarray sums to the left and right of x, they contain x right?

→ Reply

Shoeib

5 weeks ago, # |

+29

i'll never participate in edu. rounds again

→ Reply

5 weeks ago, # |

+16

How to solve problem E ?

→ Reply

-VM-

5 weeks ago, # |

+26

L Contest.

→ Reply

5 weeks ago, # ^ |

what is meaning of L bro ?

→ Reply

-VM-

5 weeks ago, # ^ |

-11

It means that the contest is bad. Too much math.

→ Reply

heavenly_principles

5 weeks ago, # |

+89

worst educational round ever

→ Reply

vitosevski

5 weeks ago, # ^ |

+28

woah woah woah bro there has been much worse

→ Reply

winner2050

5 weeks ago, # ^ |

D also has weak pretests

→ Reply

donpaul2718

5 weeks ago, # |

couldn't submit anything in the last 3 minutes.

→ Reply

sammyuri

5 weeks ago, # |

+28

G is a cool problem

→ Reply

Chaeryeong

5 weeks ago, # ^ |

How to solve it? I have no idea

→ Reply

sammyuri

5 weeks ago, # ^ |

+24

First reformulate the problem into counting equal pairs rather than unequal pairs. Split into blocks of size $$$B$$$. We can maintain block_ans[i][j] which stores the answer for all the blocks in the range $$$[i, j]$$$ (there are $$$\frac{n^2}{B^2}$$$ such ranges), and block_prefcnt[i][j] which stores for each value $$$i$$$, its count in the first $$$j$$$ blocks. They can be updated in $$$O(\frac{n^2}{B^2} + \frac{n}{B})$$$ and using those values you can do queries in $$$O(B)$$$ (the idea is similar to square root decomposition). Then you just need to choose the right value of $$$B$$$, if you let it be about $$$n^{\frac{2}{3}}$$$ then the complexity is $$$O((n + q) \cdot n^{\frac{2}{3}})$$$ (I just fixed it to $$$1000$$$ though and that was fast enough).

→ Reply

Chaeryeong

5 weeks ago, # ^ |

← Rev. 2 →

Clever solution!

→ Reply

sammyuri

5 weeks ago, # ^ |

After a small amount of hacking I now have first solve on G... although my solutions will most likely fail system tests to my own hack cases lol (they are vulnerable to being hacked in the same way)

→ Reply

tickbird

5 weeks ago, # |

+31

thank you for giving worst ever-experience on Christmas in my life.

→ Reply

gabriel88766

5 weeks ago, # |

← Rev. 3 →

+27

For problem F, I solved each query in a dp with at most $$$7*64*50$$$ operations, worst case $$$2.2*10^9$$$. 1109 ms.. The case when $$$r-l+1 > 50$$$ is easier, if there is any 0, then choose 0, otherwise there is some number with 2 or more reps, choose any pair of those.

→ Reply

jkulanko

5 weeks ago, # |

Wow, I'm bad. 10k solves on Q2 and I couldn't figure it out after spending an hour on it. Then finally moved on to q3 and solved with 30 seconds left in the contest

→ Reply

dreameater69

5 weeks ago, # ^ |

what changes did u make to pass the tc 4 ?

→ Reply

jkulanko

5 weeks ago, # ^ |

I was looking at: min(minLeftOfUnique,minRightOfUnique) to the max(maxLeftOfUnique,maxRightOfUnique). Once I changed it to the min(0,minLeftOfUnique)+min(0,minRightOfUnique) to the max(0,maxLeftOfUnique)+max(0,maxRightOfUnique), then it passed.

→ Reply

dreameater69

5 weeks ago, # ^ |

I just noticed I made a slight error.. I mistakenly wrote x instead of abs(x) at one point and got the entire problem wrong .

→ Reply

suryansh0_0

5 weeks ago, # ^ |

if(other!=-1){
            int val;
            s.insert(arr[other]);// other is index of element != -1 or 1
            int leftmin=0;
            int rightmin=0;
            int leftmax=0,rightmax=0;
            val=0;
            for(int i=other-1;i>=0;i--){
                val+=arr[i];
                leftmin=min(leftmin,val);
                leftmax=max(leftmax,val);
            }
            val=0;
            for(int i=other+1;i<n;i++){
                val+=arr[i];
                rightmin=min(rightmin,val);
                rightmax=max(rightmax,val);
            }
            int start=leftmin+rightmin;
            int end=leftmax+rightmax;
            for(int i=start;i<=end;i++)
            s.insert(arr[other]+i);
        }

what's wrong with this one?

→ Reply

barbarian

5 weeks ago, # ^ |

I guess you arent adding the element X on both start and end try it

→ Reply

blablabla1803

5 weeks ago, # |

← Rev. 3 →

nvm

→ Reply

https://www.geeksforgeeks.org/find-a-co-prime-pair-with-maximum-difference-in-a-given-range/

5 weeks ago, # ^ |

You are legendary grandmaster. figure out yourself bro ...

...

Spoiler

I looked at your code, but I can't understand without comment. I can share the approach I have used.

1) Split the array in two parts from the "DIFFERENT" element.

2) Find out maximum subarray sum and minimum subarray sum, of those two partitioned arrays. ( for that, you can write single function, and then make a call to function twice ) .

3) [ a1,a2,a3 ... ai, X , a(i+2) , a(i+3) ... ] Find out minimum and maximum spans, such that rightEndpoint of your subarray is a[i]. Similarly find out minimum and maximum spans such that leftEndPoint is a[i+2].

Then in total you will have range from [min1 + min2 + X  , max1 + max2 + X] .

→ Reply

cleanser

5 weeks ago, # |

← Rev. 2 →

-10

D ^

Edit: doesn't work oops

→ Reply

5 weeks ago, # ^ |

As we know that GCD(N, N + 1) is always 1 and we need to find the maximum difference of the pair with GCD 1 so GCD(L, R – 1) and GCD(L + 1, R) will be one as GCD(L, L + 1) and GCD(R – 1, R) will be 1 so there cannot be any common factors between (L and R – 1), and (L + 1, R).

How is this True? What about L = 15 and R = 64

→ Reply

cleanser

5 weeks ago, # ^ |

gcd(15, 64) = 1 so use that.

→ Reply

5 weeks ago, # ^ |

But the statement itself is still false

→ Reply

BledDest

5 weeks ago, # ^ |

← Rev. 2 →

+65

It does not actually work, like a lot of stuff from geeksforgeeks

upd: for example, if you take $$$14$$$ and $$$36$$$:

$$$gcd(14, 36) = 2$$$
$$$gcd(15, 36) = 3$$$
$$$gcd(14, 35) = 7$$$
$$$gcd(15, 35) = 5$$$

→ Reply

10k people solved C, only 4k solved B

5 weeks ago, # ^ |

← Rev. 5 →

-23

Small request BledDest.

why not save these kind of tricky B problems for Div(1 + 2) rounds. It makes sense to use such an intellectual problems when GM and LGM's are competing rated.

Look at this past EDU history,

8k solved C, only 7k solved B.

10k solved A, only 5k Solved B.

May be you have this thought process in mind that "during EDU round, each problem has equal points, so may be, if problem is difficult, then participants should skip the problem and solve next one". And from ICPC point-style, it makes sense also.

My humble request is, to save such an intellectually, math-involved problems for BIG-ROUNDS, and let the Div-2 people enjoy their life peacefully !!!!

→ Reply

BledDest

5 weeks ago, # ^ |

+16

You have a point, there have been some difficulty issues in the past. But I don't agree that today's B is really as intellectual and math-involved as your (and many others') comment suggests.

Yes, it has a solution which is very math-involved (checking all divisibility rules for $$$3$$$/$$$7$$$/$$$9$$$). But this is not the only way to solve the problem. There are other, much less "mathy" ways. I will illustrate one of them in the official editorial.

→ Reply

5 weeks ago, # ^ |

Today's B was fine for me, but many people struggled. So based on the data-points and opinion evaluation, I shared my thoughts.

I have seen much worse B problems in past EDU. so I am way above this discussion now. It's just my suggestion, to save good problems for Big contest...

→ Reply

sho_eib_w_sho_msh_eib

5 weeks ago, # ^ |

last Edu. rounds have a lot of problems which u must get about 3-5 WA before getting AC.
I'm not saying that all of these problems were bad (i love a lot of them),
but they have a lot of corner cases / guesses / luck which ruins the contest especially when the contest have more than one problem like that, or these problems positions are B.

Thanks

→ Reply

5 weeks ago, # ^ |

When will you release the editorial. I have been waiting for it for some time now.

→ Reply

vstiff

5 weeks ago, # ^ |

← Rev. 2 →

Here is B solved by pure bruteforce, math'd only division by 5:298342531

→ Reply

om.nom

5 weeks ago, # |

+14

Man I could have solved C if there was a little more time left. WTF was B ??? took me 1 hour.

→ Reply

kauan.fank

5 weeks ago, # ^ |

yeah, time was tough for me too, i'm still too slow. For C I thought that I was on the time, the contest was supposed to last until 13:45 and I submited at 13:41, but I don't know why it had already ended.

→ Reply

jkulanko

5 weeks ago, # |

How to solve B? I feel like an idiot for not being able to figure out the trick. Finding the answer for 1,3,5,9 seemed simple but I couldn't figure out 7 to save my life

→ Reply

sandbag

5 weeks ago, # ^ |

I can't prove that my solution works. But I found the first repeating number divisible by each odd number and compared it to the length of the repeated number.

Code

void solve(){
    int n, d;
    cin >> n >> d;
    vector<int> ans;
    for (int i = 1; i <= 9; i+=2) {
        int cur = d;
        int len = 1;
        bool ok = false;
        if(cur%i==0) ok = true;
        while(cur%i && cur <= 1e17) {
            cur = cur*10+d;
            if(cur%i == 0) ok = true;
            len++;
        }
        bool ok2 = false;
        if (len <= n) ok2 = true;
        if (fac(n) % len == 0) ok2 = true;
        if(ok && ok2) ans.push_back(i);
    }
    for (auto i : ans) cout << i << " "; cout << endl;
}

→ Reply

om.nom

5 weeks ago, # ^ |

It took me 1 hour to figure out, so according to divisibility rule of 7, ddd...d — 2 * d where ddd...d contains n! — 1 digits should be divisible by 7, so take d common and we have d( 111..1 — 2). Now either d is divisible or other one. If other one is divisible then by rule 111..1 which contain n! digits is also divisible. Now just divide 1111.... by 7 and you will find that this is only divisible by 7 if length is divisible by 6. So n! must be divisible by 6 which means n >= 3.

→ Reply

lightph

5 weeks ago, # ^ |

If any number divides the given number for some n, then it automatically does for all n greater than that one. For example, since for n = 3, d = 3, 333333 is divisible by 7, all other numbers with d=3 and n>=3 will also be divisible by 7. You can see that by expressing the higher n numbers as sums of multiples of the previous ones by powers of 10. So, if you check for each digit you see that for n=3, 7 is always a factor. So for all possibilities with n>=3, 7 is a factor. Now for n<=2, the only possible case in which it is divisible by 7 is if the digit itself is 7.

→ Reply

bithal

5 weeks ago, # ^ |

in the question you can see the given number can be represented by d*11111111(n! times).So you can observe 11111..... (x times ) is divisible by 7 if and only if x is a multiple of 6 so when n=3 ,n! becomes 6 afterwards all the factorial will be divisible 6

→ Reply

New_and_simple

5 weeks ago, # ^ |

d*1111.... = d/9(9999....) = d/9(10^(n!) — 1) 10^(n!) = 1 (mod 7) => 3^(n!) = 1 (mod 7) Every 6th cycle, remainder repeats Being 0 at n = 6k where k= 1,2,3...

→ Reply

Astroflexx

5 weeks ago, # |

I'm 1592 2.6k rank (Div 2 only) can I get to 1600? (after hacking phase and system tests)?

→ Reply

TCS_Bhediya

5 weeks ago, # ^ |

YES

→ Reply

elseecay

5 weeks ago, # ^ |

for 1600 u need ~2k place in div2

→ Reply

sandbag

5 weeks ago, # |

Is D meant to be solved deterministically? I figured that the probability any two numbers are coprime is so high that we might as well try the first 1000 numbers in the segment. It passes.

Code

void solve(){
    int l, r, g;
    cin >> l >> r >> g;
    int a = l/g;
    if(l%g) a++;
    int b = r/g;
    vector<int> ans = {-1, -1};
    int d = 0;
    int cnt = 0;
    while(a<=b && cnt<1111) {
        for (int i = 0; b-i>=a && i < 10000; i++) {
            int tb = b-i;
            if(__gcd(a,tb) == 1  ) {
                if ( (tb-a > d) || ans[0] == -1) {
                    d = tb-a;
                    ans = {a, tb};
                }
                break;
            }
        }
        cnt++;
        a++;
    }
    if(ans[0] != -1) {
        ans[0] *=g;
        ans[1] *=g;
    }
    cout << ans[0] << " " << ans[1] << endl;
    
}

→ Reply

_Crimson_

5 weeks ago, # ^ |

-8

Actually, prime numbers are pretty regularly distributed. So you can always find a prime number on a long enough segment. That's why yours and similar solutions work.

→ Reply

heWhoCooks

5 weeks ago, # ^ |

-16

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10^9 maximal distance is 282

→ Reply

5 weeks ago, # |

Mathforces. Nice problems no Alice wants to stay on the left and bob doing some crazy thing and me shouting at my homie like whatttt. Anyways problem D is it find the 2 most separate coprime in the range ceil(l/G) and floor(r/G) is this the solution?

→ Reply

https://t.me/codeforces_answers

5 weeks ago, # ^ |

← Rev. 2 →

nvm. I typo caused me the problem D and -50. I typo

→ Reply

imLLUSION

5 weeks ago, # |

forgot about the contest, started when 10 mins were left, got TLE in first ques with 30 seconds left. Ls

→ Reply

catchTheCheater

5 weeks ago, # |

Cheating groups like these ruin the spirit of Codeforces and sharing of answers on these temper the ranking. Strict action should be taken against such cheaters.

→ Reply

iordache_

5 weeks ago, # |

+38

A<D<C<B

→ Reply

dsa-Daddy

5 weeks ago, # |

Second question was tricky

→ Reply

dsa-Daddy

5 weeks ago, # ^ |

yes it was tricky

→ Reply

5 weeks ago, # ^ |

+43

who is bro talking to

→ Reply

5 weeks ago, # |

+18

Never knew that Div2D could be solved with just two nested loops.

→ Reply

wuhudsm

5 weeks ago, # |

+18

I guess Problem B that will go down in history ;)

My Solution of $$$E$$$:

First, each bit is independent. So we only need to consider $$$a$$$ and $$$b$$$ as binary matrices.

We observe that if the last operation is operation 2, then there must be a column in $$$b$$$ that is all 1s; if the last operation is operation 1, then there must be a row in $$$b$$$ that is all 0s.

We can find the columns in $$$b$$$ without any 0s and the rows in $$$b$$$ without any 1s, and set all the numbers in these positions to the wildcard -1. Repeat this process until no more operations can be performed. Finally, compare $$$a$$$ and $$$b$$$.

A brute-force simulation of this process might cause a timeout. Using BFS can reduce the complexity to $$$O(mn)$$$. 298292699

→ Reply

5 weeks ago, # ^ |

Bro, can you explain a little bit please. I tried watching the stream of youtubers who attempted this contest but nobody gave a way to arrive at a solution. Can you please help with the editorial until the official one is out.

→ Reply

vstiff

5 weeks ago, # ^ |

Different approach, but I think it's easier to code and come up with.

Iterate over each column, find $$$x$$$ that will have all missing bits in a that are set in b, then apply it to column $$$a_{ij} |= x$$$. Basically, because there is no other way to get a = b otherwise.
Iterate over each row, find $$$x$$$ that will have no extra bits set in b, then apply it to row, $$$a_{ij} \&= x$$$
Compare a and b.
Unfortunately this is not a solution yet, because when you change one number a to b it will break others in row/col, but it's bits are still may be "compatible". So we need to repeat this process until we get something we already tried. I used hash for this, but some just make 30 iterations and it passes.

→ Reply

Rating_10101010

5 weeks ago, # |

I will really become a gray name in this round. Is it magic?

→ Reply

Typed_SIGTERM

5 weeks ago, # |

Sorry I have a sad Christmas Eve T_T

→ Reply

TCS_Bhediya

5 weeks ago, # |

Can someone tell me where am i doing wrong in C. 298296633

→ Reply

TCS_Bhediya

5 weeks ago, # ^ |

wtf, i didn't write the number of elements in set for the case of (n == 1) I was handling and this costed me the whole problem... lmao (too much pain).

→ Reply

5 weeks ago, # ^ |

hehe, I did same for my C's first submission.

→ Reply

5 weeks ago, # |

← Rev. 3 →

-20

I was wrong A tests were trash for real

→ Reply

5 weeks ago, # ^ |

+11

One of the most enjoyable ~~edu rounds imo~~ IMO edu rounds.

→ Reply

EastMaple

5 weeks ago, # ^ |

No, consider $$$[6, 9]$$$, the two numbers that are farthest apart and coprime are $$$7$$$ and $$$9$$$, both odd numbers.

→ Reply

5 weeks ago, # ^ |

cool , my greedy was wrong , ok thanks for breaking the illusion xD

→ Reply

Egor

5 weeks ago, # |

+14

Video of me solving this contest in rust will eventually be available here

→ Reply

5 weeks ago, # |

← Rev. 2 →

+64

Thanks for the christmas eve contest ! As usual, here is my advice about the problems

Overall optinion

→ Reply

5 weeks ago, # ^ |

→ Reply

5 weeks ago, # ^ |

Which problem do you need help on ? I don't mind sharing the intuitions to solve each problem

→ Reply

5 weeks ago, # ^ |

Well I wanted to ask mainly about D & E but now the editorial is out. I'll read that. Thanks for your reply though.

→ Reply

om.nom

5 weeks ago, # |

How to find condition for 7 in B

According to divisibility rule of 7, ddd...d — 2 * d (where ddd...d contains n! — 1 digits) should be divisible by 7, so take d common and we have d( 111..1 — 2). Now either d is divisible or other one. If other one is divisible then by rule 111..1 which contain n! digits is also divisible. Now just divide 1111.... by 7 and you will find that this is only divisible by 7 if length is of the form 6k. So n! must be divisible by 6 which means n >= 3.

So final condition is ((d % 7 == 0) || (n >= 3))

→ Reply

5 weeks ago, # ^ |

there are two cases :

if $$$d=7$$$ then it's trivial that it's divisible by $$$\underbrace{11111...111}_{n!}$$$
.$$$d \neq 7$$$ then $$$\underbrace{11111....1111}_{n!}$$$ is only divisible by 7 , if $$$n!$$$ is a multiple of $$$6$$$ then $$$n! \ge 6 \implies n \ge 3$$$ (why idk , I just bruteforced it and took pattern)

→ Reply

Carousel

5 weeks ago, # ^ |

← Rev. 2 →

$$$\displaystyle \underbrace{ddd\dotsc dd}_{n!} = d \cdot \sum_{k=0}^{n!-1} 10^k=d \cdot \frac{10^{n!} - 1}{9}$$$ $$$\displaystyle d \cdot \frac{10^{n!} - 1}{9} \equiv 0 \pmod{7} \implies d \cdot (10^{n!} - 1)$$$

since $$$\gcd(7,9 = 1)$$$, so we have two cases:

$$$d = 7$$$, trivially divisible by $$$7$$$
$$$10^{n!} - 1 \equiv 0 \pmod{7} \implies 10^{n!} \equiv 1 \pmod{7}$$$

We note that $$$6$$$ is the order of $$$10 \in \mathbb{Z}_7$$$, by Fermat's Little Theorem (or Euler's Totient Theorem), we must have $$$6 \mid n! \implies n \geqslant 3$$$

→ Reply

Dan4Life

5 weeks ago, # ^ |

← Rev. 3 →

$$$10^{x} \mod 7 (x>=0)$$$ has a period of 6: $$$1, 3, 2, 6, 4, 5, 1...$$$

The sum of the first 6 numbers is 21 which is divisible by 7 therefore $$$dddddd$$$ is also divisible by 7 and hence n-digit numbers (where n is divisible by 6 and all digits are the same) is also divisible by 7 because the period is 6.

→ Reply

BLACKCOFFEE-420

5 weeks ago, # |

my dream of becoming expert in this contest remain dream only :((((

→ Reply

UP84

5 weeks ago, # |

← Rev. 2 →

+33

Why make D, stop making proof by AC.

→ Reply

5 weeks ago, # |

For D, if the answer exists, it is only necessary to check $$$(l_1 + k \cdot g, r_1 - s \cdot g)$$$ for $$$0 \leq k, s \leq 5$$$ where $$$l \leq l_1 \leq r_1 \leq r$$$ and $$$l_1, r_1$$$ are divisible by $$$g$$$ (that is, the minimum and maximum numbers in the range that are divisible by $$$g$$$).
submission

→ Reply

noobcoder180

5 weeks ago, # ^ |

-9

interestingly, you only need to check $$$[l_1, r_1$$$], $$$[l_1 + 1, r_1]$$$, $$$[l_1, r_1 - 1]$$$

→ Reply

5 weeks ago, # ^ |

Wait it's incorrect, isn't it?

→ Reply

NeverSpot

5 weeks ago, # ^ |

Can you please tell me why and what is correct way to get to 5 instead of 1?

→ Reply

5 weeks ago, # ^ |

Clearly, the problem boils down to this: there is a segment $$$[l, r]$$$ find a pair $$$l_1, r_1$$$ in it such that $$$l \leq l_1 \leq r_1 \leq r$$$ and $$$gcd(l_1, r_1) = 1$$$ and $$$r_1 - l_1$$$ is maximal. Intuition tells me that if the answer exists, then $$$l_1 \sim l$$$ and $$$r_1 \sim r$$$, by $$$\sim$$$ I mean that $$$|l_1 - l| < C$$$ for some $$$C$$$. In contest, I got $$$AC$$$ by putting $$$C = 25$$$, but it's actually a lot more than I need.

In other words, it's hard to say why $$$5$$$ is enough, but right after reading this, my intuition tells me that the problem is solved like this.

→ Reply

NeverSpot

5 weeks ago, # ^ |

Yes, I also fixed C = 10 but I don't understand why....I just made a guess... I want to know why this will work.

→ Reply

timreizin

5 weeks ago, # ^ |

How to prove that?

→ Reply

phsads

5 weeks ago, # ^ |

← Rev. 2 →

hacked :D https://codeforces.net/contest/2043/hacks/1106554

→ Reply

phsads

5 weeks ago, # ^ |

← Rev. 2 →

L        R

mod 2:  1        0

mod 3:  0        1

mod 5:  0        0

mod 7:  0        3

mod 11: 0        4

mod 13: 11       2

mod 17: 16       1

mod 19: 18       3

mod 23: 21       0

mod 29: 27       1

mod 31: 29       3

mod 37: 0        2

mod 41: 37       1

mod 43: 39       0

this might also be hackable with k,s <= 6 (im not quite sure for 7 tho) (and something like 10 or 12 is 100% safe i think)

→ Reply

https://codeforces.net/contest/2043/submission/298219615

5 weeks ago, # ^ |

← Rev. 2 →

thanks! :)

→ Reply

cleanser

5 weeks ago, # |

For D, what's bounds do you have to iterate on?

→ Reply

EastMaple

5 weeks ago, # |

In problem D, why can we do $$$O(n^2)$$$ enumeration like this, is there any mathematical proof?

→ Reply

Misuki

5 weeks ago, # ^ |

← Rev. 3 →

If you find two prime $$$p, q$$$, it's definitely good, and the distance between two prime is around $$$O(lg^2 C)$$$ so if you enumerate like that, it would stopped very quickly.

btw, it's known as prime gap

→ Reply

timreizin

5 weeks ago, # ^ |

+16

Max prime gap up to 1e18 is around 1600, Using that bound the solution will be too slow (1600^2 * 60 * 1000).

→ Reply

hrishabh314

5 weeks ago, # ^ |

+11

Check out Prime Gap.

No proof, imo. Just a matter of fact that primes are pretty frequent in the range and we'll find one soon.

→ Reply

heWhoCooks

5 weeks ago, # ^ |

-8

You can check out this problem which uses the concept of prime gap Problem D , see its tutorial https://codeforces.net/blog/entry/20766. Even for n as high as 1e9, the difference b/w two primes is 282

→ Reply

Rising-coder

5 weeks ago, # |

← Rev. 2 →

+30

Fantastic stuff

Spoiler

→ Reply

Shoeib

5 weeks ago, # ^ |

+27

→ Reply

Red_Before_GTA6

5 weeks ago, # ^ |

Your handle perfectly explains the situation

→ Reply

moradiya84

5 weeks ago, # ^ |

Holy shit dude, i thought i had worst contest.

→ Reply

5 weeks ago, # |

im so confused about problem D, am i misunderstanding the statement? why isn't the answer simply ceil(l/g) and floor(r/g)? (assuming you solve the case of gcd(floor(r/g), ceil(l/g)) == ceil(l/g))

→ Reply

djm03178

5 weeks ago, # ^ |

Check this case:

1
6 10 1

The answer should be 7 10 instead of 6 9, because gcd(6,9)=3. Therefore, it's not sufficient to check only two cases where you only decrease $$$B$$$ at most once.

→ Reply

5 weeks ago, # ^ |

i c. thank you

→ Reply

hrishabh314

5 weeks ago, # ^ |

Looks like you are choosing A = ceil(l/g) * g & B = floor(r/g) * g. According to the statement, you'd want gcd(floor(r/g) * g, ceil(l/g) * g) == g. This will happen when gcd(floor(r/g), ceil(l/g)) == 1.

→ Reply

picoton

5 weeks ago, # |

+69

D is the worst garbage ive ever seen

→ Reply

Abhinaysai16

5 weeks ago, # |

Merry Christmas to everyone

→ Reply

Always_WA14

5 weeks ago, # |

i love mathforces

→ Reply

borekking

5 weeks ago, # |

← Rev. 7 →

Solution for B:

Every number is divisible by 1
A numbers is divisible by 3 iff the sum of its digits is divisible by 3. The sum of its digits is n! * d, which is divisible iff 3 divides n! or 3 divides d. So we get (n >= 3 or d % 3 == 0).
A number is divisible by 5 iff its last digit is 0 or 5. So we get (d == 5).
For 7 note that the number can we written as (10^{n!}-1) / 9) * d where the first factor is a whole number. Since 7 is a prime number at least one of the factors has to be divisible by 7. d is divisible by 7 iff (d == 7). (10^{n!}-1) / 9 is divisible by 7 iff 10^{n!}-1 is divisible by 7. Further 10^{n!} - 1 == 0 (mod 7) iff 10^{n!} == 1. And as usual 10^x mod 7 is periodid: 10^0 == 1, 10^1 == 3, 2, 6, 5, 1, 3, ... Hence 10^x == 1 mod 7 iff 6 divides x. So the second case is 6 divides n! which is n >= 3.
For 9 we can check the sum of digits again. The number is divisible by 9 if the sum of its digits is divisible by 9. Here we have to check for 3 cases: n! * d is divisible by 9 iff (9 divides n! iff n >= 6) or (9 divides d iff d == 9) or (3 divides n! and 3 divides d).

Submission

→ Reply

Spasitelj

5 weeks ago, # |

This is a rated contest right? I applied as "rated" or whatever, but how come I didn't get any rating, and it says it's unrated in my "Contests" page.

SOrry for the noob question.

→ Reply

https://codeforces.net/contest/2043/submission/298300293

5 weeks ago, # ^ |

the ratings are updated tomorrow

→ Reply

Spasitelj

5 weeks ago, # ^ |

Thanks

→ Reply

Folka

5 weeks ago, # |

Problem C is a bit harder to be Div.2 C also, in my opinion D is much easier than C (may be because I am a math lover XD ). However, Great contest as we used to from BledDest!

→ Reply

reshwanthind

5 weeks ago, # |

In Problem D

Can anyone explain the correctness of finding the co-primes within very less range i.e 10 iterations in this solution of mine .. sadly it got accepted after the contest :(

→ Reply

udta_kouwa

5 weeks ago, # |

for problem-D, is it not possible to fix L to be smallest divisor of G in range L to R. can we prove it, test-case-3 has this case.

→ Reply

ParasBedi298

5 weeks ago, # ^ |

Consider G=1, L=15, R=21.
Then fixing L=15 will give you a maximum gap of 4 (19-15). While the best possible gap is 5 (21-16).

→ Reply

fibbonugget

5 weeks ago, # |

Something seems wrong with the testing script for problem D, my code for problem D fails on test case 2. I checked the part where it fails. for some reason the outputs of the 20th case and 19th case are getting swapped in my submission but works fine on my system.

→ Reply

5 weeks ago, # ^ |

I think you should check your system.

→ Reply

fibbonugget

5 weeks ago, # ^ |

I checked it and I was at fault, lol.

→ Reply

lawwash._.

5 weeks ago, # |

Merry Christmas

→ Reply

ByteMeHarder

5 weeks ago, # |

Hey everyone so I faced a very weird issue today.

When I ran the following code using the c++ 17 compiler my code gave runtime error while the same code got accepted on c++ 20 compiler. LINK TO THE C++ 17 submission LINK TO THE C++ 20 submission

Any reason why it might have happened?

→ Reply

-firefly-

5 weeks ago, # ^ |

+24

As you may know, the c++17 compiler is 32-bit, and the c++20 compiler is 64-bit. In the 32-bit compiler, size_t is uint32_t and in the 64-bit compiler, size_t is uint64_t.

Therefore, when you attempt int i=a.size()-1 on Line 127 when a.size() is $$$0$$$ (consider sample case 4), although both versions encounter underflow, the outcomes differ. In the 32-bit version, the underflowed result is $$$2^{32}-1$$$, which is assigned to a long long (note the #define int long long in the front!), so $$$i$$$ becomes a huge positive integer and visiting a[i] clearly raises a runtime error. In the 64-bit version, however, the underflowed result is $$$2^{64}-1$$$, which is "correctly" assigned to a long long, which will overflow again to the correct -1.

→ Reply

srikanth15458

5 weeks ago, # |

-22

This was an awesome contest

→ Reply

5 weeks ago, # |

Didn't participate in this round partly because of: I strongly recommend BledDest to reconsider his view on Div2 and Div3 rounds. I've noticed that almost each time he is a problemsetter, you should expect round to be unnecessary tricky. He's done it even in some of the previous Global Rounds, making guys even with higher rating than his to argue about unnecessary difficulty. And don't put it like 'Oh, you didn't solve problem, cry about it'. We are here to learn and difficulties should be. But people should not get discourage each time you decide to write a problem. If you really want to show your problemsetting skills, then create problems that are hard enough to make people think and not that difficult for people to fail. Especially for Div2, where so many people participate, from Newbies to Masters.

I really suggest the community to create a rating system for problems and rounds. If you make problems, that do not meet the requirements of the round, then you are a bad problemsetter.

→ Reply

dummy_varr

5 weeks ago, # ^ |

who are you to decide whether problem is too difficult or not , and who are you to decide whether the problems met the requirements of the round or not . How can you even categorize someone as a bad problemsetter just because you could not solve the problems

→ Reply

5 weeks ago, # ^ |

You didn't get the point. It's not me the guy that "who is that guy to say these things?". It's me the guy that just summing up the overall reaction. Look at the comments first. It's much more easy to be kind-hearted guy and not being against anything and anyone than to reveal your honest opinion.

And if you really want to play this game, I am the guy who's seen a decent amount of negative comments to the BledDest's problems (and solved them too) previously and nowadays this is just a pattern. And I'm the guy who is going to participate in the next BledDest's rounds and hopes them to be interesting and solvable. And I don't comment badly about problems that seem to be difficult only for me. Here, I repeat, is a pattern.

And this is not only your first round, but also the first solved problems on CF. Problem A is already hacked. Man, just stay on top first, then arguing.

→ Reply

dummy_varr

5 weeks ago, # ^ |

-6

Bro you did not even give the contest . I know you want to go into politics but you can practice somewhere else . This is not the place

→ Reply

copyPasteCoder

5 weeks ago, # ^ |

I mostly learnt from BledDest contests

→ Reply

5 weeks ago, # ^ |

And thats a good point too. Thanks for sharing.

I understand it and want to say that while problems should teach you something, they also should be balanced. I do not consider facing that much difficulty at B and C really worth it. Nevertheless, we can learn from it.

Maybe I was too categorical in my previous comment about BledDest being a bad problemsetter, sorry for that. I just want the situation like this day to be as rare as possible. And by this situation I mean... look at the comments. People are discouraged.

→ Reply

5 weeks ago, # ^ |

← Rev. 3 →

+10

Which problems do you think were too hard today ? I agree D was not that great (especially since guessing helps a lot to solve it). Appart from this, ABC were perfect (and E was maybe even a bit too easy compared to usual div2 E).

Maybe you think that C should be easier since there have been recent rounds where #solves A = #solves C. However, it wasn't the case three years ago (and it shouldn't be the case). Ideally, you want a geometric solve count curve i.e every contestant can find a problem that is challenging for them. I think it was the case today.

If you're looking for rounds where you can solve more problems, then you can take div3 and div4.

It is impossible to have too many "easy" problems in every round which is why div3 and div4 exist!

→ Reply

5 weeks ago, # ^ |

Yeah, sounds nice and clean but look at the comments. It's not just my opinion. "Worst edu round ever" has 93 upvotes now and this number will only increase. You're sharing only your experience, but this round worked out only for small amount of people and you're among them. IMHO, while creating a Div2, problemsetter should keep in mind that most of Div2 participants are 1600- even if there are Div3 and Div4. It doesn't mean that all problems should be "easy" but not making even masters (look at Rising-coder) stuck on the second (gosh!) problem.

→ Reply

Rising-coder

5 weeks ago, # ^ |

+19

I would say it's a skill issue. I literally ranked 10000. It is me not the problems.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

+23

Unhappy people complain but the happy ones usually do not comment (which is why I force myself to comment, in order to also share positive thoughts to the authors).

In my opinion, in div2, slow ABC ~= 1500 — 1600 perf. That seems to be the case today. Note that there are > 3k people that solved ABC, I think this proves the problems were perfectly fine: there is roughly a factor 3 between C solvers and A solvers.

Finally, people all have bad days. I myself have had bad contests (going from +150 to -150). This doesn't mean the problem setters did a bad job.

→ Reply

5 weeks ago, # ^ |

Well, if you're not a lawyer already, you should consider to be one.

→ Reply

theSkeleton

5 weeks ago, # |

I feel like problems E and D should have been swapped,E is way easier than D.

→ Reply

Nsqk

5 weeks ago, # |

For low rated people like myself, I feel like this round B and D was a big guessforces. C is nice though.

→ Reply

arihant_j

5 weeks ago, # ^ |

How is b guessing?it's maths

→ Reply

Nsqk

5 weeks ago, # ^ |

I think the same argument can be made for most problems about not being a guessing problem. But I don’t believe the majority of the people that solved B know the proof of to why that happens.

→ Reply

KarrQwq239

5 weeks ago, # |

I think ABC is the normal. I don`t no why people hate B, this is not hard mathematical problem. D is very random. AC for proof for me and i think for many peoples. Round is the normal, but i was very stupid on D (+5).

→ Reply

IceSerpent

5 weeks ago, # |

← Rev. 2 →

I want to bring to attention a major class of testcases missed by the pretests of Problem C. I unfortunately missed a case when fixing my solution and didn't think much of it when it ACed. However I realized after the contest that it would fail.

Just a subset of this major class are the test cases with 1s and -1s such that all prefix sums are non-negative are not in the pretests, which is a major class of tests, with a few examples included below

2

1 -1

and

3

1 1 -1

I am unsure as to why these were not tested. When looking at test case 2, it seems that the test case -5 -1 was tested repeatedly instead of going through the small cases, which I thought was the norm. Unfortunately, it cost me and other contestants on this contest ):

→ Reply

FzArK

5 weeks ago, # |

+33

So basically, (B, A) + (an imposter $$$x$$$ sneaking in among the $$$1$$$s, with a sprinkle of $$$G$$$ on top) = (C, D).

→ Reply

marcobonato

5 weeks ago, # |

Hello all, how did you approach problem C? I'm looking at some other people's solutions, and I don't understand their approach. I did manage to come up with my own solution though, 298342429. My idea was to combine:

All possible subarray sums before the value not equal to -1 or 1
All possible subarray sums containing the value not equal to -1 or 1
All possible subarray sums after the value not equal to -1 or 1

My main observation is that it's really easy to do it this way since you only need to consider adding or removing ±1, and then I threw a bunch of sets at the problem.

→ Reply

Tamas

5 weeks ago, # ^ |

Find maximum and minimum subarray sum before x. Do the same after x. Now insert values with thin this range into a set. Now find maximum and minimum subarray sum for subarrays starting from x and going say towards left. Now do the same for postion right to x. Add the minimum of these two sets and maximum of these two sets. Insert all the values between this range of min and Max value into the earlier set. Can it the set values

→ Reply

Lakshay_2021059

5 weeks ago, # |

Can someone please hack this

→ Reply

cdx123456

5 weeks ago, # |

In question E, I came up with a greedy approach of changing from column 1 to column m if necessary, which is clearly incorrect. I repeated this operation 30 times and randomly selected the order of attempts in column m, and it passed... (However, during the competition, I only performed it 15 times and eventually switched to a deterministic approach) Code

→ Reply

Nguyendinhbach

5 weeks ago, # |

← Rev. 2 →

Does anyone has the proof for D.

→ Reply

rubbish

5 weeks ago, # ^ |

Honestly,the pure mathematical proof,i think most of the cp contestant cannot figure out,sometimes we just need to know the theorem state and which mathematician say that is enough,the prime number theorem state that for a given integer N,the prime number less equal than N is approximate n/log(n),in other word from 1 to N,there is around N/N/log(N) which is around log(N),this mean for avg 2 consecutive prime number distance is around log(n),so how about it related to our problem?The key is if gcd(A,B)=G,this mean A=k1G and B=k2G,and gcd(k1,k2)=1 because if gcd(k1,k2)>1 then gcd(A,B)>G which is not satisfy problem statement,so we know that l<=A<=B<=r -> l<=k1G<=k2G<=r ->ceil(l/G)<=k1<=k2<=floor(r/G) so our target is finding two number k1 and k2 which gcd is 1 in ths interval,and the fact is two prime number are coprime which is gcd(pi,pj)=1 (pi and pj are prime number),but is that only prime number gcd is 1?Obviously not for example gcd(8,27)=1 but they are not prime number,so according to previous result,if we start from lower bound (ceil(l/G) and upper bound(floor(r/G) to search the first and the last prime number the worst time complexity is O(logN) but if we find two number which gcd is 1 before found the prime number then the complexity will lower than O(logN) so overall for 1 testcase the worst complexity is O(logN)

→ Reply

Nguyendinhbach

5 weeks ago, # ^ |

← Rev. 2 →

Okay but why does searching first 50 mutiples of G and last 50 multiples of G in bound(l,r) works?

→ Reply

rubbish

5 weeks ago, # ^ |

Actually it depend on the coder experience about solving this kind of problem,as i mention before there is around log(n) gap for n=1e18,log(n) around 18 but this is a avg so to prevent WA for some extreme case,most of the person will make larger value like 50,100 even 500 for me.

→ Reply

mathworker21

5 weeks ago, # ^ |

rubbish comments from rubbish. he asked for a proof, not for pointless ramblings.

→ Reply

Tamas

5 weeks ago, # ^ |

298416491 The solution is more of intuitive/common sense then actual proof. The solution just happens to work within given range. My intuition would say have a look at prime gap, it increases by leaps and bounds as we move further on the number line.

→ Reply

5 weeks ago, # |

Can someone give me a couple of hints for C

→ Reply

adel54321

5 weeks ago, # ^ |

Hint 1: what would be the solution if abs(x)=1 for every x in the array?

Hint 2: now suppose that there is exactly one x in the array such that abs(x)!=1. X can split the array into 2 arrays (possibly one of them is empty). You can apply the solution found in Hint 1 to each array of them. This will include in the solution the sums of all subarrays not containing x.

Hint 3: Once you got the sums of all subarrays not containing x, you still need to get the sums of sub arrays containing x and add them to the solution.

Hint 4: Each subarray containing x is composed of a subarray starting from x, and a subarray ending at x. The sum of the subarray is the sum of the sums of both subarrays.

I hope these hints are useful. I tried not to be super clear to avoid giving you the solution directly. If you need more explanation let me know

→ Reply

5 weeks ago, # ^ |

thanks bro

→ Reply

5 weeks ago, # ^ |

For 1 I noticed that it's not optimal to mix 1 and -1s. Adding a -1 is the same thing as not including a 1, so the answer would already have been computed. Therefore, we can compute the sums with a two-pointer technique in O(n).

Now when including a different number I can apply the same technique in the two subarrays you mentioned and add the merge of some subarrays to the answer too (that way we're including the subarrays with the different element). Each half has O(n) sums, so excuse me as I think how to merge these subarrays in an efficient manner...

→ Reply

adel54321

5 weeks ago, # ^ |

I don't think that it is not optimal to mix up 1 and -1

Consider this example:

1 1 1 -1 1 1 1 1 1 1

If you don't mix -1 and 1, the max sum you can get is 6. But this is not correct because we can get a sum of 8 by adding up all the items.

→ Reply

adel54321

5 weeks ago, # ^ |

I can give an extra hint to help with this:

Let's take an array containing only -1 and 1

1 -1 1 1 1 -1 -1 1

Let's pick an arbitrary subarray (for example):

1 1 1 [1 1 -1] -1 1

The current sum in this subarray is 1+1-1 = 1 Now what happens if we try to expand the subarray from the left?

1 1 [1 1 1 -1] -1 1 => adds 1 to the sum (sum becomes = 2)

1 [1 1 1 1 -1] -1 1 => adds 2 to the sum (sum becomes = 3)

[1 1 1 1 1 -1] -1 1 => adds 3 to the sum (sum becomes = 4)

What do you notice? If we can get the sum from 1 to 4, we necessarily have subarrays that give a sum of 2 and 3 (any integer between 1 and 4).

This is correct because as we expand the subarray from any side, we will either add 1 or subtract 1. Thus, if, starting from sum = x, we can achieve sum y by expanding the subarray from either sides, we will get all integers between x and y as sums along the way (here I am supposing y>x, but it also applies if y < x for sure).

So to sum up...

If we know that we can get a subarray with sum X, and a subarray with sum Y, then we are guaranteed to have subarrays with sum X, X+1, X+2, ..., Y

Thus... if the array is only composed of 1's and -1's, the different sums that we can get can be obtained by determining the smallest subarray sum, and the largest subarray sum. The result will be the set of every integer between the smallest subarray sum and the largest subarray sum (inclusively).

Finding the largest/smallest subarray sum is a classic dp problem that can be solved in O(N)

→ Reply

https://codeforces.net/contest/2043/submission/298352521

5 weeks ago, # ^ |

yeah turns out I was wrong asf. thank you so much though. been fighting demons to consistently solve div2 C

→ Reply

tamthegod

5 weeks ago, # |

← Rev. 2 →

How can my solution for D be hacked? The complexity is $$$O(T*50^2*60)$$$. 298249717

→ Reply

Fakewave

5 weeks ago, # ^ |

+11

it seems that p = a + i*x can exceed long long, maybe that's the problem

→ Reply

tamthegod

5 weeks ago, # ^ |

← Rev. 2 →

-8

Yeah that is a case. However my solution was hacked due to TLE, and integer overflow doesnt affect.

→ Reply

Fakewave

5 weeks ago, # ^ |

← Rev. 2 →

but then it's not clear what's happening with gcd, so it may well be TLE

→ Reply

2020TAndr

5 weeks ago, # ^ |

(checked via custom test tab) Your solution uses ~240ms on $$$T = 120$$$, which scales to well above TLE. I believe that happens because $$$O(T * 50^2 * 60)$$$ stands for $$$1.5 \cdot 10^8$$$ non-cheap loop iterations, each taking GCD.
To be precise, signed integer overflow may do anything (per definition of "undefined behavior"); should compiler detect it, it may assume that corresponding code is unreachable and e.g. remove loop checks. See https://godbolt.org/z/Y6bTP3MK3 for reference:

#include <iostream>
int main() {
    char buf[50] = "y";
    for (int j = 0; j < 9; ++j) {
        std::cout << (j * 0x20000001) << std::endl;
        if (buf[0] == 'x') break;
    }
}

→ Reply

Serioton_codes

5 weeks ago, # |

Hey someone please take a look at my submission and tell me the mistake, I am using max and min subarray sum ending at a index to find the answer.

→ Reply

Ser1kbay

5 weeks ago, # |

Worst contest i ever seen__

→ Reply

PsychoPinkQ

5 weeks ago, # |

+11

I really like C, F. However, I think D is unimaginably bad, especially in a round that participants can hack each other. I also don't like B either, but I think it's still an okay problem.

I want to know how to hack D. I'm very curious. It seems like all the hack was done with making TLE which surprises me a lot, I thought its easy to make a WA.

→ Reply

rakim_

5 weeks ago, # ^ |

How to do C?
I was able to figure out that values in the left subarray of the non 1/-1 and values in right subarray but I'm unable to find a way to get the sum of subarray including our non -1/1 element
I tried reading AC code but doesn't make sense ;-;

→ Reply

PsychoPinkQ

5 weeks ago, # ^ |

← Rev. 5 →

You already know how to do with arrays containing only -1/1, so our goal is to find the maximum subarray sum and the minimum subarray sum that includes the special element in the subarray. Let's assume that $$$id$$$ be the position of the special element and $$$s$$$ be the prefix-sum array of $$$a$$$.

We can record $$$A=\displaystyle \max_{0\leq j<id} s_j$$$ and $$$B=\displaystyle \min_{0\leq j<id} s_j$$$. Then calculate $$$\displaystyle \max_{id\leq j\leq n} s_j - B$$$ and $$$\displaystyle \min_{id\leq j\leq n} s_j - A$$$. That's just what we want.

This works cause for all $$$j\in[0,id), k\in[id,n]$$$, $$$s_k-s_j$$$ is equal to $$$\displaystyle\sum_{i=j+1}^{k} a_i$$$. $$$a_{id}$$$ is in the summation obviously.

→ Reply

rakim_

5 weeks ago, # ^ |

Yep it makes sense, Thank you so much (and Merry Christmas!)

→ Reply

lequoctran181

5 weeks ago, # ^ |

Same as I thought. I remembered a theorem which stated that "from 1 to 1e18, the maximum distance between the two primes are at most 300", so I think that finding the left and right bounder after two loops of 300 will pass. But that gave me TLE, so I have to change to 100. Luckily it passed but I thought that it was easy to hack with WA verdict. P/s: sorry for my poor English. But I remembered the theory is called "Rabin-Miller theory"?

→ Reply

PsychoPinkQ

5 weeks ago, # ^ |

But according to wikipedia, 2,300,942,549 and 2,300,942,869 are both prime, so I think "from 1 to 1e18, the maximum distance between the two primes are at most 300" might be wrong?

→ Reply

5 weeks ago, # ^ |

Yeah not 300, but the max gap between two consecutive primes is atmost 1600 till 1e18. consecutive is the thing here. But even after reading that fact from wiki, I am yet to discover the usage of this fact in the solution.

→ Reply

Altruistic_doom

5 weeks ago, # |

← Rev. 3 →

A submission for Problems about GCD , having difficulty understanding why it is giving WA,expected TLE 298363085

→ Reply

parag776

5 weeks ago, # |

how to solve G

→ Reply

5 weeks ago, # |

← Rev. 2 →

why my code — 298375202 gave TLE but similar code - this one didn't can you please tell me the reason i am very confused. Thanks in advance.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

you need to end the for loop if second — x <= mxdis or y — x <= mxdis. Plus, 4 variables(first, second, x, y) should use long long. This don't affect TLE, but you will get WA. check this.

→ Reply

rubbish

5 weeks ago, # ^ |

Your code

for (int x = first; x <= min(second, x + 100); x++) {
            for (int y = second; y >= max(x, first); y--) {
                if (gcd(x, y) == 1) {
                    if (mxdis < (y - x)) {
                        mxdis = y - x;
                        a = x, b = y;
                    }
                    break;
                }
            }
        }

In your code first=(l+g-1)/g which is ceil(l/g) and second=(r/g) which is floor(r/g) but under the constraint l and r up to 1e18 and min g is 1,in other word second to first can up to 1e18,so if you run through a loop about 1e18 definitely will be TLE,the other code is is checking around 100 number only,summary is the other code check for the number around 100 times but your code check 1e18 times which is 1e16 times than other code so it will TLE

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Mine code is also checking 100 numbers only check it see this 298375202. why its not working

→ Reply

5 weeks ago, # ^ |

Your code have a small mistake. Since x <= x + 100, x <= min(second, x + 100) equals with x <= second. So you gets TLE. you need to change this to x <= min(second, first + 100)

→ Reply

5 weeks ago, # ^ |

Silly me.. thanks ☺️.

→ Reply

vishaaaal

5 weeks ago, # |

-13

This is for the authors

→ Reply

New_and_simple

5 weeks ago, # |

I'm a newbie, would appreciate if you don't go too hard on me. Coding is not mt strong suit, I'm working on it

Could someone give me an approach to solve D, i tried it many times, then I realized my logic was wrong. I used the bounds for multiples of g: lower limit as a =  ceil(l/g) and upper limit as b = floor(r/g). 

Then I thought of the following logic, if A = a, then if gcd(a,b) == 1 then B = b else if gcd(a,b-1) != 1 then B = b - 1. Except it does not work because supposing p and q as primes, if a = pq, b - 1 = mp and b = nq, there are infinitely many pairs of m and n which satisfy (mp - nq) = 1, since it's the definition of two coprime numbers, p and q are always coprime. Then i thought of adding a max range for the lower limit, same for the upper limit, but I don't know how much to add, I understand that the range must be small, I don't know how to find how small it will be.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Do a Binary Search on your code:

WA -> range too small

TLE -> range too big

→ Reply

New_and_simple

5 weeks ago, # ^ |

Thanks a lot. I genuinely appreciate it.

→ Reply

2020TAndr

5 weeks ago, # ^ |

Until those ranges overlap (with no point which would AC), in which case you need to search for other solutions :)

→ Reply

cpdelta

5 weeks ago, # |

Never seen earlier a contest's blog with downvotes.

→ Reply

Xiao_2710

5 weeks ago, # |

My worst performance in a div2 edu till date. Problem C was very nice, learnt a lot while solving it. I think problem B was un-necesssary, imo a div2 B should'nt be math heavy to the point that most solves are proof by AC.

→ Reply

5 weeks ago, # ^ |

I don't think so b was tough at all. It was just basic number theory.

→ Reply

Xiao_2710

5 weeks ago, # ^ |

It was indeed, i am just bad at math.

→ Reply

5 weeks ago, # ^ |

Now worries just buy a number theory book and finish it you will be good to do.

→ Reply

Typed_SIGTERM

5 weeks ago, # ^ |

import math

odd = int(input())
for n in range(1, 8 + 1): # factorial(8)=40320, if not found until 8, then forget it
    times = math.factorial(n)
    for d in range(1, 9 + 1): # Check every possible number
        if int(str(d) * times) % odd != 0:
            break
    else:
        print(n) # If n is greater than or equal to this value, it must be divisible by odd
        break
else:
    print(None)

→ Reply

5 weeks ago, # |

-8

why A test are so weak ?

I mean how on earth the authors let someone got hacked on A because of precision issues ?

for real that's a bullshit

→ Reply

AttractorsTheory

5 weeks ago, # |

-8

hmm, so it seems like every straight copy past problems from an on going contest are low quality rounds

→ Reply

mnnit.prakharg

5 weeks ago, # |

Why ratings are not updating?

→ Reply

5 weeks ago, # ^ |

system testing hasn't started yet

→ Reply

tushu06

5 weeks ago, # ^ |

I have seen system testing 100% :)) when the contest ended . so another one coming up ?

→ Reply

5 weeks ago, # ^ |

Oh maybe I could have missed system testing... thanks for telling

→ Reply

_Kee

5 weeks ago, # ^ |

The system testing will happen after the open hacking phase, where all submissions are tested with test cases used for hacks. I don't think it has started yet.

→ Reply

CodeKira

5 weeks ago, # ^ |

Is the start of system tests and others manually controlled, or automated any idea?

→ Reply

tushu06

5 weeks ago, # |

when rating will be updated ?

→ Reply

ochpochmak141

5 weeks ago, # |

where is my rating bruh

→ Reply

5 weeks ago, # ^ |

→ Reply

masonpop

5 weeks ago, # |

-11

F is totally shit. the O(nv^2) sol is naive and should't appear at this pos actually. if u see the rankings u can find a lot of sols using very complicated algorithms (and some get TLE).

if u swap D and F I bet there will be much more solves.

(P.S Me myself wrote a sol using DP and FWT in contest, which is O(nV*log^3V). although it passed i'm so sad.)

→ Reply

meisgood

5 weeks ago, # ^ |

bro it’s your problem if you can’t notice it. calculating time complexity is also a part of competitive programming.

→ Reply

masonpop

5 weeks ago, # ^ |

I mean that put such a naive problem at F is not proper. Maybe it's suitable for C or D i think, putting here will only make ppl confused and solve it with methods too complicated.

→ Reply

masonpop

5 weeks ago, # ^ |

u can look at the standings, almost half of all participants solved it in a way too complicated way, just have a look at their codes.

→ Reply

heWhoCooks

5 weeks ago, # |

+20

Editorial please

→ Reply

Hyf20100507

5 weeks ago, # |

+12

Please do the system test faster! I have waited for a day.

→ Reply

5 weeks ago, # ^ |

I am happy for you and everyone expecting a +ve delta. Being someone who is (a big) maybe getting de-rank, it's getting more intense as the time passes. Please update the ratings...

→ Reply

Hyf20100507

5 weeks ago, # ^ |

Well, the system test is now starting.

→ Reply

5 weeks ago, # ^ |

The contest must be nicknamed "duality". I am not sure if I should be happy or not :)

→ Reply

Darkhood148

5 weeks ago, # |

← Rev. 2 →

Bro how my solution to A failed (cries): 298206354

→ Reply

Spasitelj

5 weeks ago, # ^ |

← Rev. 2 →

That's because you are only flooring the final result, but in the problem statement, there are these flooring brackets ⌊x/4⌋. One way you can do this is to simulate the divisions, and floor on each iteration.

Maybe something like this:

n = int(input())
c = 1
while(n>3):
        n = int(n/4)
        c*=2
print(c)

→ Reply