Codeforces Round 978 (Div. 2)

6 недель назад, # ^ |

+24

Contest is based on Mexican OI. Who do you think?

→ Ответить

21.0

5 недель назад, # ^ |

← Rev. 3 →

they could start the contest 2 or 3 hours earlier so the most of countries that are good in IOI can participate in the contest and wtf so many people cried and down voted my comment did I say something bad?

and contests like this are an unfair way to increase rating of the participants in some countries

→ Ответить

5 недель назад, # ^ |

yes, mexico should shift its OI to cater to non-mexican participants.

→ Ответить

21.0

5 недель назад, # ^ |

Who cares about IO this was a rated contest for any div2 if they want to participate in day time in Mexico they could release it as a gym

→ Ответить

5 недель назад, # ^ |

fym "who cares about OI" this is literally a mexican contest, they have no obligation to release it as a div2 contest but they did. if you want to participate in the contest at daytime take a virtual.

→ Ответить

Cyclonestopper9000

6 недель назад, # |

← Rev. 2 →

Where are the point values?

→ Ответить

RE_Prince

6 недель назад, # ^ |

dunno, probably they havent decided on some of the problems yet(?

→ Ответить

MaxValgen_

6 недель назад, # |

Is this contest IOI formatting?

→ Ответить

anshikachhabra_

6 недель назад, # |

← Rev. 2 →

I received an e-mail a few hours back, saying that the round starts on Sunday, October, 13, 2024 19:35 (UTC). Please resolve the discrepancy, if any. Thanks!

Nvm, it was a misinterpretation on my part :-/

→ Ответить

sohamdascf

6 недель назад, # |

-10

01:35 am ??? nah man i will drop dead by the time it gets started.

→ Ответить

STARSHIP_666

6 недель назад, # |

Nice but why does the timing of the competitions continue getting weird and weird

→ Ответить

6 недель назад, # |

Score distribution?

→ Ответить

cly312

6 недель назад, # |

In China,the time is 3:35.Even in Russian time, it is still 22:35.Is it free time for Russians?

→ Ответить

Nksp

6 недель назад, # |

Score distribution ??

→ Ответить

abra_r

6 недель назад, # |

1:35 in Bangladesh.

→ Ответить

programmer5777

6 недель назад, # |

Reveal the score distribution please..

→ Ответить

hundunlilun1

6 недель назад, # |

Zzz

→ Ответить

sach_in_sigma

6 недель назад, # |

Won't be able to participate due to the timing T_T Anyway good luck to all of ya who'll be participating...

→ Ответить

comingsoon.cpp

6 недель назад, # ^ |

Don't be lazy

→ Ответить

sach_in_sigma

6 недель назад, # ^ |

can't help it have to get my well deserved sleep bro

→ Ответить

Xiao_2710

6 недель назад, # |

I hope i remain a specialist after this round.

→ Ответить

mizanur26

6 недель назад, # ^ |

← Rev. 2 →

You will. just don't participate

→ Ответить

PriyanshuRaj1000

6 недель назад, # |

Bad timing for Indians.

→ Ответить

focus_2024

6 недель назад, # |

+23

I think this is the first round in the history of Codeforces when there will be no cheaters because time is unusual. (At Night)

→ Ответить

cuyu

6 недель назад, # |

im in UTC +7, i mean i need to take a sleep then open laptop in mid night to join :)

→ Ответить

CandidFlakes

6 недель назад, # |

Won't be able to participate because of timing.

→ Ответить

surgutti

6 недель назад, # |

god bless this round, let there be a 2-minute delay

→ Ответить

Be.Sabar

6 недель назад, # |

Today's contest starts at 1:30 am in Bangladesh :3

→ Ответить

pratham__22

6 недель назад, # |

OK...Good Night

→ Ответить

bihnehminduh

6 недель назад, # |

glhf

→ Ответить

Shubhamx9

6 недель назад, # |

can't i register in between the contest?

→ Ответить

picoton

6 недель назад, # |

-13

less than 7000 people made a submission lol. i wonder why

→ Ответить

iiand

6 недель назад, # ^ |

Normal ppl sleep

→ Ответить

picoton

6 недель назад, # ^ |

-10

26k people registered tho

→ Ответить

livingstone

6 недель назад, # |

+17

How to solve B??

→ Ответить

HTdeck

6 недель назад, # ^ |

ye — kept getting TLE

