Codeforces Round 949 (Div. 2)

6 месяцев назад, # |

+17

Silly Question which I can't resist to ask:

→ Ответить

Abito

6 месяцев назад, # ^ |

+45

Usually the reason is either that the contest is based on an olympiad or some other contest, so to avoid leaking problems the codeforces contest is set in an unusual time. The other reason is simply that this is the best time that fits the authors due to time zone difference or other reasons

→ Ответить

6 месяцев назад, # ^ |

+119

Yes, thanks for your understanding. Actually there is a conflict between this round and ours studying plan (we are from the same school). At the same time zltzlt and I are preparing for the Zhongkao, one of the most important exams in our life, so hope participants can understand us.

→ Ответить

Abito

6 месяцев назад, # ^ |

+47

Good luck on your exams!

→ Ответить

larush

6 месяцев назад, # ^ |

+37

I've heard that Zhongkao is very prestigious, just as Gaokao is. I wish you the best of luck, and I hope that you perform really well.

→ Ответить

yeminghan

6 месяцев назад, # ^ |

+38

Good luck & high mark in Zhongkao!

→ Ответить

6 месяцев назад, # ^ |

+48

Good luck for you too!

→ Ответить

liympanda

6 месяцев назад, # ^ |

-8

To my knowledge, both of you are good enough in competition and can be Baosong(enter without exam) to a very good high school. You don't need to do Zhongkao.

→ Ответить

6 месяцев назад, # ^ |

Actually due to the policy, we are still required to get at least 680/810 in the exam, and the school ask as to get a score of 730+. It's not that easy, is it?

→ Ответить

JWRuixi

6 месяцев назад, # ^ |

Can we stop saying "Zhongkao" and actually speak some English? This is really a bit embarrasing /qd

→ Ответить

NaOH_Frog

6 месяцев назад, # ^ |

+15

Zhongkao is shorter than 'ahrghaghrah entrance exam' and everyone knows what it means so it's not an issue

→ Ответить

6 месяцев назад, # ^ |

+36

Thanks!

→ Ответить

6 месяцев назад, # ^ |

OKay. Thanks a lot for quenching my Curiosity.

→ Ответить

x1f0cb32d3_

6 месяцев назад, # ^ |

How exactly would an unusual round time prevent leaking problems?

→ Ответить

NapSaq

6 месяцев назад, # ^ |

That's for mirror rounds, rounds that replicate an actual on-site contest.

→ Ответить

luanmenglei

6 месяцев назад, # ^ |

As far as I know, it is because Guangdong provincial team training. The author of this round is a member of Guangdong provincial team.

→ Ответить

6 месяцев назад, # ^ |

Okay Thanks a lot for replying. May I ask, How long does the training lasts and how do Chinese coders train?

→ Ответить

luanmenglei

6 месяцев назад, # ^ |

Sorry, I don't know cause i'm not in Guangdong.

→ Ответить

hzy_mod

6 месяцев назад, # ^ |

Two weeks.

→ Ответить

GrievousPiggy

6 месяцев назад, # |

+21

It will be my first contest in Codeforces, and I am looking forward to it!

→ Ответить

6 месяцев назад, # |

+42

As a first-time tester and one of the writers, I'm certain that you will have a good experience in this round and learn a lot. Just enjoy yourself:)

→ Ответить

starrykiller

6 месяцев назад, # |

+36

As a tester, hope you can enjoy the problems and get a positive rating $$$\Delta$$$!

Meanwhile, good luck to the authors who are about to attend an important examination -- Zhongkao!

→ Ответить

rui_er

6 месяцев назад, # |

+71

As a tester, I like the problem set and hope you enjoy it too!

→ Ответить

deified

6 месяцев назад, # |

Still waiting for the Educational Round blog

→ Ответить

Avik_AB17

6 месяцев назад, # |

+12

Codeforces Round 949! One step closer to the milestone Round 950! <3

→ Ответить

bettercallwael

6 месяцев назад, # |

-9

please change the time of the contest it is in the time of the pray in Egypt and we want to participate

