BENQ ROUND ORZ

15 часов назад, # ^ |

← Rev. 2 →

Note that $$$33\cdot10^n$$$ is divisible by $$$66$$$.

→ Ответить

sarvagya2545

15 часов назад, # ^ |

I dont think we need the divisibility properties of 11. We can only use 3 and 6 as digits, and the number is to be divisible by 66, so the number must end with 66.

Then you need to add 33 * pow(10, x) always, and you cannot have 9 as a digit in the resultant number. So, by logic we have answer ->

for n >= 4: concat(333333....(n — 2)times, 66) when n is even and concat(33333...(n — 4)times, 6366) when n is odd.

Then you can handle cases for n < 4.

→ Ответить

JulSjlv

15 часов назад, # ^ |

Neither did I. Fun part: If you divided the solutions in the tests by 11 you'd get something very interesting.

→ Ответить

professor_kumar

15 часов назад, # ^ |

when I looked on "n = 500", I started observing the testcases on the screen and I got it it only about 3s.

→ Ответить

rgnerdplayer

15 часов назад, # ^ |

← Rev. 2 →

+15

Sample just gives the answer. You can also just dp with the remainder, no need of any math.

→ Ответить

vitorfariaa

15 часов назад, # |

god D made me so pissed, I was only getting the last number from the last test wrong i changed all the MODS, reviewed all of them and still wrong

→ Ответить

arihant_j

15 часов назад, # ^ |

u must be using mod somewhere where u shouldn't be using it

→ Ответить

vitorfariaa

15 часов назад, # ^ |

yea yea

→ Ответить

m_nature

15 часов назад, # ^ |

← Rev. 2 →

Nah, I can assure you it is not that easy. Most probably, your algorithm doesn't even work on case #2 in the sample. Just check it.

→ Ответить

vitorfariaa

15 часов назад, # ^ |

well I think my answer had some consistency I accumulated the distance from every number from the very least significative Bit to the first Bit, and thats the number of times I could multiply a number by 2. Then I right shifted all the numbers the amount of times they could be shifted, and for every query, I get the preffix sum of all shifted numbers + the max shifted numbers left shifted the amount of times I accumulated b4

→ Ответить

15 часов назад, # |

rip in piece i got unlucky on D (first try AC but i way overcomplicated it)

→ Ответить

15 часов назад, # ^ |

Can you verify if this approach is ok I maintain a 2 stacks one with the value and one with the potential

the value is essentially the number that remains after we remove all the 2 from it if the last number is greater the the value of the stack we maintain we remove that and add it's potential to the potential of the current number ,and subtract (last_elem-1) * (2^its_potential) to the ans and at the end we add curr_elem * (2^curr_potentail) to the ans and stack

cache the 2 ^ power into and array

I spent 1 hour + on this still wa on tc 2

→ Ответить

DuongForeverAlone

15 часов назад, # ^ |

There's a case when the power of $$$2$$$ is too big, you need to handle correctly.

→ Ответить

15 часов назад, # ^ |

I think I did that

I initialized a big array with powers of 2 and applied mod on it

Have to see what that elusive test case is tho!

→ Ответить

DuongForeverAlone

15 часов назад, # ^ |

← Rev. 4 →

Maybe the way you use modulo. Take a look at the line 48. When you subtract, you need to add it to modulo instead of just using % operator.

→ Ответить

15 часов назад, # ^ |

Just checked my submission , You are right

while multiplting I naively assumed that it will stay in limit but it did not

I did c += (b*d) => overflow occured

instead of c += (b*d)%1000000007;

→ Ответить

15 часов назад, # |

I feel so dumb, Forever stuck on D, Need to improve on my debugging and analysing skills

→ Ответить

Peter-007

15 часов назад, # ^ |

Me too

→ Ответить

15 часов назад, # ^ |

Quite expected when, Peter opts to be Bond instead of being Parker.

xD.

→ Ответить

TheScrasse

15 часов назад, # ^ |

Me too :D

→ Ответить

123gjweq2

15 часов назад, # |

← Rev. 2 →

