Codeforces Round 978 (Div. 2)

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

+24

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

→ Ответить

21.0

4 недели назад, # ^ |

← 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

→ Ответить

4 недели назад, # ^ |

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

→ Ответить

21.0

4 недели назад, # ^ |

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

→ Ответить

4 недели назад, # ^ |

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

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

← Rev. 2 →

Where are the point values?

→ Ответить

RE_Prince

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

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

→ Ответить

MaxValgen_

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

Is this contest IOI formatting?

→ Ответить

anshikachhabra_

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

← 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

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

-10

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

→ Ответить

STARSHIP_666

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

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

→ Ответить

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

Score distribution?

→ Ответить

cly312

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

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

→ Ответить

Nksp

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

Score distribution ??

→ Ответить

abra_r

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

1:35 in Bangladesh.

→ Ответить

programmer5777

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

Reveal the score distribution please..

→ Ответить

hundunlilun1

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

Zzz

→ Ответить

sach_in_sigma

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

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

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

Don't be lazy

→ Ответить

sach_in_sigma

4 недели назад, # ^ |

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

→ Ответить

Xiao_2710

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

I hope i remain a specialist after this round.

→ Ответить

mizanur26

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

← Rev. 2 →

You will. just don't participate

→ Ответить

PriyanshuRaj1000

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

Bad timing for Indians.

→ Ответить

focus_2024

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

+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

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

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

→ Ответить

CandidFlakes

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

Won't be able to participate because of timing.

→ Ответить

surgutti

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

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

→ Ответить

Be.Sabar

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

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

→ Ответить

pratham__22

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

OK...Good Night

→ Ответить

bihnehminduh

4 недели назад, # |

glhf

→ Ответить

Shubhamx9

4 недели назад, # |

can't i register in between the contest?

→ Ответить

picoton

4 недели назад, # |

-13

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

→ Ответить

iiand

4 недели назад, # ^ |

Normal ppl sleep

→ Ответить

picoton

4 недели назад, # ^ |

-10

26k people registered tho

→ Ответить

livingstone

4 недели назад, # |

+17

How to solve B??

→ Ответить

HTdeck

4 недели назад, # ^ |

ye — kept getting TLE

→ Ответить

4 недели назад, # ^ |

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

→ Ответить

sashshaikh12

4 недели назад, # ^ |

but why though?

→ Ответить

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

→ Ответить

4 недели назад, # ^ |

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

→ Ответить

4 недели назад, # |

+19

Problem C is such a pointless DP exercise.

→ Ответить

wuhudsm

4 недели назад, # |

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

→ Ответить

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

Finished yet?

→ Ответить

chh9976

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

← 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)

→ Ответить

4 недели назад, # |

Really loved the problems.

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

→ Ответить

sevlll777

4 недели назад, # |

how E1 is 2250 score huh

→ Ответить

aryanc403

4 недели назад, # ^ |

+10

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

→ Ответить

4 недели назад, # ^ |

thanks for sharing.

→ Ответить

sashshaikh12

4 недели назад, # |

+12

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

→ Ответить

Raj_Tiwari

4 недели назад, # ^ |