→ Ответить

AdhamElsaady

6 месяцев назад, # |

Please delegate it one more hour, Many muslim guys in the middle east won't be able to join because of the prayer of jumaa.

→ Ответить

Norp

6 месяцев назад, # |

HOPE IN THIS ROUND I'D REACH MY GOAL BEFORE SUMMER BEGUN

GL FOR EVERY PERSON,WHO READING THIS COMMENT

→ Ответить

Mindeveloped

6 месяцев назад, # |

+11

As a Chinese CPer, I'm happy with the start time.

→ Ответить

trp_hy

6 месяцев назад, # ^ |

Don't you have any class?

→ Ответить

Mindeveloped

6 месяцев назад, # ^ |

We leave school at 5:30 p.m.

→ Ответить

YuJiahe

6 месяцев назад, # |

← Rev. 2 →

+17

As a tester, I would like to say that the problems are wonderful!

→ Ответить

wsc2008qwq

6 месяцев назад, # |

+50

As a tester, I'm zltzlt fan.

→ Ответить

zltzlt

6 месяцев назад, # ^ |

+54

As a writer, I'm wsc2008qwq fan.

→ Ответить

Wasif_Shahzad

6 месяцев назад, # |

looking forward to give this round as a cyan :)

→ Ответить

sinsop90

6 месяцев назад, # |

← Rev. 2 →

+38

As a writer, I am a fan of zltzlt.

→ Ответить

Jryno1

6 месяцев назад, # ^ |

As a tester, I am a fan of zltzlt. Good luck in Zhongkao!

→ Ответить

wangmarui

6 месяцев назад, # |

Hope the competition topic is more interesting！

→ Ответить

Bekbolot_Ubaidullaev

6 месяцев назад, # |

-20

→ Ответить

lovely-ckj

6 месяцев назад, # |

As a tester, I think this round will be educational and fun.

I think all the problems are great.

→ Ответить

6 месяцев назад, # |

OMG Finally 18:05 round

→ Ответить

anikdasad808

6 месяцев назад, # |

will be good contest

→ Ответить

mohamedeltair

6 месяцев назад, # |

← Rev. 4 →

It would be great if you can delay it by 1 hour, as many middle east contestants will miss it due to a weekly prayer at that time.

→ Ответить

6 месяцев назад, # |

Arithmetic Progression in scoring distribution!!!

→ Ответить

yeminghan

6 месяцев назад, # ^ |

+14

No because $$$3500-2500\ne2500-2000$$$ :)

→ Ответить

6 месяцев назад, # ^ |

Ohhoo, I missed the last one. But, suiitable for the first five. Thank you.

→ Ответить

deified

6 месяцев назад, # |

Giving the round to compensate the loss in educational

→ Ответить

6 месяцев назад, # |

+120

Fun fact: the setter has solved 4000+ problems on codeforces and 10k+ problems on a Chinese online judge(which provide the remote judge service of codeforces and atcoder). I'm so shocked by his hard work.

→ Ответить

AkiLotus

6 месяцев назад, # ^ |

I'm curious, how long did he take for the 10k milestone locally? Heck, this is making my 2.5k in ~2 years fall obsolete by a long shot, such a dedication.

→ Ответить

zltzlt

6 месяцев назад, # |

Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).

→ Ответить

al-ghoul

6 месяцев назад, # |

If I don't solve A B and C then it's gg

→ Ответить

al-ghoul

6 месяцев назад, # ^ |

Update: I couldn't even do B its over for me

→ Ответить

Red0

6 месяцев назад, # |

As a PST kid, I somehow managed to wake up for it :)

→ Ответить

WSD33

6 месяцев назад, # |

Wish positive delta in this round!

→ Ответить

SAD_IN_NIGHTMARE

6 месяцев назад, # |

+19

Will queue issues appear in contest because of EDU 166 system testing?

→ Ответить

DonSilvio

6 месяцев назад, # |

← Rev. 2 →

+19

Will there be delays due to an overlap with yesterday's Educational round's System Testing?

→ Ответить

01iveria