Can you please tell us which one chatGPT made?

→ Ответить

misaki646

15 часов назад, # |

Too weak for C again... GG

→ Ответить

qwerlty123

15 часов назад, # |

How to solve D?

→ Ответить

https://mirror.codeforces.com/contest/2035/submission/288353463

15 часов назад, # ^ |

← Rev. 2 →

I used monotonic decreasing Stack, which stores Odd values and powers Of 2.

You can refer to my submission. I have tried using as much as verbose variable names. In case you still have doubts, you can ask me.

→ Ответить

Md_Minhaj

15 часов назад, # |

-7

ObservationForces

→ Ответить

maxrgby

14 часов назад, # ^ |

+16

That is what CF is supposed to be, yes.

→ Ответить

15 часов назад, # |

+16

Most of the CM / Experts(including me) tried a lot to pass (bruteforce + ternarySearch) to pass pretests for problem E.

E has some sort of

This pattern for 3rd test case


current cost 6001
 current cost 3002
 current cost 2043
 current cost 1504
 current cost 1205
 current cost 1026
 current cost 907
 current cost 788
 current cost 729
 current cost 610
 current cost 611
 current cost 552
 current cost 493
 current cost 494
 current cost 435
 current cost 436
 current cost 437
 current cost 378
 current cost 379
 current cost 380
 current cost 381
 current cost 382
 current cost 383
 current cost 324
 current cost 325
 current cost 326
 current cost 327
 current cost 328
 current cost 329
 current cost 330
 current cost 331
 current cost 332
 current cost 333
 current cost 334
 current cost 335
 current cost 336
 current cost 337
 current cost 338
 current cost 339
 current cost 280
 current cost 281
 current cost 282
 current cost 283
 current cost 284
 current cost 285
 current cost 286
 current cost 287
 current cost 288
 current cost 289
 current cost 290
 current cost 411
 current cost 412
 current cost 413
 current cost 414
 current cost 415
 current cost 416
 current cost 417
 current cost 418
 current cost 419
 current cost 420
 current cost 421
 current cost 422
 current cost 423
 current cost 424
 current cost 425
 current cost 426
 current cost 427
 current cost 428
 current cost 429
 current cost 430
 current cost 431
 current cost 432
 current cost 433
 current cost 434
 current cost 435
 current cost 436
 current cost 437
 current cost 438
 current cost 439
 current cost 440
 current cost 441
 current cost 442
 current cost 443
 current cost 444
 current cost 445
 current cost 446
 current cost 507
 current cost 508
 current cost 509
 current cost 510
 current cost 511

There are multiple local minimums. How to find the optimal local minimum ?

→ Ответить

15 часов назад, # ^ |

Use sqrt-decomposition. You can refer to 1954E - Chain Reaction

→ Ответить

15 часов назад, # ^ |

← Rev. 2 →

ohhh, Understood. So for each square-root, block, we need to apply ternary search. Is that right ?

( haven't looked at your solution, Want to solve on my own. Will check your solution, if I can't solve it ).

Thanks for the hint !

→ Ответить

15 часов назад, # ^ |

← Rev. 2 →

you dont "find" the local minimum, you bruteforce!

let A be a chain of k operation 1s and 1 operation 2 (in that order)

optimal answer would be A repeated some amount of times -> op1 some amt (must be <= k) -> op2 some amt

brute force through number of A repeats -> sqrt(z/k)

if k is small (k <= 1e4) -> number of op1s is bruteforceable -> sqrt(z/k)*k = sqrt(zk) but k <= 1e4 so at worst it's 1e6 per case

if k is large then the number of op2s so that number of op1s is >1e4 is also small (i wasnt able to exactly calculate the amt but it should run fast enough)

→ Ответить

15 часов назад, # ^ |

Okay, I tried something similar, but couldn't pass.

→ Ответить

15 часов назад, # ^ |

prob some bad implementation (or youre missing some optimizations) cause mine ran in ~200ms

→ Ответить

polosatic

15 часов назад, # ^ |

+23

Check my 288346163. I used ternary-300 optimization to pass it. I will write a blog about it soon.

