BENQ ROUND ORZ

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

← Rev. 2 →

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

→ Ответить

sarvagya2545

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

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

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

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

→ Ответить

professor_kumar

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

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

→ Ответить

rgnerdplayer

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

← Rev. 2 →

+15

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

→ Ответить

vitorfariaa

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

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

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

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

→ Ответить

vitorfariaa

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

yea yea

→ Ответить

m_nature

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

← 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

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

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

→ Ответить

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

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

→ Ответить

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

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

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

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

→ Ответить

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

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

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

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

→ Ответить

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

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;

→ Ответить

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

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

→ Ответить

Peter-007

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

Me too

→ Ответить

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

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

xD.

→ Ответить

TheScrasse

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

Me too :D

→ Ответить

123gjweq2

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

← Rev. 2 →

Can you please tell us which one chatGPT made?

→ Ответить

misaki646

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

Too weak for C again... GG

→ Ответить

qwerlty123

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

How to solve D?

→ Ответить

https://codeforces.me/contest/2035/submission/288353463

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

← 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

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

-7

ObservationForces

→ Ответить

maxrgby

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

+16

That is what CF is supposed to be, yes.

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

polosatic

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

+30

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

→ Ответить

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

Thanks a lot, waiting !!!!

→ Ответить

lrvideckis

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

← Rev. 2 →

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

→ Ответить

polosatic

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

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

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

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

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

What does Authorized by ChatGPT means

→ Ответить

counterstrike2

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

how to solve C?

→ Ответить

Saivishwas

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

find patterns in sample testcases

→ Ответить

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

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

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

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

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

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

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

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

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

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

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

← 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

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

nice problem D need 2 more minutes to submit :(

→ Ответить

pikino

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

+14

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

→ Ответить

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

→ Ответить

zfnu

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

+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

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

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

→ Ответить

123gjweq2

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

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

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

i hate overflow :(

→ Ответить

i3mr125

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

← 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

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

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

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

Can anyone Share Idea of problem C ?

→ Ответить

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

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

→ Ответить

misaki646

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

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

→ Ответить

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

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

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

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

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

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

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

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

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

How to solve D?

→ Ответить

alpha1215

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

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.

→ Ответить

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

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

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

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.

→ Ответить

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

You've to wait until system testing ends.

→ Ответить

devess

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

thanks for reply. how long will it take?

→ Ответить

meowmeow_

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

← Rev. 2 →

Editorial?

→ Ответить

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

← Rev. 2 →

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

→ Ответить

meowmeow_

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

there are cases where they immediately publish an editorial

→ Ответить

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

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

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

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

→ Ответить

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

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

→ Ответить

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

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

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

+19

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

→ Ответить

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

+23

hints for F?

→ Ответить

gmusya

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

minimize something => binary search

→ Ответить

avighnakc

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

Why are global rounds always so hard :sob:

→ Ответить

Yugandhar_Master

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

Because they are global rounds :)

→ Ответить

nicksms

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

← Rev. 3 →

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

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

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

→ Ответить

Into_Your_Arms

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

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

→ Ответить

hos.lyric

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

+48

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

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

+10

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

→ Ответить

nivedkml

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

← Rev. 2 →

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

→ Ответить

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

← Rev. 2 →

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

→ Ответить

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

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

→ Ответить

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

Same mentioned here.

→ Ответить

djm03178

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

← 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

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

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

→ Ответить

bashkort

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

+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

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

hope to have rate soon

→ Ответить

Bojji

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

← 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

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

Nevermind, overlooked something in the question.

→ Ответить

Astroflexx

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

How to solve D?

→ Ответить

maxrgby

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

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

→ Ответить

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

← 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

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

+24

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

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

+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

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

+15

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

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

ty bro <3

→ Ответить

bahailu

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

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__

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

← 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

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

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

→ Ответить

prem__

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

I don't exactly know in which steps you are applying mod, but if you apply mod and then some comparisons on some value on which mod is already applied then you should expect wrong results.

Or else, maybe your solution which gives TLE is also wrong, just that it gives tle before detecting wrong answer in the test cases (maybe). Is there any test case which passes the TLE solution but gives wrong answer verdict on your other solution.

→ Ответить

bahailu

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

Without applying mod on the count TLE on test 3

Applying mod on the count Wrong answer on test 2

so, If i'm not applying mod it works, but it gives TLE because of applying arthimetic on large number. when I apply the mod it gives wrong answer.

→ Ответить

AreebZahoori

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

so i realised i was applying modulo correctly but missed the 2s > 30 thing where u dont (2 ^ 2s) with the odd number, how exactly does it help in getting the correct result?

→ Ответить

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

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__

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

← 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

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

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

→ Ответить

AreebZahoori

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

hm using the log seems beneficial since no issue of overflow and mod can be used when decrementing/incrementing the sum

→ Ответить

Lushaojie

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

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

→ Ответить

orz

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

+42

orz

→ Ответить

-is-this-BIT-

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

+11

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

→ Ответить