harsh__h's blog

Codeforces Round #931 (Div. 2)
By harsh__h, 9 months ago, In English

Hello, Codeforces!

I invite you to participate in Codeforces Round 931 (Div. 2), which will be held on Mar/01/2024 17:35 (Moscow time).

The round will be rated for participants with rating lower than 2100. Participants with higher rating can participate in round unofficially.

You will have 2 hours to solve 5 problems, with one of the problems having 2 versions. One or more interactive problems may occur in the round, so please read guide for interactive problems before the contest.

All problems are authored by me.

I would like to thank:

Good luck to all participants!

UPD: Score distribution: 500 — 1000 — 1500 — (1500 — 1250) — 3250

UPD2: Editorial

UPD3: Congratulations to the winners!

Div1 + Div2

Place Participant
1 Um_nik
2 BurnedChicken
3 arvindf232
4 turmax
5 hitonanode

Div2

Place Participant
1 mlmlml
2 2018LZY
3 q1w2e3r4_1
4 shade34
5 damjandavkov
  • Vote: I like it
  • +206
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first comment of this contest! first day of spring season! first ... hmm what else? let's add something)

→ Reply
»
9 months ago, # |
  Vote: I like it +35 Vote: I do not like it

As a tester, problems are very interesting :)

→ Reply
»
9 months ago, # |
  Vote: I like it +27 Vote: I do not like it

As a tester, I can assure that you will enjoy the problems.

→ Reply
»
9 months ago, # |
  Vote: I like it +49 Vote: I do not like it

As a tester, I enjoyed testing this round a lot! :)

→ Reply
»
9 months ago, # |
← Rev. 8   Vote: I like it -17 Vote: I do not like it

.

→ Reply
»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

As a tester, I can ensure you that the problems are quite engaging. You will love solving them. Lots of learning on the way!!

→ Reply
»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hoping for the best Div.2 round!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

[deleted]

→ Reply
»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

First contest on the spring!

I hope the tasks will be as short and clear as the announcement of this contest!

Good Luck for EVERYone!

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

OMG purple round

→ Reply
»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Interactive problems? I don't even know how to solve them, does anyone has resource which I can refer

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot for authour and tester for very good and high quality of problemset(at least A,B and C)

→ Reply
»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

score distribution???

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sounds like a tough contest tho

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codforces Round 931 (Div. 2) i think there is mistake

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

IIT Guwahati orz <3

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

interforces

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope it's better than last round

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

aryanc403 testing back to back contests

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Back to back cf contests. I like it !

→ Reply
»
9 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a second time tester, this is definetely one of the top 2 rounds I ever tested.

→ Reply
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

jdurie tester orz

→ Reply
»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

jdurie :heart_eyes:

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Jdurie