→ Ответить

15 часов назад, # ^ |

Thanks a lot, waiting !!!!

→ Ответить

lrvideckis

14 часов назад, # ^ |

← Rev. 2 →

Is this guaranteed to find the global min? It looks heuristical

→ Ответить

polosatic

5 часов назад, # ^ |

Of course it is heuristical. If it wasn't, we could find global minimum of a random function. It works because the function is close to unimodal.

→ Ответить

lrvideckis

3 часа назад, # ^ |

got it. I'm wondering if there's a condition where it will provably find it.

like maybe if f(x) is almost unimodal and there exists some unimodal function g(x) s.t. abs(f(x)-g(x)) < C then it'll find it

→ Ответить

b65524804

15 часов назад, # |

What does Authorized by ChatGPT means

→ Ответить

counterstrike2

15 часов назад, # |

how to solve C?

→ Ответить

Saivishwas

15 часов назад, # ^ |

find patterns in sample testcases

→ Ответить

15 часов назад, # ^ |

Well, I didn't find any pattern. I did simple maths. you only care about last 3 to 5 values last values

If N % 2 == 1, you care about only last 4 values.
If N % 2 == 0 and N is power of 2, you can about only last 5 values.
Otherwise, you care about last 3 values.

→ Ответить

SkibidiPilav

15 часов назад, # ^ |

if odd then obviously the max you can get is just n, and if not odd, then you can set all bits that are present in the permutation, by doing the same thing as with n-1, but just adding result^(n-1) at the en

→ Ответить

darsh1098

15 часов назад, # ^ |