→ Ответить

6 недель назад, # ^ |

$$$answer = max(a_{max}, \sum^n_{i = 1}{\lceil \frac{a_i}{x} \rceil})$$$

→ Ответить

sashshaikh12

6 недель назад, # ^ |

but why though?

→ Ответить

6 недель назад, # ^ |

← Rev. 2 →

The $$$a_{max}$$$ part is obvious, however the second part is pure guesswork. I had already given up on the contest but wanted to submit this solution just on the off 0.01% chance that it is correct.

→ Ответить

YipChip

6 недель назад, # ^ |

You can easily put all $$$a_i$$$ in priority queue to solve it. Consider that we always pop first $$$m$$$ types. For each type we minus $$$1$$$ and push in queue. After $$$k$$$ times, the rest types are less than m. We can get that the rest answer is the maximum for the rest. Following the steps, we can solve it with $$$ans = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{m} \right\rceil\right)$$$

→ Ответить

DSP-friendly

6 недель назад, # ^ |

The correct formula is: $$$answer = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{x} \right\rceil\right)$$$

→ Ответить

6 недель назад, # ^ |

I wonder, how did I get Accepted with a wrong formula, hmmmm?

→ Ответить

6 недель назад, # |

+19

Problem C is such a pointless DP exercise.

→ Ответить

wuhudsm

6 недель назад, # |

In D2, anyone knows how to use 3 operations when n=3? I writed tons of case work and can't solve it ;)

→ Ответить

6 недель назад, # ^ |

← Rev. 2 →

I felt like D2 involves some graph theory. May be whenever there is some cycle detected, we have to stop...

No Solid idea though. Just sharing my thoughts...

→ Ответить

jampm

6 недель назад, # ^ |

answer

Sorry for the delayed editorial, we (the team of writers) have also been hosting the Mexican Olympiad in informatics and monitoring both contest. Give us some minutes we'll finish it up.

→ Ответить

Dragnoid99

6 недель назад, # ^ |

Finished yet?

→ Ответить

chh9976

6 недель назад, # ^ |

← Rev. 3 →

I think no, the number of all possible combinations of 3 players with 1 imposter is 12, while 3 operations will give you at most 8 different outcomes. You cannot make one to one mapping from the outcome to the three players.

→ Ответить

sevlll777

6 недель назад, # ^ |

← Rev. 3 →

if in 2 queries you have no cycle -- there are still 3 possibilities for imposter, but only 1 query with 2 different outcomes left -> impossible

if you have cycle in 2 queries and answers are different, one of them is imposter -> easy to see no rest query can give you who exactly is imposter (cause you know nothing about 3rd player)

→ Ответить

6 недель назад, # |

Really loved the problems.

A-B-C are getting difficult day by day... It took me 1 hour to solve just ABC :|

→ Ответить

sevlll777

6 недель назад, # |

how E1 is 2250 score huh

→ Ответить

aryanc403

6 недель назад, # ^ |

+10

video editorial by Um_nik for 2022E2 - Billetes MX (Hard Version) aka Atcoder: Grid and Integers

→ Ответить

6 недель назад, # ^ |

thanks for sharing.

→ Ответить

sashshaikh12

6 недель назад, # |

+12

was it just me or B felt really hard. spent 1 hour 50 minutes on it and didnt proceed with anyything

→ Ответить

Raj_Tiwari

6 недель назад, # ^ |

