Codeforces Round #948 (Div. 2)

3 weeks ago, # |

Since the last 5 contest I'm stuck at 1100's hoping to cross 1200 this time. Best of luck everyone :)

→ Reply

3 weeks ago, # ^ |

+15

Finally reached pupil

→ Reply

kichuParina_

3 weeks ago, # |

The score of problem B is 1250!hoping to get positive delta :)

→ Reply

HarmlessJett

3 weeks ago, # |

As a participant, I hope I solve 2nd problem quickly :(

→ Reply

RD_TheCoder

3 weeks ago, # |

+13

meme

→ Reply

ayushanshul07

3 weeks ago, # |

-6

I sooo want to appear for this round, but same time IPL finals.

→ Reply

Rakesh_898

3 weeks ago, # ^ |

Cf>RCB>Finals

→ Reply

3 weeks ago, # |

C looks buff

→ Reply

34z12000

3 weeks ago, # ^ |

It's probably interactive

→ Reply

https://en.wikipedia.org/wiki/Nikita_(given_name)

3 weeks ago, # ^ |

Yea I think so too.

→ Reply

despair_101

3 weeks ago, # |

I think it's time to repeat all Stefan tricks... https://codeforces.com/blog/entry/117352

→ Reply

Kai_007

3 weeks ago, # |

I rarely get any positive delta in Div 2. Hope this time is my time. :)

→ Reply

thatchemguy

3 weeks ago, # |

Hoping for a positive delta

→ Reply

thatchemguy

3 weeks ago, # |

cf>>>ipl

→ Reply

EHMridul

3 weeks ago, # |

Hoping to solve first two problems in short time and get some fun.

→ Reply

Saumy_1

3 weeks ago, # |

Hoping for Becoming cyan participant :)

→ Reply

asr_003

3 weeks ago, # |

1750 for C... interesting.

→ Reply

deified

3 weeks ago, # |

← Rev. 2 →

-6

My confidence booster to achieve high positive delta

Alohomora

→ Reply

mohdayat

3 weeks ago, # |

500A to direct 1250B that is some score gaps i am seeing.

→ Reply

BiggestOtaku

3 weeks ago, # |

Scoring is wild on this one

→ Reply

Patel45

3 weeks ago, # |

Kontest > IPL hehe...

→ Reply

vignatej

3 weeks ago, # |

now, nikita is a boy!!!! its a girlllll

→ Reply

hashman

3 weeks ago, # ^ |

→ Reply

amoad

3 weeks ago, # |

-58

Low quality problems especially C

→ Reply

Arvi_saleque

3 weeks ago, # |

-32

Ai can solve problem B like chatGPT 4. there are lots of people who use GPT4 to solve problem B. you can find many newbies who solved problem B but could not solve problem A. Xd I think the round should be unrated. and setters ensure that any problem can't be solved by any AI.

→ Reply

ritesh160193

3 weeks ago, # ^ |

-24

Exactly. Also a few youtube channels show the answers to the problems before the contest ends. It is unfair for those trying genuinely. I am not sure if there is any way to catch those who copied and those who tried on their own. Otherwise ratings of this contest will be false representation of ones capability.

→ Reply

slabi

3 weeks ago, # ^ |

-17

I want the round to be unrated to dodge this -40 delta I'm about to get :(((

→ Reply

3 weeks ago, # ^ |

← Rev. 2 →

It's already hard to check for AI solutions and also it's very hard to come up with div2A which will be unsolvable by LLMs.

I think it's not feasible even now but in 6-12 months LLMs will be able to solve most existing div2A and div2B and some div2C so it will be almost completely impossible to prepare AI-resistant div2 contests.

→ Reply

ritesh160193

3 weeks ago, # ^ |

So are we near to the end of CP(atleast for those solving Div2 A,B & C)? Because most of the participants on codeforces are able to solve only Div2 ABC. If these problems are taken by AI then we will see only purple and above competing.

→ Reply

3 weeks ago, # ^ |

This is not the end of CP but will create some issues. Cheating is already a problem but it will be way more widespread soon.