6 месяцев назад, # |

Wish ABC！

→ Ответить

Jie-XuSheng

6 месяцев назад, # |

orz zltzlt

→ Ответить

AvaraKedavra

6 месяцев назад, # |

Tough contest.

→ Ответить

arnavwinner

6 месяцев назад, # |

This didn't seem like a Div. 2.

→ Ответить

MKasirloo

6 месяцев назад, # |

+25

It was more like Div. 1.5

→ Ответить

NqkSyte

6 месяцев назад, # |

Any smart solution for C? Feels like another boring implementation task that I can't care less debugging. Took a huge L today.

→ Ответить

The-Winner

6 месяцев назад, # ^ |

263463935

→ Ответить

ThePeak

6 месяцев назад, # ^ |

Can you please explain your intuition and solution ?

→ Ответить

The-Winner

6 месяцев назад, # ^ |

If there are no set values, just do 1 2 repeated.

If there is some value set then the prefix can be obtained from the first value by halfing. If you get to 1 you double because you cannot half. The suffix is similar.

Now to complete middle parts. Say we are bounded by $$$a$$$ and $$$b$$$. If $$$a > b$$$ then we must half $$$a$$$ in order to get closer to $$$b$$$. If we don't then $$$a$$$ was half of its right neighbour, but that only increases the distance to $$$b$$$ and we still will have to half at some point. We reduced the problem to a smaller instance (from $$$\frac a 2$$$ to $$$b$$$ and one less element). Similarly you can do the same if $$$b > a$$$. There is one issue, if both $$$a$$$ and $$$b$$$ are 1, then this does not work but you can just insert a 2 instead.

In the end you want to check the original problem constraints (you did not get an invalid array). This can be computed as you complete the array.

→ Ответить

Adityaxv

6 месяцев назад, # |

Mathforces

→ Ответить

diobrando97

6 месяцев назад, # |

+33

What the fuck of the C???????????

→ Ответить

123hope

6 месяцев назад, # ^ |

← Rev. 2 →

I used more than an hour to write the code(182 lines) for C,but still didn't AC

→ Ответить

tickbird

6 месяцев назад, # ^ |

isn't that simply find n sequence {a1,a2,...,an} start from x to y where a0 = x, a_{n+1} = y, a[i] = a[i + 1] / 2 or a[i] = a[i — 1] / 2?

→ Ответить

diobrando97

6 месяцев назад, # ^ |

yeah, very easy to get the idea, but it just brabra casework and very hard to debug.

→ Ответить

bgopc

6 месяцев назад, # ^ |

not needed that much of case handling. assume the array has this form: [-1, -1, ..., x, -1, -1, -1, ..., y, -1, -1, ...]

The prefix and suffix are kinda the same, start by doing x/2 until you reach 1 then do 2 1 2 1 2 1, In the middle part, start x/2 and y/2 from left and right, divide the bigger one in half each time, once you reach the other side just double check the OKity

→ Ответить

x1f0cb32d3_

6 месяцев назад, # ^ |

I literally missed a case in C and threw like 30 minutes finding the cause of the WA, leaving 5 minutes for D which I figured out a few minutes after the round ended ._.

→ Ответить

bs_commander

6 месяцев назад, # ^ |

I feel like I code a large number of droppings :(

→ Ответить

BananaBrain

6 месяцев назад, # |

How to do prob B ?????

→ Ответить

Adnanboii

6 месяцев назад, # ^ |

← Rev. 3 →

Go through the bits of n, let's say you're at bit x, if the bit is a 0 then check if m >= 2^x — (the number represented by the binary expression before bit x) or if x is not greater than the most significant bit of n then you can also check if m >= (the number represented by the binary expression before bit x).

263459449

→ Ответить

akashtadwai

6 месяцев назад, # ^ |

As the operation spreads for every second, at time $$$t=m$$$, the value at $$$a_i$$$ will be $$$a_i = a_{i-m}|a_{i-m+1}|...|a_{i+m}$$$.
The above is exactly the bit-wise OR in the range $$$[max(0,n-m), n+m)]$$$.