Overthinked :(

→ Ответить

6 недель назад, # ^ |

You're not alone!

→ Ответить

VMaksimoski008

6 недель назад, # |

Okay, who thought that C is a good enough for a div2 round? It is simply pointless implementation task.

→ Ответить

ciprianamza

6 недель назад, # ^ |

How did you solve it?

→ Ответить

virusss

6 недель назад, # ^ |

consider i as the current index in the upper string and j in lower one , now there can only be 3 cases i exceeding j by 1 , j exceeding i by 1 or i and j being equal.. make 3 states of dp corresponding to one i and the three cases.. it will be an n*3 dp..

→ Ответить

turkoarias

6 недель назад, # |

+12

It's hard to undertand that more than 30 people made feedback and nobody noticed the huge difficulty of the problemset. Only 3 solved in problem D2 (tourist and rainboy getting WA), 26k registered users but only 7k could solve problem A, some people beeing about top1000 without beeing able to solve problem B. The problems were quite intersting (at least trying them), but completely unbalanced.

→ Ответить

6 недель назад, # ^ |

+15

I think the point distribution checks out. C is harder than a normal C, so it has 1750 points (more than usual), D1 is easier than normal D, so it has 1750 points (less than usual), D2 is worth 3750 points so it's harder than most D2F. B is oddly hard though.

→ Ответить

zrnstnsr

6 недель назад, # ^ |

Agreed. B is very hard if one lacks attention.

→ Ответить

6 недель назад, # ^ |

+10

I think B is a problem that is very easy to overthink. I wasn't able to solve it, but the solution is the first idea I thought of (and rejected).

→ Ответить

turkoarias

6 недель назад, # ^ |

A was difficulter that average A, not only by the really low AC, the time that took thus AC is a lot for an A too. B gives only 250 point more than A and it was quite difficult and C was annoying to implement but not that hard to see the DP. D2 could be harder than most D2, but... what the point of having 3 out of 7 problems that won't be solved by more than 30 people? Even red coders can't solved that problem, I feel it's not worth it a problemset like this. Maybe for a global could work better

→ Ответить

6 недель назад, # ^ |

A is slightly harder than usual but fine. Hard A usually isn't a problem. C has annoying implementation, which is justified because it is worth more points.

On your point that D2/E1/E2 aren't solvable for most people: just treat this round as a 5-problem round. Ignore D2 and E2 and it becomes a pretty normal round: ABCD are all doable and maybe E is slightly harder than usual. It's fine.

→ Ответить

bihnehminduh

6 недель назад, # |

Problem B gave me new neurons.

→ Ответить

Hori

6 недель назад, # |

C can be solved for 3 rows too!

Code courtesy of liympanda https://pastebin.com/mjcPwbAa

→ Ответить

tickbird

6 недель назад, # |

literally what is idea behind of C?

how to be good at problem like this, it's so hard

→ Ответить

C_c-c_C

6 недель назад, # ^ |

us bro.

→ Ответить

6 недель назад, # ^ |

C is a simple dp.. as we can't have 2 dimensions due to n being large to track both the first row pointer and second row pointer I just keep the first row pointer and the 2nd state being difference between first row and second row pointers.. The difference can never be more than 1 to be eligible for dividing districts.

→ Ответить

Kaitak

6 недель назад, # |

can problem C be solved greedly ? DP was always at the back of my mind but I was too lazy to implement it(Maybe cuz am not very good at implementing quickly).

→ Ответить

jeal0uspengu1n

6 недель назад, # ^ |

idts, you've choices to make at each moment and that can't be decided greedily

→ Ответить

jeal0uspengu1n

6 недель назад, # |

+16

wtf was wrong with B ;;

→ Ответить

vitosevskich

6 недель назад, # |

What is the proof behind answer in B?

→ Ответить

mr_lolololol

6 недель назад, # ^ |

← Rev. 2 →

Suppose we have $$$C \geq \max a_i$$$ customers.

Imagine a box with $$$C$$$ rows and $$$x$$$ columns. Filling up your box column by column is sufficient.

→ Ответить

6 недель назад, # ^ |

and how do u know which car to put in which row?

→ Ответить

mr_lolololol

6 недель назад, # ^ |

Fill up every column of your box from up to down. Because $$$C \geq \max a_i$$$, doing so ensures that you won't place two cars of same type into the same row.

→ Ответить

6 недель назад, # ^ |

Thank you.. i tried with paper and pen using your approach.. It helped me upsolve this. First I did this below binary search that runs in nlog(1e16)

bool isPossible(long long customersCnt) {
    if(customersCnt * fomo < totalCars) {
        return false; //as each CX can only buy maximum of fomo cars, even if everyone buys fomo cars we can't sell every car.
    }
    for(int i=0;i<models;i++) {
        if(customersCnt < carsCnt[i]) {
            return false; // I can't sell more than one same car to same CX
        }
    }
//true in every other case by placing cars in the order mentioned by mr_lolololol
    return true;
}

Later I was able to easily convert this to O(n)

→ Ответить

iamfreeezing

6 недель назад, # |

+11

i will never recover from B's trauma

→ Ответить

alankritsingh778

5 недель назад, # ^ |

us bro us

→ Ответить

puneetks1920

6 недель назад, # |

Felt like I'm giving a div 1 contest today

→ Ответить

Mathavaroopan

6 недель назад, # |

← Rev. 2 →

I'm still wondering why my binary search on the answer solution didn't work on problem B. Can we say that the minimum "mid" >= max(arr) and mid * x >= sum(arr) would suffice?

→ Ответить

susus

6 недель назад, # ^ |

← Rev. 2 →

could be cause u are using int for the sum of the whole array instead of long long when it can exceed the int limit maybe, that's something similar that happened to me on my 1st submission

→ Ответить

Mathavaroopan

6 недель назад, # ^ |

I used #define int long long. I don't think that was the issue.

→ Ответить

_Unseen_

6 недель назад, # ^ |

BS works on B: https://codeforces.me/contest/2022/submission/285725858 P.S: Sorry for the overworked and terrible implementation :(

→ Ответить

Parsa_Abolhassani

6 недель назад, # |

B made me feel empty.

→ Ответить

re.Think

6 недель назад, # |

← Rev. 2 →

In question C, 2nd test case, shouldn't the answer be 4?

We can divide it into 4 districts such that each one has 2 Js.

I wrote the solution but I didnt see test cases and now nothing makes sense,

Edit — I have to look for As and not Js. I am way too much sleep deprived, -_-

→ Ответить

Avid.Angler

6 недель назад, # |

← Rev. 2 →

+10

Why were A and B so hard? If they are going to be this hard, there should be more div 3 contests.

→ Ответить

6 недель назад, # ^ |

Agreed .

→ Ответить

ritzo38

6 недель назад, # ^ |

True and it's getting really hard to reach pupil these days or idk maybe I'm just bad : (

→ Ответить

swarbhatia

6 недель назад, # ^ |

Agreed, B destroyed me.

→ Ответить

EndMyMisery

6 недель назад, # |

I solved problem B with binary search.

→ Ответить

Mathavaroopan

6 недель назад, # ^ |

I'm still wondering why my binary search on the answer solution didn't work on problem B. Can we say that the minimum "mid" >= max(arr) and mid * x >= sum(arr) would suffice? Is this what you did?

→ Ответить

aditya_108

6 недель назад, # |

What is the solution of D1 ?

→ Ответить

SkibidiPilav

6 недель назад, # ^ |

my solution was to group all people in groups of 3(ill explain how i handle if n%3!=0). so for each group of 3 you query 1,2 2,3 3,1 . and then lets say the type of the 1st guy is 0. then the type of 2nd guy and 3rd guy is fixed. and then you can check if the 3rd query contradicts the type of the 1st and 3rd guy. if this happens then you know that the impostor is one of these 3 guys, and you can basically brute force the solution. and if n%3==1 and we dont find an impostor then its the n-th guy for sure, and if n%3==2 you can just check both with the first guy, since we know the 1st guy isn't an impostor and find out which one is the impostor. this works in n+ 2 queries at worst. there is a simpler solution that ive seen though

→ Ответить

asdasdqwer

6 недель назад, # ^ |

Consider comparing two players with each other (ask each other about the other one). If the results of the queries are the same, then both are either knights or knaves. If the results are different, then one of them is the impostor. To find out which one is the impostor, compare them with a third player. So now, you can compare player 1 with player 2, then player 3 with player 4, etc. until you find the impostor. Submission

→ Ответить

LordLouis04

6 недель назад, # ^ |

u can make groups of 2 people, u make they answer query about the other, in this groups of 2 if the answer are different then the impostor is one of them (u use n queries or n+1 and reduce the impostor to 2 candidates) then u pick one of those 2 and make a group of 2 with a third one, if the answer are differents then u have the impostor, otherwise the impostor was the other.

→ Ответить

aditya_108

6 недель назад, # ^ |

Thanks. Got it.

→ Ответить

Shoeib

6 недель назад, # |

+15

C is the worst dp problem i have ever seen

→ Ответить

999_ms

6 недель назад, # ^ |

Maybe It's a div3 D or div4 E , nonetheless you need to get used to implementation to tackle such:)

→ Ответить

LordLouis04

6 недель назад, # |

B = guessing the answer and hoping it's correct.

→ Ответить

6 недель назад, # ^ |

not really. It's simple maths trick, it took me more than 20 minutes to prove this trick with pen and paper. Not everyone guesses. Guesses won't get you far.

Only mathematical proofs and intuitions will.

→ Ответить

Parsa_Abolhassani

6 недель назад, # ^ |

can you explain your proof?

→ Ответить

alpha1215

6 недель назад, # ^ |

There's nice proof by IceKnight1093
proof

→ Ответить

polsage

6 недель назад, # ^ |

how did you prove that trick, like i used that trick in an earlier problem where i was not able to come up with it so this time i knew after sometime what do but still i am not able to prove it

→ Ответить

6 недель назад, # ^ |

← Rev. 2 →

Try thinking this way,

0) N < K : This is very easy to understand. If the salesperson can convince to buy 'K' distinct items, then no matter what, we can Never sell 'K' items to the same customers ( since N < K ) . In this case, it is easy to see, ans is just Max of an array ( Because, everytime we will sell as many as possible items to the customer ).

1) N == K : Here also, similar logic like above. answer will be Max of an Array.