You can just ignore cheaters, e.g. compete with your friends or try to solve as much problems as possible. Or maybe at some day there will be alternative rating system which will be based on difficulty of tasks but not in comparison with other participants.

Also, look at chess, they have much worse problem with cheating, it is not only more direct PvP game (so experience suffers from cheating more), chess AI on smartphones is way stronger than humans so the problem persists even at elite level.

Nevertheless, chess is alive and well even though there is a sometimes heated discussion about cheaters and anti-cheating measures.

→ Reply

absolute-mess

3 weeks ago, # ^ |

← Rev. 2 →

AI compiles all the data from its dataset and gives you an answer. You may solve Div2A or Div2B (rarely) as it does not contain new things or logic. You can find that AI can solve many standard problems of various DSA topics, which are pretty tough and challenging to understand.

So, for AI to solve problems, the person using AI must know how to solve the problem and what prompt is required to give to the AI model for it to create the solution. AI can help reduce your labour work but cannot think on your behalf. So, instead of crying about it, learn different topics and upskill yourself. Also, Idk if it's valid for you, but if you were unable to solve a problem, then it's your fault or lack of knowledge/skill. You also have the access to GPTs, you could have also solved the problem using the similar way.

Just because you couldn't solve doesn't means that the round should be unrated

→ Reply

DarkDuel

3 weeks ago, # ^ |

Well may be ,if the language of problems is twisted

→ Reply

Curious69

3 weeks ago, # ^ |

← Rev. 2 →

+50

I wasn't able to perform as well as others == The round needs to be unrated

→ Reply

Pew_Pew.

3 weeks ago, # |

+17

What a terrible problem distribution, I was performing at ~2000 rating despite having solved only 2 problems, and this was till last 30 mins of the contest.

→ Reply

NULLgorithm

3 weeks ago, # |

Speedforces

→ Reply

towrist

3 weeks ago, # |

+26

cant believe beat jiangly to problem E lmfao

→ Reply

MKasirloo

3 weeks ago, # |

← Rev. 4 →

-23

→ Reply

interpolation

3 weeks ago, # ^ |

+10

$$$32$$$ is the number of bits, how you want to solve it?

→ Reply

Reterko

3 weeks ago, # ^ |

Because you need to be smart enough to not use brute force, which took me some time to realise

→ Reply

interpolation

3 weeks ago, # |

+26

I solved D using hashing. For each column there are $$$\leq n + 1$$$ ways to get only one $$$1$$$. And these "ways" are almost identical. (We should either remove all $$$1$$$ and recolor one $$$0$$$, or remove all $$$1$$$ except one)

→ Reply

tickbird

3 weeks ago, # |

is problem C using dp?

I tried tokenize each element by counting prime factor then greedy n^2 but didn't worked.

→ Reply

3 weeks ago, # ^ |

← Rev. 4 →

Yes it's kind of dp, the main idea is that there are 2 options:

LCM of whole subset is larger than max(a) -> then answer is n
LCM of whole subset is <= max(a) <= 1e9 and then there are not that many possible LCMs, I don't have a proof but intuitively if you have a lot of different prime factors, then LCM quickly grows to be large and also that if you add a new number to a subset LCM either stays the same (does not increase amount of LCMs) or multiplies (so grows very fast).

So the solution is: check for option 1, if it's not the case just keep dp = map<LCM, max_subset_size> and add elements one by one (iterate over all previously calculated LCMs) and update dp

→ Reply

bigSchrodinger

3 weeks ago, # ^ |

← Rev. 2 →

+18

For the 2nd point, every possible LCM that can be formed from the subsequences will be a divisor of the maximum. So there are at most ~1000 divisors.

→ Reply

3 weeks ago, # ^ |

Oh right, it's very simple, thanks!

→ Reply

YatinUtreja

3 weeks ago, # ^ |

← Rev. 2 →

I used the same approach but got tle. Any particular reason you can think of?