→ Ответить

shviv1

6 месяцев назад, # |

-6

loved problem B.

→ Ответить

DangerMouse

6 месяцев назад, # ^ |

Can you explain how you did?

→ Ответить

shviv1

6 месяцев назад, # ^ |

yeah, just notice by writing the operation a couple of times let say 20 and 3 are values of n and m then in the first operation value will be (19|20|21) and in the second operation the value will be (18|19|20)|(19|20|21)|(20|21|22) --> which is nothing but or of [18,22], so if u write more such iteration u can conclude that the answer is OR of range(max(0,n-m),n+m).

→ Ответить

DangerMouse

6 месяцев назад, # ^ |

I reached uptil this that answer will be bitwise OR from range(max(0,n-m),n+m) but was not able to implement it, was this an easy implementation? because if it was an easy one i would work on my bitwise section

→ Ответить

DangerMouse

6 месяцев назад, # ^ |

Or am i missing something? does just doing output OR of range(max(0,n-m),n+m) will not give the answer

→ Ответить

Neko1i3

6 месяцев назад, # ^ |

It will give the correct answer, but not always in the time limit. To actually solve this problem you need to consider every bit individually and try to greedily find a number that has this bit set and lies in the range [max(0,n-m),n+m].

→ Ответить

6 месяцев назад, # ^ |

You can check out my submission. I also did the same observation as shviv1.

Here is my submission

→ Ответить

pkhaustov

6 месяцев назад, # |

-6

Pure math + wrong difficulty estimation from coordinators. Typical Codeforces.

→ Ответить

master_bait_41

6 месяцев назад, # |

the authors cooked

→ Ответить

lovely_cyc

6 месяцев назад, # |

+10

C is not a C. D is not a D.

I think CDEF should be DEFG, and insert an easier C.

→ Ответить

Mindeveloped

6 месяцев назад, # |

I hate it when a math problem (problem D) appears in my interesting interval