2) N >= K : This is crucial and tricky part. Implement Greedy logic on the sample test case [ 2 , 2, 3 , 3, 5 , 5, 5, ] for K = 4 . It is easy to see that, it is optimal to sell the items, which has the highest frequency. Everytime we pick top 4 elements from this array, and reduce their values by '1' and then again sort the array. After 2 operations, we will get this [ 2 , 2 , 2 , 2 , 3 , 3 , 3 ].

This is where I got the intuition. CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?

Every time we reduce 1 from top K member, the sorted set will sort itself and pick the optimal 'K' values in next time. This way, you are ALWAYS REMOVING 'K' ITEMS from the set ( except for the last time, where you will remove remaining (SumOfArray % K ) items ). So

answer = (SumOfArray / K ) + (SumOfArray % K > 0 ? 1 : 0)

There is small edge case required, when the there is very large number in array, and we need to reduce that number every operation. To tackle this edge case, just take answer = max(answer, maxOfArray)

This is how I approached the solution.

→ Ответить

Karim__2

6 недель назад, # ^ |

I tried to brute force this problem using Multiset just like you said.

but i took the $$$x$$$ biggest elements and substracted them from the smallest one and then reinserted the new values to the multiset and repeat

why didn't this work ?

285732512

→ Ответить

bruce_x001