Overthinked :(

→ Ответить

4 недели назад, # ^ |

You're not alone!

→ Ответить

VMaksimoski008

4 недели назад, # |

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

→ Ответить

ciprianamza

4 недели назад, # ^ |

How did you solve it?

→ Ответить

virusss

4 недели назад, # ^ |

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

4 недели назад, # |

+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.

→ Ответить

4 недели назад, # ^ |

+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

4 недели назад, # ^ |

Agreed. B is very hard if one lacks attention.

→ Ответить

4 недели назад, # ^ |

+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

4 недели назад, # ^ |

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

→ Ответить

4 недели назад, # ^ |

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

4 недели назад, # |

Problem B gave me new neurons.

→ Ответить

Hori

4 недели назад, # |

C can be solved for 3 rows too!

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

→ Ответить

tickbird

4 недели назад, # |

literally what is idea behind of C?

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

→ Ответить

C_c-c_C

4 недели назад, # ^ |

us bro.

→ Ответить

4 недели назад, # ^ |

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

4 недели назад, # |

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

4 недели назад, # ^ |

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

→ Ответить

jeal0uspengu1n

4 недели назад, # |

+16

wtf was wrong with B ;;

→ Ответить

vitosevskich

4 недели назад, # |

What is the proof behind answer in B?

→ Ответить

mr_lolololol

4 недели назад, # ^ |

← 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.

→ Ответить

4 недели назад, # ^ |

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

→ Ответить

mr_lolololol

4 недели назад, # ^ |

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.

→ Ответить

4 недели назад, # ^ |

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

4 недели назад, # |

+11

i will never recover from B's trauma

→ Ответить

alankritsingh778

4 недели назад, # ^ |

us bro us

→ Ответить

puneetks1920

4 недели назад, # |

Felt like I'm giving a div 1 contest today

→ Ответить

Mathavaroopan

4 недели назад, # |

← 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

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

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

→ Ответить

_Unseen_

4 недели назад, # ^ |

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

→ Ответить

Parsa_Abolhassani

4 недели назад, # |

B made me feel empty.

→ Ответить

re.Think

4 недели назад, # |

← 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

4 недели назад, # |

← 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.

→ Ответить

4 недели назад, # ^ |

Agreed .

→ Ответить

ritzo38

4 недели назад, # ^ |

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

→ Ответить

swarbhatia

4 недели назад, # ^ |

Agreed, B destroyed me.

→ Ответить

EndMyMisery

4 недели назад, # |

I solved problem B with binary search.

→ Ответить

Mathavaroopan

4 недели назад, # ^ |

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

4 недели назад, # |

What is the solution of D1 ?

→ Ответить

SkibidiPilav

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

Thanks. Got it.

→ Ответить

Shoeib

4 недели назад, # |

+15

C is the worst dp problem i have ever seen

→ Ответить

999_ms

4 недели назад, # ^ |

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

→ Ответить

LordLouis04

4 недели назад, # |

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

→ Ответить

4 недели назад, # ^ |

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

4 недели назад, # ^ |

can you explain your proof?

→ Ответить

alpha1215

4 недели назад, # ^ |

There's nice proof by IceKnight1093
proof

→ Ответить

polsage

4 недели назад, # ^ |

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

→ Ответить

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

← 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.

→ Ответить

4 недели назад, # ^ |

READ AGAIN , what I have written.

→ Ответить

bruce_x001

4 недели назад, # ^ |

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

→ Ответить

swarbhatia

4 недели назад, # ^ |

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

→ Ответить

polsage

4 недели назад, # ^ |

Ohk got it thank you

→ Ответить

kir_tan22

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

→ Ответить

alpha1215

4 недели назад, # ^ |

link to comment

→ Ответить

34z12000

4 недели назад, # ^ |

+10

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

→ Ответить

aryanc403

4 недели назад, # ^ |

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

→ Ответить

SkibidiPilav

4 недели назад, # ^ |

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

4 недели назад, # ^ |

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

4 недели назад, # ^ |

← 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

4 недели назад, # ^ |

just binary search on the answer

→ Ответить

kovidsaivemuri

4 недели назад, # ^ |

-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

4 недели назад, # ^ |

← 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

4 недели назад, # |

Wrong Answer on pretest 2 for D2 :(

→ Ответить

programmer5777

4 недели назад, # |

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

→ Ответить

Cowdeforces

4 недели назад, # |

How to solve B???

→ Ответить

alpha_6124

4 недели назад, # ^ |

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

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

→ Ответить

navneetk12

4 недели назад, # |

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

4 недели назад, # |

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

→ Ответить

SkibidiPilav

4 недели назад, # ^ |

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

4 недели назад, # |

← 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

4 недели назад, # |

← 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

4 недели назад, # ^ |

+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

4 недели назад, # ^ |

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

4 недели назад, # |

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

→ Ответить

jeroenodb

4 недели назад, # |

+15

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

→ Ответить

_Unseen_

4 недели назад, # ^ |

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

4 недели назад, # ^ |

Can you explain your solution to D2?

→ Ответить

jeroenodb

4 недели назад, # ^ |

+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

4 недели назад, # ^ |

Thanks, implemented and got AC.

→ Ответить

Ioana

4 недели назад, # |

+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

4 недели назад, # ^ |

+10

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

→ Ответить

Ioana

4 недели назад, # ^ |

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

4 недели назад, # |

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

→ Ответить

detective...dots

4 недели назад, # |

← 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

4 недели назад, # ^ |

nice pfp

→ Ответить

Shoeib

4 недели назад, # |

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

→ Ответить

YipChip

4 недели назад, # ^ |

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

→ Ответить