→ Reply
»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hope C is not interactive :D

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Give us the score distribution,precious! (Read in Gollum's voice.)

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I want to become blue wish me luck

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

contest on the first day after 29th February. Let's see!

→ Reply
»
9 months ago, # |
  Vote: I like it +22 Vote: I do not like it

What happened to the chain of pictures of authors?

→ Reply
»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

hope no bitmasks(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bring it on, It's time for My Redemption.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

One and only author harsh__h :)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow. Two contest in a row and two positive delta.

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can I be a newbie tester for some future contest. I want try what it's like to be a tester.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's easy you just have to write that that were the best problems you've ever saw in your life in comments.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This problems were indeed the best problems I solved in my entire life. Especially the interactive problem, I just loved it

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can we hack others in interactive problems?

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In many of them, the author of the question was clarifying this. I hope it will be the case this time.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem setters pic where

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

with one of the problems having 2 versions One or more interactive problems XD XD

→ Reply
»
9 months ago, # |
  Vote: I like it +23 Vote: I do not like it

indian setter = mathforces

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

it was very enjoyable contest

→ Reply
»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Waiting for problem setters pics

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

There is just one author and people are asking him to post his selfie onto the announcement which will be shown on the home page lol. (no offense)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing maths problem (propply)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like recent Div 2 demotions in the current contest are considered “out of contest” even if their rating is 2100 by the start of the contest. Any reason why?

https://mirror.codeforces.com/contestRegistrants/1934/page/2?order=BY_RATING_DESC

→ Reply
»
9 months ago, # |
  Vote: I like it -42 Vote: I do not like it

whats wrong with last 2 rounds?

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

awful contest

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -33 Vote: I do not like it

Wtf, why C is interactive again? Is it so hard to make up NOT interactive problem for Div2?

→ Reply
»
9 months ago, # |
  Vote: I like it +69 Vote: I do not like it

No early screencast from Um_nik? :-(

→ Reply
»
9 months ago, # |
  Vote: I like it -32 Vote: I do not like it

can we stop with the interactive C please, welcome back pupil

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it

    i really like it personally, even though i couldn't solve it. You may never do interactive problems if you don't encounter it in a contest

    → Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

russian translation for D1 is a bit strange. In english text it says: "This is the solo version of the problem". But word 'solo' is also used in russian text "Это сольная версия задачи". At first I thought it was somehow 'salty' version of problem D (salty is used to describe contention, bitterness, anger, or an otherwise-foul attitude). I got confused for a second, I even changed the language of the text to doublecheck.

I think the better way to say it both in english and in russian was "This is non-interactive version of the problem" / "Это неинтерактивная версия задачи"

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Though I guess it would change the meaning — I suppose that by 'solo' the authors meant that unlike in D2, D1 IS NOT a two player game [as of game theory classification] (:

    → Reply
»
9 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Such a beatiful contest , I decided to give up just like my crush.

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

not able to solve problem B I should quit CP

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Author probably thought he was proposing these problems for a math Olympiad

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

see y'all in green :|

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Why is the limit on operations 63 in problem D when there is a solution with 2 operations?

→ Reply
»
9 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Problem C seems to essentially be a duplicate of a problem which I wrote in a previous DMOJ round, but with one fewer step.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -57 Vote: I do not like it

deleted

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why c is interactive

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me problem B

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, observe pair $$$10,15$$$. What can you say about it?

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i use 15 coins (n/15)

    then switch case 14 cases...(remain of divided by 15)

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's call the answer of this problem $$$f(n)$$$. I did some experiments and found that for almost all $$$n > 30$$$, $$$f(n) = f(n - 30) + 2$$$, but there seemed (only!) two exceptions: $$$f(35) = 3 \ne f(5) + 2$$$, and $$$f(38) = 4 \ne f(8) + 2$$$.

      So my solution was as follows: generate a table of $$$f(n)$$$ up to $$$n \le 60$$$ using DP, and for $$$n > 60$$$ calculate $$$f(n)$$$ using the above formula. I didn't prove, but the results of experiments seemed very promising.

      → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it in a partial DP sort of way. Calculate the least number of coins required for creating sum up until 30, beyond which the optimal way would be to first reduce the amount to below 30 by taking as many coins of 15 as possible and calculate the minimum for what's left.

    The main problem arises when you have 23/20 coins left, because if you blindly apply greedy you will get 15 + 6 + 1 + 1 and 15 + 3 + 1 + 1, when the optimal way is actually 10 + 10 + 3 and 10 + 10, respectively

    → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    What is the maximum times you can use any number? [1, 3, 6, 10, 15]

    Is there any point in using 3, 3, 3, 3? Or 1, 1, 1, 1, 1, 1? Or 10, 10, 10?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In some cases yes, just google unbounded knapsack it's a standard problem

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes I've solved unbounded knapsack problem but in this problem we had to minimize the number of coins so I thought its best to replace 3, 3 with 6 and so on.

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For small numbers all coins necessary. For huge only 15.

          For a math contest my solution is wrong, but that's how programmers do it, just precompute and forget

          → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no hack phase this time?

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Only in div. 3 and edu div. 2. You can still hack but you'd have to do it during the contest.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you do it during the contest?

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        1

        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        First, lock a problem using lock icon visible on dashboard. Then, click on the Room tab, where you can see coders who are in your room, you can only hack among these. The locked problems here should be visible in bold format. Click on the solution of any other coder for the same problem and hack it.

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing interactive problems; I don`t know how to start.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else get this annoying error for Problem C wrong output format Unexpected end of file — int32 expected (test case 2)?

Also, I technically never submitted a problem and passed test case 1, so is my participation unrated?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the problems were nice although I could only solve A , B

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

spent whole contest time for problem C

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    C was really cool problem

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah but, I'm terrible at geometry

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess its about pattern. SO if there is only ONE mine — you can request 1,1 and if dis is less then n, we will request (n-(n-dis), 1) cause it will be on diagonal of n, else (n-(dis-n),m) then we within 2 request we can find mine. But there are two mines, so we will spend two more request, cause one mine will be on diagonal and the second mine is tricky. Maybe I complicated the solution, but anyway you can check my code.

        → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A and B problems Screencast here: https://www.youtube.com/live/iSkTzLR84pQ?si=EbJ_9lnTspSnm6Pw

→ Reply
»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

D was easier than B.

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 6   Vote: I like it +21 Vote: I do not like it

    imo D2 < D1 < B < C lol

    though I must add that i think problem D2 was quite nice

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve D?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You just need to change x such that MSB of Y is set in X.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        For D2, the consider the parity of the numbers of '1's in the binary representation of $$$p$$$. (Hint: when played optimally, the current player wins if and only if there are an even number of '1's in the binary representation of $$$p$$$)

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

249172627 can anyone please tell me why Div2.C giving such error?

→ Reply
»
9 months ago, # |
  Vote: I like it +66 Vote: I do not like it

I know this is a skill issue on my part, but still — CF should really give a interactor / tester like GCJ used to. I presume me and many others just YOLO submit interactive problems without testing at this point since it is a pain to validate compared to normal problems.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use jdoodle for testing them, there's a separate switch to enable interactive input

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For simpler problems like C, I somehow manage to make a judge function in my local environment, but yeah for complex problems like D2 where the interactor needs to be smart, such thing would really save a lot of time.

    → Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

So bad...

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please say, why I'm getting rt here? 249171286

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are printing both (x1,y1) and (x2,y2) as answers

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, yeah, I was in a such rush that I didn't read the statement properly

      → Reply
»
9 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I had a terrible experience in this round as well as the previous, both C and D1 are true mind benders.

Signing up AB -- 15mins, wrong idea for C -- 15mins, trying D1 and getting 3 WAs -- 45mins, correct idea for C -- 25mins, work on D1 again -- 15mins

→ Reply
»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

C is a good problem but very painful to implement. Took so much of time for me.
Good round overall, thanks harsh__h and all testers!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What DO you Do in Interactive Problems???? Can someone pls explain
I followed the instructions but still getting Idleness Limit Exceeded
My Code

Thanks!

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to flush before taking input and after giving output, you're flushing after taking input.

    → Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

MathForces

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

-100 lets go

also what happened with my C

edit: lines intersect outside of boundary. Accepted now

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You only need to ask any three out of c1,c2,c3,c4 queries. (c1,c4) and (c2,c3) are complementary equations, so each mine satisfies exactly one of these equations. On solving the three equations, you get two solutions, exactly one of which is a mine. For the final query, you can ask the distance from either of these solutions. If the distance is zero, then it is a mine. Otherwise, the other solution is a mine.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. First find possible points from query(1,1) , query(1,n) , query(1,m). Atmost two points are possible from this.
    2. now find distance from one of the possible points . if you get response as zero then this pair is answer or other pair will be answer.
    → Reply
»
9 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Worst day ever

→ Reply
»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

A: Sort a[i] and the answer is a[n]+a[n-1]-a[1]-a[2].

B: We can believe that for some n0, we have dp[n]=dp[n-15]+1 for all n>=n0, and we can solve the problem by brute force for n<n0. (n0=300 can pass)

C: First query for (1, 1), let answer be d0, then there will be a mine on the line L0: x+y=2+d0. Then we query for the 2 endpoints of the intersection of L0 and the grid, let these points be A1,A2 and answer be d1,d2, then the circle (A1, d1) and (A2, d2) will have exactly 1 intersection with L0 in the grid, one of them will be the answer.

D1: If n is power of 2 we cannot do any operation. Otherwise, let r=floor(log2(n)). If 2**r<=m, then (m^n)<n, we can solve the problem in 1 operation. Otherwise, let t1=floor(log2(n-2**r)), t2=floor(log2(m)). If t2<t1, we can solve in 2 operation: n --> 2**r+m --> m. If t2==t1, we also have (m^n)<n and solve in 1 operation. If t2>t1, there's no solution.

D2: Let ppc(n) be the count of '1' in the binary representation of n. Then if ppc(n) is even, we always can do some operation to turn it into n1, n2 such that ppc(n1), ppc(n2) are odd. If ppc(n) is odd, for any n1, n2 such that (n1^n2)==n, one of ppc(n1) and ppc(n2) will be even. So If the initial ppc(n) is even we play first, otherwise we play second, and we can always let ppc(n) to be even on our turn. To win in 63 turns, we can let n1=2**r, n2=n-2**r, if the opponent choose n1 they will lose immediately, if they choose n2 the value of n will be halved.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    For B, is n0 = 30 the right minimum value for it?

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    For B I think that n0 = lcm(1,3,6,10,15) = 30 is the "optimal" choice

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B could be solved greedily. Grab 10 or 1 (based on the current n) until it is divided by 3, then grab 3, 6, 15 greedily for the rest. Submission

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Explain you approach. Also why you are keeping n>= 10 ?

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm not keeping n >= 10. If n < 10 then obviously I couldn't grab 10 coins.

        → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    249172491

    I think I did what you said, but it tle on test 1, could you help me with it please?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      			ll cosas = 1;
			ll p1 = 0;
			bool usar = true;
			for (ll i = 0; i < 63 and cosas > 0; i ++){
				if ((1LL << i) & n){
					p1 ^= (1LL << i);
					cosas --;
				}
			}

      In this section p1 will be the lowest bit of n. Try to let p1 be the highest bit of n.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh I see what can happen. Now it works, thanks!

        → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    May be I am wrong, but in problem D1 are you not using operation of type 2 ($$$x := x \oplus y$$$)?

    → Reply
»
9 months ago, # |
  Vote: I like it +40 Vote: I do not like it

I hate myself. Due to a series of stupid oversights I spent 35 minutes not seeing a single missing +1 in E, thinking that I verified all possible tests locally

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Yes, it's interesting

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you, author, for a great contest! Both problem B and C were really cool! C is one of the best problems I solved so far. Sad i didn't have enough time(

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I enjoyed thinking about problems D2 and E.

Thanks for the contest!

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Amazing contest and Again amazing problem C. I think every contest need an interactive Problem.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

What is the error in this code?

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define endl '\n'
#define PI 3.1415926535897932384626433832795l
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const double EPS = 1e-9;
void solve()
{
    int n, m;
    cin >> n >> m;
    cout << "? 1 1" << endl;
    cout.flush();
    int d1;
    cin >> d1;
    if (d1 == 0)
    {
        cout << "! 1 1" << endl;
        cout.flush();
        return;
    }
    cout << "? 1 " << m << endl;
    cout.flush();
    int d2;
    cin >> d2;
    if (d2 == 0)
    {
        cout << "! 1 " << m << endl;
        cout.flush();
        return;
    }
    cout << "? " << n << " " << 1 << endl;
    cout.flush();
    int d3;
    cin >> d3;
    if (d3 == 0)
    {
        cout << "! " << n << " 1" << endl;
        cout.flush();
        return;
    }

    int x1 = ((d1 + d2 - n) + 1) / 2;
    int y1 = d1 - x1;
    int x2 = ((d1 + d3 - m) + 1) / 2;
    int y2 = d1 - x2;
    if (x1 + 1 > 0 && y1 + 1 > 0)
    {
        cout << "? " << y1 + 1 << " " << x1 + 1 << endl;
        cout.flush();
        int d4;
        cin >> d4;
        if (d4 == 0)
        {
            cout << "! " << y1 + 1 << " " << x1 + 1 << endl;
        }
        else
        {
            cout << "! " << y2 + 1 << " " << x2 + 1 << endl;
        }
        cout.flush();
    }
    else
    {
        cout << "? " << y2 + 1 << " " << x2 + 1 << endl;
        cout.flush();
        int d4;
        cin >> d4;
        if (d4 == 0)
        {
            cout << "! " << y2 + 1 << " " << x2 + 1 << endl;
        }
        else
        {
            cout << "! " << y1 + 1 << " " << x1 + 1 << endl;
        }
        cout.flush();
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

The code seems correct for C question, please help me find bug

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You should either provide a link or use a spoiler, and you're not even telling us which problem. :(

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    int x1 = ((d1 + d2 - n) + 1) / 2;
int y1 = d1 - x1;
int x2 = ((d1 + d3 - m) + 1) / 2;
int y2 = d1 - x2;

    This might be where it is going wrong. You will need to check whether the two lines actually intersect or not by performing modulo 2, I made the same mistake in my first submission.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro sent the code as a spoiler or as a link

    → Reply
»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

B and C were very appropriate difficulty-wise. Good job.

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Amazing problems and huge thanks to the author! Problems involving binary representations have always been one of my most feared type, and D1 and D2 really teached me a lot!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interactive forces ftw

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting Idleness Limit Exceeded in this Code?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

fvck interactive

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem D1 I tried to derive what those operations mean.

Let number $$$n$$$ has at least $$$2$$$ digits $$$1$$$. Then we can take prefix of these digits $$$1$$$, and either change them all to $$$0$$$ and the last to $$$1$$$, or change them all to $$$1$$$ and the last to $$$0$$$. All digits after the chosen prefix can be changed to any other without restrictions.

1000100010101010101
|   |   |
0   0   1
 000 000 [anything]

But it turned out, that the intended solution is "we can see that..."

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yup, same (I actually got the solution with 2 operations for one case, but since there were 63 operations, I thought that there would probably be some "change bits one by one" sort of solution).

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are ratings decided based on (no of Problems solved + time taken to solve each problem — incorrect submissions) or is it based on ranking ??

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Fast system testing..

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B some people have pre-computed a string of length 30. How they are approaching that problem?

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    It can be proven that after n = 23 there is no combination where you shouldn't use 15 coins. So we always use 15 coins before we get to the 23 (or less) left, where we can brute force the correct combination.

    → Reply
»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Thank you, interactive problems made my purple handle gone.

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

After the contest, I realize that I only used 3 operations on problem C, and got choke till now.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B number problem is literally same as the famous coin change dp problem solution of which is also available throughout youtube and other sites. Then how come this problem is unique?People can just use the available code changing the coin denominations!

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can. But u'll get TLE.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Nope, the simple DP won't work, because the limit of $$$n$$$ is too large -- you can't create a table with $$$10^9$$$ elements. You need to find a way to calculate the answer for a large $$$n$$$, which is the core of this problem.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm learning basics of dp now like knapsack problems but still in the basic ones so do you recommend trying this problem to learn something helpful ?

      → Reply
»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

D1: 249146196 WA3

1<<j --> 1ll<<j

249177813 AC

Pain.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Compiling with -fsanitize=undefined can catch these types of overflow errors, just so you know

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong with this code for C?? 249143051

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why making a invalid query in c gave WA

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

rating updates ?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Troll

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why am I getting idleness limit exceeded? I have flush after every write, can this be due to my wrong approach? 249177547

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    sorry to say, but your code is not that clean. Writing clean code is important, as it can save time and make it easier for others to find and fix errors. In general, if your code is messy, people may not even bother to look at it.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for letting me know, I will try improving on this, any tips?

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        remove unusual functions and store them to somewhere else. use functions only when it's necessary. In addition, try to learn C++ properly. java isn't suitable for problem solving.

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Even though my rating is below 2100, I am somehow not included in the official standings

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a doubt during upsolving of problem B: Can anyone let me know, what is the difference in my 2 codes and why I get WA on 3 in 1st one and Accepted on 2nd, that feels so weird why dp fails in 1st one

249181823 : My Incorrect Submission

249181977 : My Correct Submission

Lookin forward for a positive response. Thanks <3

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First is not correct for cases like 15005 where you use 1000 15s, 3, 1, 1. Instead of 15,3,1,1 use 10,10.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Amazing C !! LOVE MATH. Thanks for this problem setter

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is your solution for c?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      If we set the the point (1,1) as fixed and ask(1,1) then we will get the nearest point to (1,1) now one of the following (1,m) or (n,1) must have the same near point no we have

      • d1 = ask(1,1)

      • d2 = ask(1,m)

      • d3 = ask(n,1)

      let (x,y) is the our point that can be obtained from d1,d2 now ask(x,y) if the result is zero then this is the point else we have to take (x,y) with respect to ask(1,1) , ask(n,1)

      How to obtain a possible (x,y) from two queries you can solve equation of two variables form any two of the following :

      • d1 = (x-1) + (y-1)

      • d2 = (x-1) + (m-y)

      • d3 = (n-x) + (y-1)

      You can have a look on my submission that also have some comments that may help you 249181821

      upvote if that helps you <3

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks

        Note that the third equation is not correct

        It should be d3 = (n-x) + (y-1)

        → Reply
»
9 months ago, # |
  Vote: I like it -7 Vote: I do not like it

i solved B with this code , does this count as brute force ?? ps : if i am not allowed to post solution here plz inform me and i will delete it 

def solve():
    n = inp()
 
    coins = [1, 3, 6, 10, 15]
    ans = float('inf')
 
    def dfs(num, index, curr):
        nonlocal ans
        if num == 0:
            ans = min(ans, curr)
            return
        if index == 0:
            ans = min(ans, curr + num)
            return
 
        c = coins[index]
        for i in range(index):
            k = num // c
            dfs(num - (c * k), i, curr + k)
            if k > 1:
                dfs(num - (c * (k - 1)), i, curr + (k - 1))
 
    for j in range(len(coins)):
        dfs(n, j, 0)
    return ans
→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't exactly know how your solution works, but I think it's really cool because it works in the time limit and it doesn't involve hard-coding some magic values...

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice solution. Can you please explain how you did this?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      it pretty much generates 'all the possibilities' and takes the minimum of those possiblities, it even calculates the possibility when the number of coins is max lol,

      for the base cases :

      • if num == 0 that means the the sum of coins we have is equal to original n and the number of those coins is (curr) so with we take that curr if it's inferior to our current minimum (ans)
      • if index = 1 that means we are at coin = 1 so we take what left of original n and add it to the current number of coins than update the ans if it's inferior

      the loop inside the dfs function will call dfs recursively with what's left of n after taking the max possible number of coins with current coin (c) k = num //c add that number to the current number of coins we have (curr+k) and pass that number and what's left of n to coins with value inferior than the current coin, so for example at 3: we will pass the same (what's left of n and curr+k) to coin 1, at 6 we will pass them to 3 and 1 at 10 we will pass them to 6,3,1 and we will calculate until we reach the base case , and update the minimum for the second dfs call inside the loop dfs(num — (c * (k — 1)), i, curr + (k — 1)) it takes care of the possibility where i can replace 1 coin of 15 with x coins , of any coins with value inferior to it and if such possibility provides an inferior curr it will be updated in the ans, like the case for number 98 **it better to take 98 = 15 * 5 + 10 * 2 + 3 * 1 = 8 coins , than 98 = 15 * 6 + 6 * 1 + 1 * 2* = 9 coins

      The outside loop that calls the dfs 

      for j in range(len(coins)):
        dfs(n, j, 0)

      is for the possibility when the original n is directly divisible by any coin , like the case of 20 , if i don't call dfs in a loop and call it only on 15 or index= 4 in my case it will return 20 = 15*1 + 3 * 1 + 1* 2 = 4 coins, because if i call it only on 15 the 20 will never reach coin = 10 untouched , it will reach coin = 10 with the value 5 = 20 — 15, so i need to also call dfs with 10 as the starting coin,and the original n as the starting value in this case it will return 20 = 10 * 2 = 2 coins and as i said in the start the algorithm will take the minimum of all those possibilities and return it

      Sorry if my explanation is unclear , if you have any other questions regarding the solution i will try to answer it

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For addressing Problem B, let's denote the solution as f(n). Through empirical observation, it appears that for nearly all n greater than 30, f(n) follows the recurrence relation f(n) = f(n-30) + 2. However, there are two notable exceptions: f(35) = 3, which doesn't align with f(5) + 2, and f(38) = 4, contradicting f(8) + 2.

To tackle this, I adopted the following strategy: I constructed a DP table to compute f(n) for n up to 60. For values exceeding 60, I employed the aforementioned recurrence relation. While I haven't formally proven this approach, extensive experimentation suggests its efficacy.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Through empirical observation, $$$cnt(1)<3$$$ because otherwise we can change the surplus $$$1$$$'s into $$$3$$$.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a complain. I have solve Question B & C of today's contest was succesfully run in pretests, but after the contest it's showing runtime error. & submitting the same code after this problem it is succesfully accepted. Please Check, or tell me how it's happened.

C: During Contest & after contest

B: During Contest & after contest

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Welcome to the land of undefined behavior

    In problem B when i = 30, you are accessing sieve[30] but your vector size is exactly 30 (should be > 30)

    In problem C you didn't delete the code from problem B and the same thing happens

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      shittt. I got it,but why there is no runtime error in test 1, it should come at the earliest testcase only. & Please tell why the same code is successfully submitted after the contest.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        The thing about undefined behavior is your code will become completely unpredictable

        You can try submitting that same code for some more times and see that it might get different verdicts for different submissions of the same code

        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 4   Vote: I like it +1 Vote: I do not like it

        You can read more about undefined behavior here: https://en.cppreference.com/w/cpp/language/ub

        (I know that it's kinda weird that C++ doesn't immediately throw a rte on invalid array accessing, but I guess it's just a quirk of C++ that you have to deal with...)

        Also as a side note, vector has a .at() method and it is guaranteed to perform bound checking (It will throw an exception in case of invalid accesing), so you might want to use it instead of the normal [] operator

        → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

how to report cheating ? have a look.. exact same code.

249197369

[249112538](https://mirror.codeforces.com/contest/1934/submission/249112538 edit : bro I'm new. Why so many down votes :(

→ Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

when will the rating change happen?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B can be solved greedily 249152430

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's my first comment in pupil, Thanks for an amazing contest <3

→ Reply
»
9 months ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

I was unrated even though I was purple when joining… Could someone please look into this issue? It would’ve been my best perf by far :(

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

To much interactive questions, that's not great

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was the name for problem A chosen as a reference to the solution? Taking the two min and two max?

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, after sorting, you can choose i = 0, j = n-1, k = 1, l = n-2, so you can get maximum value.The answer is 2·(a[j]+a[l]-a[i]-a[k])

    → Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

LoL, this round was a rated for me, even though my rating was >= 2100

2024-03-02-091013

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The round was unrated for me even though my rating was < 2100.

    → Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Feedback on the problems:

  • A: A typical easy problem, but I don't think it's interesting — just boring casework. There must be an origin if need to choose 3 elements.

  • B: I don't know why the authors set $$$1,3,6,10,15$$$, still boring.

  • C: Good problem. Maybe it's not a good choice to place an interactive problem on D2C. Many participants are familiar with it.

  • D1: Normal problem imo. It's easy to get a $$$2$$$-step solution by doing some case work, do the authors set $$$k\le 63$$$ in order to mislead?

  • D2: Nice problem. The parity is traditional in games, and combine it with popcount is cool. Also the example is strong enough to check some mistakes. (I got 10 WAs on pretest 1 because of not using long long)

  • E: Not read.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
void solve()
{
	int n, m;
	cin >> n >> m;

	cout << "? " << 1 << " " << 1 << endl;
	int d1;
	cin >> d1;

	int bx = min(n, d1 + 1), by = max(1LL, d1 - n + 2);
	int ty = min(m, d1 + 1), tx = max(1LL, d1 - m + 2);

	cout << "? " << bx << " " << by << endl;
	int d2; cin >> d2;

	cout << "? " << tx << " " << ty << endl;
	int d3; cin >> d3;

	pair<int, int> ans1, ans2;
	ans1 = {bx - d2, by + d2};
	ans2 = {tx + d3, ty - d3};

	cout << "? " << ans1.ff << " " << ans1.ss << endl;
	int d4; cin >> d4;

	if (d4 == 0)
	{
		cout << "! " << ans1.ff << " " << ans1.ss << endl;
	}
	else
	{
		cout << "! " << ans2.ff << " " << ans2.ss << endl;
	}
}

Can someone help me to find out why it is WA?

Step 1 - Query (1, 1), we got a diagonal of cells where one mine can be present.
Step 2 - Query endpoints of the diagonal.
Step 3 - Form 2 new set of points and one of them must be an answer.
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The best Div!!!!!

→ Reply
»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why C skip? I am afraid of hack, so I make my code long. Submission

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    T_T

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, it is strictly forbidden to use __asm__. In this case, we cannot tell whether the code is copied.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe your code coped anyone

    → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Code obfuscation isn't allowed, you aren't allowed to intentionally make your code harder tl understand to avoid hacks

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first solve interactive questions in Codeforces!!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for the best Div.2 round!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Became Pupil, Thanks for the contest!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I enjoyed testing this round a lot! :)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@harsh__h why my code get skipped? mine whole code is written by me why plag then?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what should i do if my code was similar to some others users? System already skipped this...i am sorry for that

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my code get skipped? i think this was a similar approch. I request an appeal from Codeforces Sir MikeMirzayanov to review one more time of my code...

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's very interesting contest).

→ Reply