6 недель назад, # ^ |

← Rev. 3 →

It won't work

Counter Test Case :

1
5 3
3 3 3 3 3

Reason : You are taking k largest elements and then subtract the minimum one from all those

but the optimal way is to subtract 1 from each and now perform with modified k largest elements from the array.

I hope it is clear. If not, then try to dry run the test I have given, you'll get it.

→ Ответить

6 недель назад, # ^ |

READ AGAIN , what I have written.

→ Ответить

bruce_x001

6 недель назад, # ^ |

OK ok got it ! I haven't read your comment. Thanks for sharing

→ Ответить

swarbhatia

6 недель назад, # ^ |

Thankyou, I was able to get the intuition behind this.

→ Ответить

polsage

6 недель назад, # ^ |

Ohk got it thank you

→ Ответить

kir_tan22

6 недель назад, # ^ |

← Rev. 2 →

@ papa-ka-para

CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?

why did you not brute force it? i did in 285718545

what possibly went wrong?

→ Ответить

https://codeforces.me/contest/2022/submission/285743640

6 недель назад, # ^ |

If your bruteforce is passing then test cases are weak. The values are from 1 to 10^9. BF solution shouldn't pass.

→ Ответить

kir_tan22

6 недель назад, # ^ |

no it is not passing. i was wondering why so I asked. Why though? isn't it like <= 10*(n) with n<=5e5 ?

it is failing on some test case and i do not know what is wrong in doing this BF

→ Ответить

pranavsrivastav24

6 недель назад, # ^ |

plz provide the proof, i cant think of it at this time

→ Ответить

alpha1215

6 недель назад, # ^ |

link to comment

→ Ответить

34z12000

6 недель назад, # ^ |

+10

B's easily provable, that's why it's B

→ Ответить

aryanc403

6 недель назад, # ^ |

Video editorial by adaptatron
Their video is for x=2 but same arguments hold here.

→ Ответить

SkibidiPilav

6 недель назад, # ^ |

I think this is a well known trick. i have solved something similar before, and I think it's not that hard to come up with the quick solution.

→ Ответить

Klaus26

6 недель назад, # ^ |

Yeah, it is well known, nevertheless I haven't seen a well known proof (other different form the greedy algorithm: always taking first $$$x$$$ greatest elements) xd I almost solve it but I missed the lower bound $$$max_{1 \leq i \leq n} (a_i)$$$ part.