(the problem is nothing wrong tho, just I'm too skill issued)

→ Ответить

harshbksp98

6 месяцев назад, # |

Problem B seemed tougher as compared to normal div2B problem ...

→ Ответить

HliasBoss

6 месяцев назад, # |

+20

Tough contest. We weren't given enough time.

→ Ответить

deadnecro18

6 месяцев назад, # |

What is wrong in this? 263494295. If someone can provide a testcase, it would be very helpful.

→ Ответить

https://mirror.codeforces.com/contest/1981/submission/263485331

6 месяцев назад, # |

Brother, only the time was not unusual; To me, problem 'B' was also unusual, aaand the whole contest was unusual too!!!

→ Ответить

iceycola

6 месяцев назад, # |

← Rev. 5 →

my method for C

assume L is somewhere a[i]!=-1 ,R is next one that a[i]!=-1

then when a[L]>a[R] we can make a[L+1]=a[L]/2

when a[L]<=a[R] we can make a[R-1]=a[R]/2

if a[L]==a[R]==1 we can make a[L+1]=2

my english is so bad so dont critisize me

this is my code and i know it is ugly

→ Ответить

yeminghan

6 месяцев назад, # |

← Rev. 2 →

+36

Stucked on C for $$$45$$$ minutes and finally got 1 place lower than sevlll777, who solved 1 problem less than me. The slowest episode ever.

→ Ответить

__NO__NAME__

6 месяцев назад, # |

agony

→ Ответить

wangyishan

6 месяцев назад, # |

Who can give me C's solution?

I did it for 1h30mins,but i have no ideas.

→ Ответить

1e3bonzakura

6 месяцев назад, # ^ |

You can do 3 ops when moving from $$$i$$$ to $$$i+1$$$, namely divide by 2 (and floor), or multiply by 2, or multiply by 2 and add 1. It is easy to see that in enough steps, any number can be achieved with these operations. You compute the minimum operations, and if the distance is less than that, or the distance minus the minimum operations is odd, then it's impossible. The implementation is a bit tricky though...

→ Ответить

wangyishan

6 месяцев назад, # ^ |

Thanks for you comment. in the competition,i thought of this trick but i dont know how to calc the minnium distance lol.

→ Ответить

Tanjiro_Nezuko

6 месяцев назад, # |

Can anyone please help me find error in my solution for problem B ? It's failing on pretest 7. https://mirror.codeforces.com/contest/1981/submission/263482380

→ Ответить

Tanjiro_Nezuko

6 месяцев назад, # ^ |

Nevermind I got my mistake.

→ Ответить

TrendBattles

6 месяцев назад, # |

+22

I'm officially having skill issue with constructive problems (again) :D

→ Ответить

bibimoni

6 месяцев назад, # ^ |

+15

same

→ Ответить

244mhq

6 месяцев назад, # ^ |

Same

→ Ответить

Savior-of-Cross

6 месяцев назад, # |

how to F

→ Ответить

6 месяцев назад, # |

a B-like A a C-like B a D-like C and a C-like D Bruh...

→ Ответить

6 месяцев назад, # ^ |

+14

BitForces (

→ Ответить

britishcat

6 месяцев назад, # |

I actually enjoyed solving problem C a lot. but aren't the rounds a little too hard? there was literally only one full solve which came from a person probably above div.2 level. still, cool problems

→ Ответить

jmyszka

6 месяцев назад, # ^ |

britishcat now an expert!

Orz

→ Ответить

adepteXiao

6 месяцев назад, # |

+50

It wasn't fun at all

→ Ответить

diobrando97

6 месяцев назад, # ^ |

I couldn't agree more with this comment.

→ Ответить

dogshit

6 месяцев назад, # |

Will the rating changes of this round be calculated on the ratings before the EDU or on the updated ratings of the EDU?

→ Ответить

DuongForeverAlone

6 месяцев назад, # |

+13

Adhoc dominates codeforces nowadays a lot.

→ Ответить

Aldijohn

6 месяцев назад, # |

Can someone tell me how to solve A? I know it must be easy, but I couldn't come up with a solution.

→ Ответить

master_bait_41

6 месяцев назад, # ^ |

p=2 works and hence, the largest power of 2 <= r is the answer

→ Ответить

Aldijohn

6 месяцев назад, # ^ |

Oops! That was easy! I somehow made it in my mind to be much more complicated. Thank you!

→ Ответить

Omiya_Shinobu

6 месяцев назад, # |

Abnormal contest with CNOI-style problems.

→ Ответить

ChenWenxin2009

6 месяцев назад, # |

Problem C did give me a lesson...

→ Ответить

RidhamPatel

6 месяцев назад, # |

In contest i tried second question for 1 hour and 54 minutes still not able to solve it :(

→ Ответить

MeZoxx7

6 месяцев назад, # |

not only not enough time but the problems were harder than usual div 2 problems

→ Ответить

6 месяцев назад, # |

← Rev. 2 →

+37

I love the $$$O(\frac{n^2}{\ln n})$$$ solution of problem F, however I spent my whole time in $$$O(n\log n)$$$ overcomplicated segment tree merging solution and mixed indices like tr[x<<1](should be tr[tr[x].ls]) then finally finished 10 minutes after the contest...

edit: I got the first blood!! so funny XD

→ Ответить

tyr0Whiz

6 месяцев назад, # ^ |

can you elaborate the idea?

→ Ответить

6 месяцев назад, # ^ |

Basically we have $$$x\not\in A\Rightarrow\text{mex}(A)\le x$$$. Then we can apply DP: $$$f_{x,y}$$$ is the minimum cost in subtree $$$x$$$ such that $$$y$$$ doesn't appear in the top path, then segtree merging.

→ Ответить

tyr0Whiz

6 месяцев назад, # ^ |

I had similar thought, but wouldn't it be N^2 though

→ Ответить

6 месяцев назад, # ^ |

you can check the different between my two submissions. In the first RE one I use array $$$g$$$ to maintain, and it was replaced by segment tree in the second one.

→ Ответить

Fork512Hz

6 месяцев назад, # |

← Rev. 4 →

I think it will be more balanced to insert a *1500 problem between B and C.

Difficulty prediction (luogu): Orange Yellow Green Blue Blue (Black)

Difficulty prediction (Codeforces): 900 1400 1700 2200 2400 (3200)

→ Ответить

6 месяцев назад, # |

After the Educational round I thought, "I am going to get a healthy positive delta". The rating is not updated yet. But after this unusual 949 round I am scared of being Pupil again!!!

→ Ответить

Fork512Hz

6 месяцев назад, # |

Wait. maspy FSTed on problem F???

A 0-solve D2F??

→ Ответить

https://mirror.codeforces.com/contest/1981/submission/263488201

6 месяцев назад, # ^ |

yes bro

→ Ответить

smit_384

6 месяцев назад, # |

got RE on test case 2 of problem c and got accepted after contest. if just had 1 minute more whould get ac

Spoiler

→ Ответить

_akasi

6 месяцев назад, # |

← Rev. 2 →

a very nice D!! Thanks for the contest.

→ Ответить

Mo3tassem_229

6 месяцев назад, # |

how can calculate rate and educational rate not calculated yet??

→ Ответить

Day_Tao

6 месяцев назад, # |

But I really didn't have fun ...

I think it is too hard for a Div.2 contest.

→ Ответить

ChenWenxin2009

6 месяцев назад, # ^ |

Day_Tao is so bright,/bx Day_Tao.

→ Ответить

pranshul_047

6 месяцев назад, # |

← Rev. 2 →

Hi, can someone tell me where my submission for B is going wrong?

I converted the decimal numbers (n-1) and (n+m) to binary, and then traversed (from MSB to LSB) and compared their bits. Where ever they differ, that means from that bit onwards all the bits will be 1

→ Ответить

1e3bonzakura

6 месяцев назад, # ^ |

The left should be $$$l=max(n-m,0)$$$, not $$$n-1$$$. Also, Bitwise operations in C

→ Ответить

krishna_08

6 месяцев назад, # |

Am I the only one who felt A is tough than usual div 2 rounds

→ Ответить

6 месяцев назад, # ^ |

← Rev. 2 →

wdym it's literally int l, r; cin >> l >> r; cout << (int)log2(r) << endl;

→ Ответить

krishna_08

6 месяцев назад, # ^ |

I got that idea after some time but initially I some how thought that we have to calculate the x in between l and r with maximum factors.I have to carefully read the question next time

→ Ответить

puspendra_09

6 месяцев назад, # ^ |

small code does not generally mean the problem is easy.

→ Ответить

6 месяцев назад, # ^ |

Het can you tell me why this method leads to wrong answer sometimes as i got in this question Atcoder Question

→ Ответить

6 месяцев назад, # ^ |

#include <bits/stdc++.h>

using namespace std;

int main() {
  int h;
  cin >> h;
  
  cout << 1 + (int)log2(h+1) << endl;  
}

This code resulted in AC

→ Ответить

6 месяцев назад, # ^ |

Also, here is AtCoder Test Cases (Dropbox Link). You can check them if you try a problem for a significant amount of time and still can't figure out your mistake :)

→ Ответить

6 месяцев назад, # ^ |

Damn I didn't know they provide Tc's to

→ Ответить

RatingIsNotJustANumber

6 месяцев назад, # |

CornerCaseForces

→ Ответить

iLLuSiOnZ

6 месяцев назад, # |

+14

BitForces

→ Ответить

6 месяцев назад, # |

Carrot is not working :( Any other working performance calculator extensions?

→ Ответить

CLANCY--

6 месяцев назад, # ^ |

Sometimes Codeforces close the API during contests due to the heavy load, it doesn't work because it can't get the data to 'predict',

give it some time and it'll be working fine.

→ Ответить

Fork512Hz

6 месяцев назад, # ^ |

It might be Cloudflare's protection mechanic instead of Codeforces'. I can see an error message containing 403 and !DOCTYPE html followed by some are you a human webpage content

→ Ответить

chayankumawat2004

6 месяцев назад, # |

← Rev. 2 →

Chineseforces

→ Ответить

kjhhjki

6 месяцев назад, # |

+15

It might be better to swap the D and E.

→ Ответить

FrostLeaf

6 месяцев назад, # ^ |

+12

very correct

→ Ответить

6 месяцев назад, # ^ |

I think C>D=E(((

→ Ответить

emam_hasan_himu

6 месяцев назад, # |

I hope someday I will be congratulated like this.

→ Ответить

NULLgorithm

6 месяцев назад, # |

+37

There are 10 types of people: 1. Those who like bit manipulation. 2. Those who don’t like it.

→ Ответить

al-ghoul

6 месяцев назад, # ^ |

bro that's 2 not 10 man

→ Ответить

accord

6 месяцев назад, # ^ |

+42

Clearly, you are the second type of person.

→ Ответить

master_bait_41

6 месяцев назад, # ^ |

deep within, most of us belong to type 2 only

→ Ответить

Avik_AB17

6 месяцев назад, # ^ |

← Rev. 2 →

10 in binary is indeed 2

→ Ответить

senguptasushruta

6 месяцев назад, # |

Can anyone explain the approach of C

→ Ответить

6 месяцев назад, # ^ |

← Rev. 3 →

We can make the problem simpler ...

=> Given a and b in 'a -1 -1 -1 ...(k times) b', is it possible to fill the -1s with numbers >=1 and <=1e8 such that adjacent elements follow either A[i+1] = A[i]/2 or A[i] = A[i+1]/2 ?

Let's approach to solve it from both ends (now, from the left). Say A[i] = a and A[j] = b, so A[i+1] can be a/2 on division side (call it OP1) or 2a or 2a+1 on multiplication side (call it OP2). So we store the number of such operations in respective maps for both OP1 and OP2 till j-i number of operations.

Similarly, from the right-hand side. Since the hops between a and b are j-i for any common number x on map_OP1 or map_OP2, we have (say) t = map_OP1_left[x] + map_OP1_right[x] as the total number of hops. If (j-i) and t have different parity, it is not possible for such x to be a convergence point (obvious), so if they have the same parity and t > (j-i), one could just make x from a and b and fill between even hops by *2 and /2 alternatively. You can fill '-1 -1 -1 ... a' and 'b ... -1 -1 -1' ones similarly.

That's the approach and here's my submission 263482841.

→ Ответить

gateway_1916

6 месяцев назад, # |

When will the ratings get updated any idea ??

→ Ответить

ab2112

6 месяцев назад, # ^ |

yeah, its pretty late

→ Ответить

bussy_slayer

6 месяцев назад, # |

Author cooked

→ Ответить

RockStars

6 месяцев назад, # |

a contest where no one completes all the questions But it is useful

→ Ответить

ShivamJNU

6 месяцев назад, # |

Can anyone please explain why my following approach for the problem B fails:

My Approach

→ Ответить

6 месяцев назад, # ^ |

I cant tell what but you were trying to do something like this 263477911

→ Ответить

6 месяцев назад, # ^ |

Your approach is 100% correct, and this is my AC submission which is the same tbh 263460829

→ Ответить

ShivamJNU

6 месяцев назад, # ^ |

Finding the smallest number greater than 'n' whose ith bit is set is easier. But can you please explain the approach to find the greatest number smaller than 'n' whose ith bit is set, because the number may or may not exist?

→ Ответить

6 месяцев назад, # ^ |

← Rev. 2 →

So we traverse from i+1th bit towards MSB, and the moment we find a 1, say at bit j, unset bit j and set all bits from j-1 till 0, call this number x. That is the closest number on its left with the ith bit set, and this is the nearest because as you increase from x, you won't get the ith bit set in any number till n.

→ Ответить

ShivamJNU

6 месяцев назад, # ^ |

Got the error in my code. orz

I was setting the bits from (i-1) to 0 instead of (j-1) to 0, where j is the first bit set while moving towards MSB from (i+1).

Here's the clutter created by me :)

→ Ответить