Edit: Got the correct answer was getting integer overflow. while checking intitial condition :(

→ Reply

3 weeks ago, # ^ |

I had overflow as well initially, thankfully pretests cached it in my case

→ Reply

avighnakc

3 weeks ago, # ^ |

← Rev. 2 →

Hey, I tried coding this out but got WA on test 8. Could you please tell me where I'm going wrong?

Edit: I found my mistake. I did not account for the fact that sometimes the LCM could be so big that it overflows. I simply added a check to see if the LCM ever got bigger than $$$10^9$$$, and it ACed. Thanks!

→ Reply

Ran_Mouri

3 weeks ago, # |

can you give me hint for B please

→ Reply

3 weeks ago, # ^ |

Balanced Ternary

→ Reply

Reterko

3 weeks ago, # ^ |

+25

x + 2x = 4x — x

→ Reply

yariss

3 weeks ago, # ^ |

$$$2^0+2^1+...+2^{n-1}=2^n - 1$$$

→ Reply

peti1234

3 weeks ago, # |

+33

E is very similar to this problem: https://oj.uz/problem/view/IOI23_longesttrip

→ Reply

libobil

3 weeks ago, # ^ |

And yet knowing the solution of longest trip doesn't help you much

→ Reply

rliu4936

3 weeks ago, # |

is C brute force try all subsets of factors of the largest element to see which subset will give the largest count

→ Reply

asdasdqwer

3 weeks ago, # ^ |

← Rev. 2 →

Basically, yes. You first calculate the LCM of all the numbers. If that number is greater than $$$10^9$$$ then the LCM cannot be inside of the array, so you just take all the numbers. Otherwise, you iterate over every divisor of the LCM (works in $$$\sqrt{LCM}$$$ time), check for each number in the array if it's divisible, and then return the maximum result. Here is my submission: Submission

→ Reply

zhangwenniu

3 weeks ago, # ^ |

good idea, thanks for sharing.

→ Reply

3 weeks ago, # ^ |

I think if the $$$LCM(array)$$$ $$$>=$$$ $$$max(array)$$$ is more appropriate than checking $$$>=$$$ $$$10^9$$$

→ Reply

aryamsingh7676

3 weeks ago, # ^ |

← Rev. 2 →

can you tell me what you are doing in this line? Thanks

if (tl != x)continue;

→ Reply

asdasdqwer

3 weeks ago, # ^ |

Let $$$x$$$ be the considered divisor of the LCM, and $$$S$$$ be the set of all numbers in the input such that $$$x$$$ is divisible by that number. The variable tl represents the LCM of the set $$$S$$$.

For a subsequence to be valid, the LCM of that subsequence is not allowed to be in the input. Now, if the LCM and $$$x$$$ are not equal, there might be a chance that the LCM already is inside the input, so we just skip it. If the set $$$S$$$ was a valid subsequence however, then it would pass this constraint when the considered divisor $$$x$$$ is different, namely the same as the LCM of $$$S$$$.

→ Reply

Astroflexx

3 weeks ago, # |

-25

Yeah, this contest, its uh...., NOT GOOD.

→ Reply

gvelesa

3 weeks ago, # |

Optimal approach for C?

→ Reply

3 weeks ago, # ^ |

Find LCM of list. If LCM > max element: answer is n.

Otherwise iterate through all factors of LCM.

If factor not in list. Keep track of cnt of items divisible by factor and LCM of said items.

Answer max(cnt of items for all factors not in list and where LCM(items) = factor).

→ Reply

accord

3 weeks ago, # ^ |

If LCM of array =/= largest value in array, answer is N
Iteratively calculate LCM of array. If at any point exceeds 10^9, we know the above case is automatically satisfied.

Now, where LCM = largest value in array = L.

The LCM of the elements for our answer can be only factors of L. So, find all factors of L.

For each factor of L that does not appear in the original array, count how many maximum elements divide it. Ensure that LCM of these elements = this factor. If this is satisfied, find maximum across all count values.

complexity: O(N sqrt(max(A_i)))

→ Reply

ay012

3 weeks ago, # ^ |

Shouldnt there be a log(a_i) factor too ? in time complexity

→ Reply

accord

3 weeks ago, # ^ |

← Rev. 2 →

If you assume computing lcm over a list to take O(n log(a_i)), then yes. However, practically you can assume O(n). See https://codeforces.com/blog/entry/63771.

→ Reply

ay012

2 weeks ago, # ^ |

oh wow thats nice thanks

→ Reply

Itachi_Uchiha13

3 weeks ago, # |

+13

How to solve D, I was trying to solve it in O(n*m*min(n, m)), was getting TLE on pretest 19 :(

→ Reply

3 weeks ago, # ^ |

i had a hashing soln but i couldn't submit due to small bug.
my idea is for each column compute all possible operation which can be made on i'th column  such that i'th column becomes special
there will be n such operation possible ops
pick the operation which occurs most of the times

→ Reply

3 weeks ago, # ^ |

upd : i got AC

→ Reply

granadierfc

3 weeks ago, # ^ |

Even I'm wondering how to D. I had some partial ideas , first of all take a particular column j , and make all it's elements zero , by choosing appropriate rows and inverting them. Then we can choose an i such that we will again apply inversion at the row i making this column good with 1 at row i. Now all the other columns , which had a 1 at i_th row and one more 1 at some other row will become good , but the main challenge seems to me is how to find them efficiently?

→ Reply

3 weeks ago, # ^ |

let mask = j'th column which wan to make specail
if you want i'th position to be 1 and all other positions 0, operation required is
ops = mask ^ (1 << i)
now you can use hashing to store all these ops and pick the most frequent ops

→ Reply

martins

3 weeks ago, # ^ |

+13

I saw your code and you have the right idea for small $$$m$$$.

For small $$$n$$$ you can just iterate over all the $$$n$$$-sized bitsets that make each column have exactly one 1, group them in a map, and return the bitset that maxes the result.

Code: 262803308

→ Reply

Itachi_Uchiha13

3 weeks ago, # ^ |

← Rev. 4 →

Wow great!! Got it, that’s an amazing solution. I think if we use hashing along with your method, that would pass for any n and m. Thanks!

Upd: I tried Hashing 262808152, getting wrong answer on test 4. Cannot really figure out why, I tried to debug it and there is a collision, 2 different bitsets are giving the same hash. I’ll try to figure out why. Also I tried submitting with multiple different values of mod and p but still the same result :(

→ Reply

MoLotfi

3 weeks ago, # ^ |

← Rev. 2 →

+13

I was having the same issue, and I fixed it by having two keys with two different primes (I am using polynomial hashing).

It is definitely not an elegant solution, and I see the other guys doing something with rand that probably provides a better solution (but I honestly do not understand it).

→ Reply

Itachi_Uchiha13

3 weeks ago, # ^ |

Damn, I never expected it was actually due to collision, because I tried so many values different values of mod. I thought there was some flaw with the algorithm to hash 2 vectors the same. I'll try double hashing then. Thanks!

→ Reply

akkafakka

3 weeks ago, # ^ |

You can overcome this by again calculating the max value using the hash you found (changing the columns accordingly) . This gives correct answer (I implemented this) but cannot say why this works.

→ Reply

Md_Minhaj

3 weeks ago, # |

how to approach B?

→ Reply

egor.okhterov

3 weeks ago, # ^ |

← Rev. 2 →

First convert x into binary form 10110100111.
After that fix all positions where you have 11.

→ Reply

lipet2k

3 weeks ago, # ^ |

I'm not sure if it works, but I had two cases:

We can see that if we have two consecutive digits that are 1's in binary we can increment i-1 and set i+1 to -1. For example if we have 3 in binary (11) this is also: 1*4 + -1*2 + 1*1.
If i is -1 and i+1 is 1 then we can set i to 0 and i+1 to -1. For example, 3 = 1*4 + -1*2 + 1*1 = 1*4 + 0*2 + -1*1.

→ Reply

I_lOVE_ROMAN

3 weeks ago, # ^ |

What about the number which has 29 1's like 2^30-1

→ Reply

3 weeks ago, # ^ |

-1 followed by 28 0s then 1

→ Reply

OMgL

3 weeks ago, # ^ |

if x is odd we can turn x divisible by 4 by either adding 1 or subtracting 1, and if x is divisible by 4 the next element can be 0 meaning there can always be 0 between 2 non zero elements

→ Reply

3 weeks ago, # |

← Rev. 4 →

i need 5 more minutes for D i am too noob at implementation. i had a small bug in code :(
upd : it's a correct AC soln

sad

→ Reply

3 weeks ago, # |

Even though I was only was able to solve 2 questions, I must say the questions were really interesting

→ Reply

Yes_itSMe

3 weeks ago, # |

← Rev. 2 →

Please someone explain Question : D Thanks in advance.

→ Reply

Eslam_Ahmed

3 weeks ago, # |

← Rev. 3 →

+29

CHATGPT

ChatGPT give me correct solution to B

LOL

I think most of participants use ChatGPT to get the solution

→ Reply

3 weeks ago, # ^ |

no, I didnt

→ Reply

3 weeks ago, # ^ |

many participants do cheat but the whole point of solving cp problems is to improve problem solving skills or to get dopamine boost after solving a problem which you don't get just by copy pasting code

→ Reply

NexTopper

3 weeks ago, # ^ |

-30

Conest should be unrated

→ Reply

qsmcgogo

3 weeks ago, # |

I love this round!

→ Reply

Kustizus168

3 weeks ago, # |

B is not easy :(((

→ Reply

3 weeks ago, # ^ |

+16

TBH this B = normal C, this C = normal D, this D = normal E. Tough round, but you need only 3 instead of 4 questions to get massive + delta.

→ Reply

akashtadwai

3 weeks ago, # ^ |

I just submitted it after the contest my bad :)

My idea was something like this (I'm trying to prove it formally, but couldn't yet succeed) —

If the binary representation has $$$x$$$ digits, then my claim is that — in the given constraints, we can build the array in almost $$$x+1$$$ digits. I wrote a recursive function to implement this.

AC Submission: https://codeforces.com/contest/1977/submission/262782660

→ Reply

Vampire

3 weeks ago, # |

-49

Unbalanced contest, downvoted

→ Reply

thatchemguy

3 weeks ago, # |

how to avoid tle in c?

→ Reply

accord

3 weeks ago, # |

I thought the problems this contest were nice (and normal). For some reason the standings seem very unbalanced though, so probably my judgement is incorrect.

→ Reply

Noluck_167

3 weeks ago, # |

← Rev. 2 →

B was tough ,but as many participants said code of Chat GPT passes ,means many submitted it maybe you should check the question before, i lost my cool when i saw 9000+ submission, man i am bad at this but not that bad. Anyway if someone is interested in Non Chat GPTed solution then here it is 262781288

→ Reply

123gjweq2

3 weeks ago, # ^ |

damn chat GPT is smarter than me

→ Reply

Noluck_167

3 weeks ago, # ^ |

feeling++

→ Reply

economist

3 weeks ago, # |

+13

during this round i suddenly realised that i have dyslexia

→ Reply

3 weeks ago, # |

Partial Editorial:

A — If n>=m and n and m share parity( both even or both odd) then yes, else no.

B: Repeatedly do the following until n = 0. If n is even. Output 0 and divide n by 2. If n is one more than a multiple of 4, Output 1 and divide n by 2. If n is one less than a multiple of 4, Output -1 and add one before dividing by 2.

C: If LCM(array)> max(array) answer is n.

Else, iterate through max(arr)'s factors,

For each factor track amt of items in list divisible by factor and LCM(those items).

Answer = max(amt of items if factor not in array and LCM(amt) = factor).

→ Reply

Abito

3 weeks ago, # ^ |

Is it enough to go through max(A) 's divisors only? I went through all divisors of all elements

→ Reply

3 weeks ago, # ^ |

yes, it is enough to go through the divisors of max(A), because this is LCM(A). All of item's divsors are simply a part of divisors of max(A).

→ Reply

akashtadwai

3 weeks ago, # ^ |

How do you get the idea that if $$$n\mod2==1$$$, decide the next digit based on $$$n\mod4$$$ ??

→ Reply

3 weeks ago, # ^ |

Looking at sample cases.

→ Reply

akashtadwai

3 weeks ago, # ^ |

← Rev. 3 →

Damn! I was just trying and figuring out how to build the array for the whole time in the contest and did not care about samples! Anyway, my approach is seemingly different from the above one (more complex). My claim is that for a number $$$n$$$ with binary representation consisting of $$$k$$$ digits, the answer can be constructed in at most $$$k+1$$$ digits. I'm trying to prove it formally but couldn't do it so far. Submission: https://codeforces.com/contest/1977/submission/262782660

→ Reply

3 weeks ago, # ^ |

It must be at most n+1 digits. Proof by contradiction.

If n+2th digit is 0. Then it serves no use.

If n+2th digit is 1. Then number is at least 2^(n+1) + 1 which is impossible as number only uses n bits.

If n+2 digit is -1. Then number is negative unless a higher digit is 1, which leads to same problem as described when n+2th digit is 1.

→ Reply

Tanjiro_Nezuko

3 weeks ago, # ^ |

A non ChatGPT-ed simple solution for problem B:-

If n%4==0, representation looks like "0 0 <that of n/4>"

If n%4==1, representation looks like "1 0 <that of (n-1)/4>"

If n%4==3, representation looks like "-1 0 1 <that of (n+1)/4>"

If n%4==2, representation looks like "0 <that of n/2>"

It meets all the conditions required.

Here's my submission :- https://codeforces.com/contest/1977/submission/262746874

→ Reply

3 weeks ago, # ^ |

Looks like there are many ways to solve C. Mine is exactly the same as your editorial lol.

262772972

→ Reply

on_sight

3 weeks ago, # |

solved B literally 3 minutes after the contest ended :(

i should have typed a bit faster or something

→ Reply

5hriom

3 weeks ago, # |

-79

Hi Stefan2417, in the problem C I have made a small error in factorisation (instead of checking till $$$\sqrt{n}$$$, I only checked till $$$\lfloor\sqrt{n}\rfloor$$$), this caused my solution to be wrong for some cases, one of them is: n=4, a=[1,2,3,36]

If possible kindly rejudge my solution 262765545, I hope I will be cautious next time to not make these mistakes, at the same time I feel it would be unfair if I got a good rank due to this small error.

→ Reply

egor.okhterov

3 weeks ago, # ^ |

Why do you care about rating? =)

→ Reply

3 weeks ago, # ^ |

WA is WA.

→ Reply

saquib2508

3 weeks ago, # ^ |

Ahh... bad luck. I used to have this feeling 10 years ago (feeling that such a small error should be allowed to rejudge, or why do I have to suffer for such a negligible mistake where my logic/thought process is correct), so I totally understand your frustration. Thanks for making me nostalgic.

Lesson: Error is error. 100% your fault. Own it, embrace it, learn from it, overcome it, grow from it.

→ Reply

5hriom

3 weeks ago, # ^ |

+16

Yes agreed, I owned up to my mistake in the comment, can anyone explain why am I getting downvotes? Have I offended someone?

→ Reply

Dominater069

3 weeks ago, # ^ |

+18

people misunderstood you, thats all. Also dont worry about it, weak tests happen often. I would say you definitely deserved it as you got the problem idea right which imo is much more important.

→ Reply

hashman

3 weeks ago, # ^ |

← Rev. 2 →

Ok, so what I think is that people probably misunderstood you: You were saying that your solution was incorrect because of a small typo, but it got marked as correct during the contest, because of which you got a good rank which you feel like you didn't deserve, correct (instead, they assumed that you were saying that your solution got WA because of a small bug, and so you should get AC just because it's so small)? Well, I'm saying that you do deserve it: Just look above / below you, there are so many people with solutions that aren't actually correct for D, but they work on all the testcases. In the end, in competitive programming, what matters is passing all the tests, not whether your solution is actually correct (although for most problems with strong tests, those two are equivalent...). So, if you deserve your rating, you will keep it in the next contest, and if you don't, well you're gonna drop down next contest anyway, so it's fine :)

→ Reply

5hriom

3 weeks ago, # ^ |

+15

Thanks a lot!!

→ Reply

eternal1422

3 weeks ago, # |

Damn, I couldn't even solve B when ChatGPT could :(

→ Reply

BLUmOOn

3 weeks ago, # |

← Rev. 2 →

MY submission 262742856 was accepted during the round but during testin g phase it got runt ime error on TC 1?I changed my language to c++ 20 and it got accepted.My question is why was it showing accpeted during the contest then? please look into this Stefan2417

→ Reply

artificialoryx

3 weeks ago, # |

scoring worse than last div2

how is that even possible...

→ Reply

naman005

3 weeks ago, # |

I have seen many solutions that seems to me ai generated, Is there a way to report such solutions?

→ Reply

tickbird

3 weeks ago, # |

solving two gray problem fast was sufficient to become an expert in this round

interesting

→ Reply

3 weeks ago, # ^ |

and getting three problem quickly is equivalent to master.

→ Reply

hackerbhaiya

3 weeks ago, # |

← Rev. 3 →

In problem D, is it true that atleast one of the first 39 columns should be special for the max case?

If not, hack : 262784406

UPD : Hacked :)

→ Reply

3 weeks ago, # |

short solution for D till editorial is not out
for each column consider all possible ops that can be performed to make i'th column special there will be n such ops possible for each column pick the operation which occurs most of the times ops can be store in the form of hashes

→ Reply

3 weeks ago, # |

Weak tests on Problem C, my solution is wrong shouldn't pass but it did.
Instead of checking if the whole LCM of the array is greater than the max. I just keep using modulo to avoid overflow, I used map to generate all possible LCMs hoping it wont TLE and I didn't.
It's easy to hack my solution just generate an array which it's LCM Mod 1e9+7 already exists in the array.

→ Reply

ZyadFva

3 weeks ago, # ^ |

$$$a_i \le 10^9$$$

so how can the LCM be greater than the MOD and in the array at the same time?

→ Reply

3 weeks ago, # ^ |

← Rev. 2 →

1
3
1 8 125000001

→ Reply

i_squared

3 weeks ago, # ^ |

Why didn't you just put a condition to check if lcm gets larger than 1e9 and output n in that case?

→ Reply

3 weeks ago, # ^ |

Because I made my submissions in the last 5sc. I tried to fix it after a WA I knew the LCM was overflowing and didn't have time to think about the condition.

→ Reply

-dub-otrezkov-

3 weeks ago, # ^ |

← Rev. 2 →

no, your solution can't be hacked since it is correct) you are searching for all possible LCMs only if LCM of elements is already in array, so it is less then $$$10^9$$$, and obviously all possible LCMs of any subsequence are divisors of global LCM so there are less than $$$\sqrt{10^9}$$$ possible LCMs hence your time complexity is $$$O(n \sqrt{maxA})$$$ (oh I see you find global LCM wrong way and solution already got hacked :(( )

→ Reply

3 weeks ago, # ^ |

Yes I was talking about the way I found the global LCM, now I got hacked. anyway thanks for the analysis you made.

→ Reply

BabyPopcorn

3 weeks ago, # ^ |

The tests are weak indeed. My solution clearly fails this test case

1
9
2 3 6 7 1003 1003 14042 21063 42126

Answer should be 5

→ Reply

deified

3 weeks ago, # |

-9

Please donate me +4 i want to be 1700 (crying emojis)

→ Reply

deified

3 weeks ago, # ^ |

-8

My prayers were not unheard , they increased 96, it was +75 before Happy happy to reach 1700

→ Reply

MisterGir

3 weeks ago, # |

In one sentence: the correct solution B is hidden in the tests.

→ Reply

3 weeks ago, # ^ |

Depends how are you approaching it to be honest, there are more ways than one to solve it.

→ Reply

_Will_W

3 weeks ago, # |

← Rev. 3 →

For problem B, my solution didn't pass the pretest. However, I think my output was correct if I'm not mistaken. I might be hella dumb but here is my answer for pretest 1 case 7:

input:
19
output:
6
-1 0 -1 -1 0 1

32 — 8 — 4 — 1 = 19
I don't know please help I'm a noobie.

→ Reply

hashman

3 weeks ago, # ^ |

You can't have two nonzero numbers beside each other.

→ Reply

_Will_W

3 weeks ago, # ^ |

Okay thanks stupid brain i guess.

→ Reply

treasuryonly

3 weeks ago, # ^ |

There are 2 consecutive -1 in -1 0 -1 -1 0 1 so this is invalid.

→ Reply

fanwen

3 weeks ago, # |

← Rev. 2 →

Can anyone explain to me why my submission 262785189 is accepted. I have read others and tried it out. It was correct. I do not understand why this is.

→ Reply

TahsinArafat

3 weeks ago, # |

The Test Cases are weak in D!

I designed a code to solve the problem which should solve the problem with O(m * m * n) time complexity! But the code passed with O(45 * m * n) time complexity, though it shouldn't pass!

Here is my solution: 262786847 Time: 249ms, Memory: 6976 KB

→ Reply

udta_kouwa

3 weeks ago, # |

← Rev. 2 →

Code Is this hackable?

→ Reply

RKS_Codes

3 weeks ago, # |

Can anyone tell me how I can improve? Seeing my recent performance in the past 2 contests, I seem to have hit a roadblock.

My C++ concepts are limited, and don't know much about DSA either. Should I stop participating in the contests for now and focus on learning or just continue practising from the problem set?

→ Reply

Dell_Know

3 weeks ago, # ^ |

Continue practicing on the problemset. Solve problems around your level and you will be good.

→ Reply

Rzhek

3 weeks ago, # |

← Rev. 10 →

Guys please help. I AC'ed on B during the contest, but I got a TLE during system check. But when i submitted the exact same code but without fast io, it AC'ed.

Can anyone explain why it happened?

With fast io 262763870 Without fast io 262791262

→ Reply

treasuryonly

3 weeks ago, # ^ |

cout << nums.size() << "\n";

You can replace "\n" with '\n' and submit again.

→ Reply

Rzhek

3 weeks ago, # ^ |

How is that supposed to fix it? P.S. still TLE

→ Reply

treasuryonly

3 weeks ago, # ^ |

According to this endl or "\n" will make the program flush, but even after replacing it still gives TLE then maybe because of another reason.

→ Reply

hphuong

3 weeks ago, # ^ |

I think the actual problem in your code is RTE

for (int j = 1; j <= len; j++){ nums[i+j] = 0; }

In this line of code, i + j can be equal to nums.size(), which will eventually cause out of bound. Still I don't understand why removing fast I/O fixed, maybe due to the vector capacity allocation.

→ Reply

eklavya_k

3 weeks ago, # |

editorial please. How to solve D?

→ Reply

nsqrtlog

3 weeks ago, # ^ |

Use hashing. For each column, only $$$n$$$ possible sets of rows can make it special, and all of them can be calculated quickly since they are very similar (any two sets only differ in 2 rows). Then just find the max frequency hash.

→ Reply

3 weeks ago, # |

← Rev. 3 →

My solution to C by factorization and brute-force: 262772972

First, factorize each input numbers to product of some a_i ^ p_i, and maximize each p_i to get the LCM.

If LCM is greater than the largest input, the answer is trivial (n), otherwise:

Let's brute-force each p_i, i.e. brutu-force each (including non-prime) factor of LCM:

This factor should not occur in the inputs.
Choose all inputs that are divisible by this factor.
Verify that the LCM of the chosen inputs are this factor.
If all the above is satified, then we consider this as a proper answer. Maximize the count of chosen inputs during the brute-force.

Integers below 10^9 with the most count of factors is 735134400, which has 1344 factors. Time cost: 1344 * n * (count of prime factors) + cost of factorization

→ Reply

pride_._

3 weeks ago, # ^ |

nice solution, some of my friends had a solution which got accepted in the contest, but later when I tried, failed on test case 18

Your solution is absolutely correct

→ Reply