I hope to see a good editorial with a proper proof for this kind of problems.

→ Ответить

Dominater069

6 недель назад, # ^ |

← Rev. 3 →

+15

TLDR : just fill stuff cyclically, and it can be proven to be good

We want to prove that ans = max(ceil(sum / k), max(a[i])) is achieveable. Consider "ans" number of boxes (0 — indexed) each with capacity x

We do the following process :

p = 0
for i from 1 to n : 
   for j from 1 to a[i]: 
      put(type i in box p) 
      p = (p + 1) % ans

This will always provide a valid arrangement. Why?

1) First condition : No box will have more than x things, well this is obviously true because ans >= sum / k, and we fill stuff cyclically

2) Second condition : no two things of same type end up in one box Proof by contradiction : assume that two things end up in same box, then it means that wherever we started filling type t, we returned back to it after cycling through everybody else. Therefore, a[t] > ans, but ans >= max(a). Contradiction

→ Ответить

Shoeib

6 недель назад, # ^ |

just binary search on the answer

→ Ответить

kovidsaivemuri

6 недель назад, # ^ |

-18

Donno Why So many people are complaining about b. It is simple either we need max(arr) number of customers or total/k which ever is maximum. simple to prove it.

Spoiler

void solve(){
    ll n, k; cin>>n>>k;
    vector<ll> arr(n);
    ll mx=0, tot=0;
    for(auto &x: arr) {
        cin>>x;
        mx = max(mx, x);
        tot+=x;
    }
    tot = (tot%k)?((tot/k)+1):(tot/k);
    ll ans=max(tot, mx);
    cout<<ans<<'\n';
}

→ Ответить

999_ms

6 недель назад, # ^ |

← Rev. 2 →

Binary search always works here , if u get to this point(how to check for BS), mathematical formula makes much sense(and provable!)

→ Ответить

theRealChainman

6 недель назад, # |