so for odd I just have to print 2 1 3 4 5 6 7 8.. but what for even?? tbh I got destroyed by this C :( too tough for me

→ Ответить

SkibidiPilav

15 часов назад, # ^ |

You print whatever at the beggining and at the end print 1 3 n-2 n-1 (res^n-1). where res is the highest set bit in n times 2 — 1

→ Ответить

darsh1098

15 часов назад, # ^ |

ahh okay I upsolved it with little different approach that if n is a power of 2 or n is odd then max answer we can get is n and so I printed it like 2 1 and then 3,4,.. else i took the highest power close to n which is less than it call it x I printed 2 1 3 4 till x-2 and then from reverse I printed n to x-1

→ Ответить

knoothopian

14 часов назад, # ^ |

← Rev. 2 →

For even $$$n$$$, the intuition is as follows,

First of all you can show $$$k$$$ can always be $$$2^{\lfloor\log_2 n \rfloor+1} - 1$$$ if $$$n \geq 4$$$ and we are given $$$5 \leq n$$$

Now for explanation, consider n = 10. Let $$$p_n = 2^{\lfloor\log_2 n\rfloor} = 8 = 1000$$$.

We know $$$k = 15 = 1111$$$, so there must be an $$$x_n$$$ such that $$$8 | x_n = 1111$$$. So, $$$x_n=0111$$$ (not $$$1111$$$ as that does not exist in this permutation).

Now, we want $$$p_{n-1} \land x_{n-1} = 0111$$$, thus $$$p_{n-1} = 0111 = 7$$$. Now we can fix $$$p_{n-2} = 6 = 0110$$$ and $$$p_{n-3} = 1 = 0001$$$ as we can observe their OR gives us $$$p_{n-1}$$$.

Finally we just need to ensure that $$$x_{n-3}$$$ is odd so $$$p_{n-3} \land x_{n-3} \neq 0$$$. This we can do by letting all even indices from 1 to $$$n - 4$$$ be odd and odd indices from 1 to $$$n - 4$$$ be even. Thus at each OR step, we would be ORing with an odd number. Since $$$n$$$ is even $$$n-3$$$ is odd. So if we are ORing at $$$n$$$-th step, we are ANDing at $$$n-3$$$th step. But $$$n-4$$$-th step would have an odd number as per our construction so $$$x_{n-3}$$$ would be odd!

Final permutation looks like this: $$$\text{odd}_1,\ \text{even}_2,\ \ldots \ \text{odd}_{n-4},\ 1,\ n-2,\ n-1,\ n$$$

Here

→ Ответить

alpha1215

15 часов назад, # |

nice problem D need 2 more minutes to submit :(

→ Ответить

pikino

15 часов назад, # |

+14

In problem D, "Since this problem is too easy" killed me.

→ Ответить

15 часов назад, # ^ |

→ Ответить

zfnu

15 часов назад, # |

+17

If there's no elegant solution for B and C then they are not good, since it's casework for odd\even basically. D and E on the other hand are great, thank you.

→ Ответить

FrostBytee

15 часов назад, # ^ |

I thought there must be some proof and did not see the standings assuming it was hard, i fcdkup :)

→ Ответить

123gjweq2

15 часов назад, # ^ |

To be fair, C really just boils down to solving for $$$2 \cdot \lfloor \frac{n}{2} \rfloor$$$ so idk if it is fair to call it casework.

→ Ответить

hg3141

15 часов назад, # |

i hate overflow :(

→ Ответить

i3mr125

15 часов назад, # |

← Rev. 3 →

For C, I just got the pattern for $$$n > 4$$$. if $$$n$$$ is odd, a permutation of $$$[2, 1, 3, 4, 5, \dots, n]$$$ always gives the max answer which is $$$n$$$. For even the maximum answer will be $$$2^{p+1}-1$$$, where $$$p$$$ is just the number of the leftmost bit, and it's still the same pattern but $$$2^p-1$$$ should be the last number. but if $$$n$$$ is a power of $$$2$$$ it should be the last number after the $$$2^p-1$$$. I want proof of this.

→ Ответить

equeen

15 часов назад, # |

I solved C by guessing but got stuck on both D and E. I enjoyed the contest though, D is a great problem in my opinion. I think I was missing the case where it was a situation like [4, 4, 11, 2, 3], and the max array would be [1, 1, 176, 1, 6], not [1, 1, 176, 2, 3].

→ Ответить

Prakash_OP

15 часов назад, # |

Can anyone Share Idea of problem C ?

→ Ответить

15 часов назад, # ^ |

Try to get $$$2^{k}-1$$$ for even numbers.

→ Ответить

misaki646

15 часов назад, # ^ |

how to get the permutation that fits 2^k -1?

→ Ответить

15 часов назад, # ^ |

If $$$2^{k-1}<n<2^{k}$$$, the array ends with $$$[2^{k-1}-1, (2^{k-1}-1)\,\text{XOR} \,\text{lowbit}(n),n]$$$. The $$$\text{lowbit}$$$ is to ensure that $$$n$$$ can fill the zero bit that the previous item of $$$n$$$ causes.
If $$$n=2^k$$$, the array ends with $$$[1,3,n-2,n-1,n]$$$. $$$1$$$ is to fill the last bit that $$$n-2$$$ lacks
If $$$n$$$ is odd, note that $$$a\,\text{AND}\,b\le a$$$, so $$$n$$$ itself is the maximum and you can just put $$$n$$$ after your even array to reach the maximum.

→ Ответить

misaki646

15 часов назад, # ^ |

Thanks, I got the even/odd observation. But miss the [1,3,n-2,n-1] could be a thing... I was desperate to code a dfs and pray that I have enough luck but I guess I don't

→ Ответить

sarodesparsh

15 часов назад, # ^ |

It's always possible. There is always a number m < n such that n|m gives all ones in binary so last but one should be that m which is actually odd. So its now reduced to odd case from here except for edge cases for numbers less than 5

→ Ответить

anirudhc69

15 часов назад, # |

Why I found D easier than C :(

IDK why it was happening while doing C my brain not Braining I was not able to focus on the pattern.

Damnnn any ideas ?

→ Ответить

SkibidiPilav

15 часов назад, # ^ |

How to solve D?

→ Ответить

alpha1215

15 часов назад, # ^ |

i did dp till index i such that total power of 2s <= 32 and then do greedy aferwards
can't submit during contest, but let see if that's correct or (hopefully) atleast the idea is correct.

→ Ответить

15 часов назад, # ^ |

For large enough ($$$\geq 8$$$ works) even $$$n$$$, you can just end the permutation with $$${1, 3, maxpow-2, maxpow-1, n}$$$, where $$$maxpow$$$ is the greatest power of $$$2$$$ that's $$$\leq n$$$, which ends up with having all bits that are set in at least one number $$$\leq n$$$ on, so the answer is $$$2*maxpow-1$$$. A greater answer is clearly impossible. And for large enough odd $$$n$$$ ($$$\geq 8$$$ still works), you may note that the result is bounded by the last element of the permutation, and therefore by $$$n$$$. And the result $$$n$$$ is achievable by putting $$$n$$$ at the end of the optimal permutation for $$$n-1$$$. Cases where $$$n<8$$$ can be hardcoded.

→ Ответить

devess

15 часов назад, # |

I am not able to solve the problems after the contest. I am getting "You can't run practice now or contest does not support practice" error.

→ Ответить

15 часов назад, # ^ |

You've to wait until system testing ends.

→ Ответить

devess

15 часов назад, # ^ |

thanks for reply. how long will it take?

→ Ответить

meowmeow_

15 часов назад, # |

← Rev. 2 →

Editorial?

→ Ответить

15 часов назад, # ^ |

← Rev. 2 →

Contest ended $$$20$$$ minutes ago. The editorial isn't usually published that early. I'm sure it will eventually appear.

→ Ответить

meowmeow_

15 часов назад, # ^ |

there are cases where they immediately publish an editorial

→ Ответить

15 часов назад, # ^ |

There are. Not very often, and there are also cases where the editorial is published $$$3$$$ hours after the contest. I think out of the $$$12$$$ contests I participated in, editorial was published immediately twice or something like that.

→ Ответить

PaarthJuneja

15 часов назад, # ^ |

the fact that you almost once reached master within just 12 contests is WILDDDD, username checks out

→ Ответить

15 часов назад, # ^ |

I think he is an ALT user. If not then Mad Respect. ORZ.

→ Ответить

14 часов назад, # ^ |

I'm not an alt user, but I started with competitive programming (olympiads and stuff) about $$$2$$$ years before joining Codeforces, and I've been doing math olympiads even longer (which also helps).

→ Ответить

PaciukZvichainyi

15 часов назад, # |

+19

During this contest my mental health dropped to a new record.

→ Ответить

15 часов назад, # |

+15

hints for F?

→ Ответить

gmusya

15 часов назад, # ^ |

minimize something => binary search

→ Ответить

avighnakc

15 часов назад, # |

Why are global rounds always so hard :sob:

→ Ответить

Yugandhar_Master

15 часов назад, # ^ |

Because they are global rounds :)

→ Ответить

nicksms

15 часов назад, # |

← Rev. 3 →

Weak systests on E, incorrect "sqrt" decomp (~2e7 ops/tc worst case) passes in 500ms:

https://mirror.codeforces.com/contest/2035/hacks/1094322 (uphack of my own sol)

Didn't think to pick my parameter correctly. Didn't matter.

→ Ответить

Into_Your_Arms

12 часов назад, # ^ |

Even my C $$$maybe$$$ hackable.. for even $$$N$$$.

→ Ответить

hos.lyric

15 часов назад, # |

+38

I like the essential observation part of problem G, nice! However reading a binary search using closed interval ($$$[l, h]$$$ instead of $$$[l, h)$$$) was painful, please go learn X(

→ Ответить

willy108

14 часов назад, # ^ |

I agree wholeheartedly with $$$[l, h]$$$ being painful.

→ Ответить

nivedkml

15 часов назад, # |

← Rev. 2 →

Pressed submit and timer ended 1 second before. Tried submitting after system testing. It was AC. :(

→ Ответить

15 часов назад, # ^ |

← Rev. 2 →

next time u will get ... fosho ! just don't give up.

→ Ответить

15 часов назад, # |

Why is the amount of wrong submissions for E more than $$$11$$$ times the amount of correct submissions, what was going on

→ Ответить

15 часов назад, # ^ |

Same mentioned here.

→ Ответить

djm03178

15 часов назад, # ^ |

← Rev. 2 →

Me who submitted it 15 times: I first ran into a wrong idea that a single ternary search would work. It turned out that it doesn't work because it can have multiple local minimums. It was too late for me to carefully think of a right approach, so instead I could only try to add some extra ranges to search and hope that they are enough. None of them could pass pretests.

→ Ответить

alexpril39

15 часов назад, # |

bruh, the round was sweaty to be fair. Anyway ,returned ,my expert after a disasterous div2 yestersay.

→ Ответить

bashkort

15 часов назад, # |

+51

Loved the contest, thank you! G is cool, F is nice, D is nice, E is OK, and B&C are also OK.

Missed the trivial "remove every test" case in G1 :(

→ Ответить

thembululquaUwU

15 часов назад, # |

hope to have rate soon

→ Ответить

Bojji

15 часов назад, # |

← Rev. 2 →

whats wrong with this approach on D? I couldn't even match the sample test cases on this one :(.

Thanks in advance.

→ Ответить

Bojji

14 часов назад, # ^ |

Nevermind, overlooked something in the question.

→ Ответить

Astroflexx

15 часов назад, # |

How to solve D?

→ Ответить

maxrgby

15 часов назад, # |

My final code was edit distance 2 away from AC-ing E...:(

→ Ответить

15 часов назад, # |

← Rev. 2 →

Hint to D:

Let us pick $$$a_i$$$ and $$$a_j$$$ and decompose $$$a_i$$$ into $$$a_i=p_i\cdot2^{q_i}$$$ where $$$p_i$$$ is odd and $$$q_i>0$$$. Performing the operation on $$$a_i$$$ and $$$a_j$$$ is optimal if and only if $$$p_i<a_j$$$.

→ Ответить

KiKoS

14 часов назад, # |

+21

Liked C a lot:

Solve for evens through solve for odds, always a cool trick. I used $$$solve(2n) = [\ldots, solve(2^{\lfloor\log(2n)\rfloor} - 1), 2n]$$$.
A lot of ways to solve for odds: I used $$$[\ldots, 3, 1, n - 1, n]$$$ as $$$(n & (n - 1)) = n - 1$$$ for odd numbers and $$$1 & 3 = 1$$$ that we can push to the ans as well.
$$$n \ge 5$$$ is a good constraint. I hadn't to manually if cases.

Maybe a bit harder than a regular D2C, but definitely solvable (and in many approaches, whats not always a case). It's generally hard to create a good problem for position C and today it was just awesome.

→ Ответить

Hori

14 часов назад, # ^ |

+32

Interestingly enough the answer for lower $$$n$$$ is just the identity permutation. I still decided to remove it so people didn't get confused by edge cases.

→ Ответить

tyristik

14 часов назад, # ^ |

Bad decision, you should've done everything in reverse: made $$$n \geq 1$$$, made $$$1$$$ multitest in examples with $$$n=1,\ 2,\ 3,\ 4$$$ and printing identity permutations as answers for them. Doing so we would see a lot of noobies sending solutions with just printing identity permutations xD xD xD

→ Ответить

alfoos

13 часов назад, # ^ |

ty bro <3

→ Ответить

bahailu

14 часов назад, # |

For problem D, I didn't understand how to use the modulo. When I apply it to intermediate results, it gives me the wrong answer. If I only use it at the end, I get a TLE. I believe the numbers are getting too large. Any help?

Spoiler

import sys

def solve():
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    result = [0] * n

    mod = 10**9 + 7

    pq = []
    sum_ = a[0]
    result[0] = a[0]

    if a[0] % 2 == 0:
        heapq.heappush(pq, a[0])

    for i in range(1, n):
        while pq:
            current = heapq.heappop(pq)
            temp = current

            count = 1
            while current % 2 == 0:
                count = (2 * count)
                current //= 2

            old_sum = (temp + a[i])
            new_sum = (current + (count * a[i]))

            if new_sum >= old_sum:
                sum_ -= (temp - current)
                a[i] = (count * a[i])
            else:
                heapq.heappush(pq, temp)
                break

        if a[i] % 2 == 0:
            heapq.heappush(pq, a[i])

        sum_ = (sum_ + a[i])
        result[i] = sum_ % mod

    print(*result)



if __name__ == "__main__":
     for _ in range(int(input())):
        solve()

→ Ответить

prem__

14 часов назад, # ^ |

← Rev. 2 →

In my correct submission, I apply it while calculating answer for each index but I store numbers num = x * 2^y as (x, y) , where x is an odd number (Edit: clearly here x and y will always lie in int range as per constraints in the problem). And while comparing I use log2 of the num which is log2(x) + y, which gives correct comparison.

→ Ответить

bahailu

28 минут назад, # ^ |

Thank you for the explanation. but, still I didn't get why applying the modulo for every intermediate result cause a wrong answer!

→ Ответить

14 часов назад, # ^ |

Numbers quite large. So, instead of doing the multiplication, you just need to store the oddNumber, and powerOfTwo everytime you process the value. This will help in managing integer overflows ( although, in python u won't get any ).

→ Ответить

prem__

14 часов назад, # |

← Rev. 3 →

+10

In problem D of this round, it has missing test cases. One missing test case that I found, which potentially could give rejected verdict on some submission:

1
3
999999986 2097152 1048576

My last submission 288365525 during contest gives correct answer for it, but my earlier submission during contest gives wrong answer. But still when I resubmitted my earlier submission 288377619 after the contest ended to check if it passes system tests, unfortunately it passed!!

Explanation of mistake in earlier submission:

My approach for above given test case:
given n = 3, and array a = {999999986 2097152 1048576} = {499999993 * 2^1, 1 * 2^21, 1 * 2^20}

for i = 1: f[a1] = a1 (obviously)

for i = 2: f[a1, a2] I first check if I can transfer power of 2 from earlier indices which have power of 2 and increase the total sum.
I check it as if last_element_having_factor_2/(power_of_2_in_it) <= current_element, then transfer the power.
Since, transferring power from a1 to a2, will reduce the total sum, so I don't do it here.
So, f[a1, a2] = (999999986 + 2097152)%1000000007;

for i = 3: f[a1, a2, a3]
last previous index which has power of 2 is a2 which is 1 * 2^21 and since 1 <= current_a3 (1 * 2^20), so I transfer the power from a2 to a3, then a3 becomes 1 * 2^41.
then last element which has power of 2 is a1 which is 499999993 * 2^1 and here is where there is silly mistake in my older submission which still passes the system test cases.
In my correct solution I check if log2(499999993) <= log2(1) + 41 , but in older submission I checked if 499999993 <= 1 * (2^41 % 1000000007), which gives wrong answer as it does satisfy the condition to transfer the power, but it should.
So, correct answer = (499999993 + 1 + 2^42)%1000000007 .
But my other submission (which passes the system tests) gives answer = (999999986 + 1 + 2^41)%1000000007 .

This modular arithmetic mistake could have been done by few (or maybe many) other users also. So Hori, would the test cases be updated and since many others might have done same mistake, would the solutions for problem D be rejudged for the contest or the updated test cases be used for further submissions only. Or test cases won't get updated as contest is over.

Edit: My flawed submission has been uphacked. I didn't know someone can uphack even after contest ends and hacking phase ends.

→ Ответить

dark111

12 часов назад, # ^ |

← Rev. 3 →

That's a valid test case that should be in the contest. Problem setters and/or testers should have added such test cases. Nonetheless, they should add it now.

There can be many such test cases, like
1
3
999999998 2097152 1048576

and many more, but unfortunately official test cases didn't have any of them.

→ Ответить

Lushaojie

13 часов назад, # |

I don't think D is a good question about mod.

→ Ответить

orz

13 часов назад, # |

+34

orz

→ Ответить

-is-this-BIT-

10 часов назад, # |

Too many cheaters again today on D, submission blew up too much in the last one hour

→ Ответить