Wrong Answer on pretest 2 for D2 :(

→ Ответить

programmer5777

6 недель назад, # |

What was the problem with B..(am I wrong or they)??

→ Ответить

Cowdeforces

6 недель назад, # |

How to solve B???

→ Ответить

alpha_6124

6 недель назад, # ^ |

its quite standard problem (most time you've seen of breaking into two groups)

cout <<1ll*max((sum+x-1)/x,mx) << endl;

→ Ответить

navneetk12

6 недель назад, # |

https://leetcode.com/problems/domino-and-tromino-tiling/description/ problem C looks much similar to this one, a DP exercise basically transformed to a new question!

→ Ответить

zachman99323

6 недель назад, # |

Why did Problem B have the condition x <= 10?

→ Ответить

SkibidiPilav

6 недель назад, # ^ |

i got WA on pretest 2 by doing something with a vector of size x, so maybe its to trick people? if i saw x was up to 10^4 or smth, i wouldnt waste 2 attempts on that, so it could be just to confuse people

→ Ответить

ant0xic

6 недель назад, # |

← Rev. 2 →

Can somebody help me with the Problem B, please? I don't understand, why I'm wrong. P.S. I know how to solve it correct, but I just so interested in reasons my "h2h" solution doesn't work.

→ Ответить

Boboge

6 недель назад, # |

← Rev. 2 →

My solution(285744957) for E2 using binary search to check when the answer is 0 got TLE. Is that a constant issue or did I write something wrong?

upd: It is a constant issue. I got accepted after removing some useless edges. See 285745386.

→ Ответить

jampm

6 недель назад, # ^ |

+10

This was the first solution I came up with when thinking about the problem. There's also a couple of alternative solutions. There's also a way of solving the problem online in $$$\mathcal{O}\left(n\log(n)\right)$$$.

→ Ответить

TheZachMan

6 недель назад, # ^ |

Mine (285739542) got TLE on Pretest 21 (technically only an E1 solution, but easy to make an E2 solution from it) — would also like to know if it's because of python or if there's a way to do it faster (in particular, I'm suspect of my test function, which is just a BFS looking for a cycle, and doesn't update anything).

→ Ответить

Rohak

6 недель назад, # |

What's the point of B? I've solve this problem at least twice before.

→ Ответить

jeroenodb

6 недель назад, # |

+15

Thank you for the problemset! D2 is a very cool problem.

→ Ответить

_Unseen_

6 недель назад, # ^ |

Sorry for commenting on this thread, but could anyone pls clarify my doubt in D1?

We know that if ask(i,j)!=ask(j,i) then one of them must be the impostor, However, I'm slightly confused as I queried on pairs that are distinct (i.e 1,n 2,n-1 and so on). Since the grader was adaptive, I declared j as impostor if ask(i,j)!=ask(j,i), since it's possible for any of them to be the impostor, and since the queries are independent of the previous ones.

Why do we need to verify again which one is the impostor once we get the above condition?

→ Ответить

Aspergillus

6 недель назад, # ^ |

Can you explain your solution to D2?

→ Ответить

jeroenodb

6 недель назад, # ^ |

+27

For $$$n=3$$$ you can find out on paper what is the best strategy, and it turns out $$$f(3)=4$$$. For all other $$$n$$$, I made a strategy such that $$$f(n)=n$$$. Basically you can always take person $$$1$$$ and $$$2$$$, do queries $$$1 2$$$ and $$$2 1$$$, this detects the impostor. If you detect it, do two more queries to find out which of the two it is. If not, you reduced to a subproblem of $$$n-2$$$ people, and used $$$2$$$ queries. For $$$n=5$$$ and $$$n=4$$$ you need to write a special case which does the querying in $$$n$$$ moves. For $$$n=5$$$ the main trick is first querying $$$1 2$$$,$$$2 3$$$ and $$$3 1$$$. This lets you notice if impostor is one of $$$1$$$,$$$2$$$ or $$$3$$$.

Proof sketch of the lowerbound on $$$f(n)$$$: Lets look at the queries as directed edges that get added to a graph. If there are $$$n-1$$$ edges placed, then some node has indegree $$$0$$$, and some node has outdegree $$$0$$$ by pigeonhole.

Case $$$1$$$: If there are two different nodes with either indegree $$$0$$$ or outdegree $$$0$$$, then there are still multiple options of where the impostor could be, so if we always gave queries that are consistent, never revealing the impostor, the player cannot know where the impostor should be.

Case $$$2$$$: If the indegree $$$=0$$$ and outdegree $$$=0$$$ coincide, then the graph must look like a bunch of cycles and one isolated node. If we make sure that at the $$$n-1$$$'th query, if this query closes a cycle, and we would end up in Case $$$2$$$, we give an inconsistent answer now, such that the impostor is inside some cycle of $$$\geq 2$$$ nodes, then the player cannot know which of the nodes the impostor is in,

This proves $$$n-1$$$ queries are not enough to know exactly where the impostor is. And we have a strategy for $$$n$$$ queries, that does find the impostor, except for $$$n=3$$$ which is a special case.

→ Ответить

Aspergillus

5 недель назад, # ^ |

Thanks, implemented and got AC.

→ Ответить

Ioana

6 недель назад, # |

+21

I can swear I saw something super similar to E1 before (possibly but not necessarily on codeforces) — might have been sum instead of xor but it was the same underlying task of either finding a contradiction or counting the unforced cells by merging row restrictions when they share at least a column, does anyone remember any similar problem? Also it's NOT the atcoder one (Grid Integers)

→ Ответить

patatapum

6 недель назад, # ^ |

+10

Maybe Extending Set of Points? I found it very similar to this one.

→ Ответить

Ioana

6 недель назад, # ^ |

Found what I was thinking about: Tick, Tock !

The condition here is being able to make all cells equal by adding 1 to either to an entire row or an entire column, which ends up being equivalent to each subgrid having equal sums of their opposite corners (a[i1][j1] + a[i2][j2] = a[i1][j2] + a[i2][j1]). Other than that it's the same idea — some cells are not occupied and we need to count the valid ways to fill them.

→ Ответить

Osama_Fahim

6 недель назад, # |

Can someone explain to me why my solution for problem b is wrong which case could give the wrong and ?285742700

→ Ответить

detective...dots

6 недель назад, # |

← Rev. 2 →

Just solved B (literally by luck), This is the most problem that ever made me mad, I hope that the tutorial will show why this solution is valid

→ Ответить

Karim__2

6 недель назад, # ^ |

nice pfp

→ Ответить

Shoeib

6 недель назад, # |

D1 is much easier than C (they should be swapped)

→ Ответить

YipChip

6 недель назад, # ^ |

I agree, but C is easy to think about but hard to code.

→ Ответить