include <bits/stdc++.h>

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

+37

nice cat

→ Ответить

puupil

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

We got catman before GTA 6

→ Ответить

fft97

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

As a tester, I will be missing the chance to participate in this amazing contest(( I hope everyone enjoys the problem set.

→ Ответить

RNG

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

Amazing Contest how????????????

→ Ответить

BurnedChicken

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

+37

As a tester again, I tested today.

→ Ответить

hackstar

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

+20

What happened with wxbqwq ? Why he became an unrated perticipant?

→ Ответить

-2.71

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

-7

As a tester , The problems are worth solving !

→ Ответить

lakshya_rocks

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

As a Participant, I would be able to confirm this fact after contest:)

→ Ответить

RNG

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

Stop lying

→ Ответить

mispertion20

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

← Rev. 2 →

+18

As a tester, I wish good luck to every participant!

→ Ответить

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

← Rev. 2 →

-15

can a newbie solve first two problems???

→ Ответить

Saurabh600

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

Bro first 3 questions are mostly about intuition and logic.

→ Ответить

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

and the other three??

→ Ответить

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

lmao

→ Ответить

maxrgby

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

you've already done 10 contests, you should know

→ Ответить

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

← Rev. 2 →

-13

hopefully I'll Solve First two problems

→ Ответить

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

← Rev. 3 →

Hopefully :)!!

→ Ответить

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

and I solved First two Problems ....

→ Ответить

larush

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

← Rev. 2 →

As a tester, I hope you perform well this round. Good luck!

→ Ответить

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

← Rev. 4 →

-46

→ Ответить

Bichpaket

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

As a tester, contest is amazing

→ Ответить

monaxia

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

What is the point of using existing problems?

→ Ответить

fft97

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

Problems are only used for a specific small group of people who can be considered as testers.Also this contest is not publicly available

→ Ответить

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

As a participant, i shall wake up on time

→ Ответить

yashesh76

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

u awake ?

→ Ответить

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

thanks

→ Ответить

k1ngash

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

+12

As a tester, the problems were really nice 👍

→ Ответить

a-c

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

Thank you

→ Ответить

towley

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

cat

→ Ответить

biximo

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

+72

Poor kitty got photobombed...

→ Ответить

AdityaTakkar

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

+19

As a tester

Hint

→ Ответить

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

Chatgpt solved B1 and I just copied and pasted it. Why do you lie?

→ Ответить

AdityaTakkar

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

+10

well i guess, we found a legendary ~~cheater~~ prompter

→ Ответить

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

← Rev. 2 →

-31

Besides that finding such things doesn’t help you and is a waste of time and effort, I also just copied and pasted the problem statement. So, nothing is legendary but a weak and liar tester

→ Ответить

AdityaTakkar

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

I am sorry if that comment offended you(it was just a joke). But if you used ChatGPT during the contest for B1 , i think you are at loss(if not, Awesome!!). Apart from that i wish you good luck on your journey to CM. All the best!!

→ Ответить

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

← Rev. 2 →

It’s fine . It’s not important what i did. The important is to put more effort in preparing contests and testing and to come up with original problems in order to avoid problems that generative AIs can simply solve. Thank you and good luck to you too.

→ Ответить

N29

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

+14

As a tester, this is my first contest as a tester, I wish luck for participants!

→ Ответить

tickbird

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

As a participant, please give me positive delta!

→ Ответить

jot_s_bindra

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

+11

score distribution?

→ Ответить

IAMSHADOW

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

← Rev. 2 →

+15

As a participant ikrpprppp 's hair is majestic!

→ Ответить

dazlersan1

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

As a tester, I feel problems are interesting and worth solving. I wish good luck to all the participants.

→ Ответить

ZeoCool

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

+15

As not a tester, I hope I get +3 delta

→ Ответить

ZeoCool

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

Quick update, I got my +3 delta and became expert

→ Ответить

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

as not a tester hoping to get color change today

→ Ответить

xiojoy

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

Me too.

→ Ответить

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

all the best hope u reach CM today

→ Ответить

xiojoy

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

Hope you can reach pupil！Good luck:)

→ Ответить

817

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

;)

→ Ответить

chipi_chipi

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

congrats :D

→ Ответить

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

thanks :)

→ Ответить

Vipin

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

Maybe I'll take a step back to take a longer leap in div 3.

→ Ответить

xorfftdp

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

Very excited for this round!

→ Ответить

Banis

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

As a tester again, I tested few days ago, hope you find this round interesting:)

→ Ответить

Xiao_2710

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

Hoping to become specialist in this round:)

→ Ответить

dipanshu_115

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

It's interesting to see a cat studying for a CS degree.

→ Ответить

A1ternate

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

Какая разбалловка?

→ Ответить

pathetique

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

orz

→ Ответить

123gjweq2

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

pic goes hard

→ Ответить

Heisenberg2020

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

+14

Scoring distribution when??

→ Ответить

Binary_Thinker

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

As a tester, I tested the round!

All the best, problem is nice which I solved.

→ Ответить

_ville.claude__

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

As a normal user, i wish i can be CM

→ Ответить

_ville.claude__

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

well, i changed my color after this contest

→ Ответить

djm03178

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

As an *out of competition participant, I want to AK a Div. 2 round for the first time.

→ Ответить

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

scoring distribution when?

→ Ответить

black_big_cock

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

cute cat

→ Ответить

Akkshat_1505

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

+17

What are the score distributions?

→ Ответить

physics0523

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

As a tester, I invited to test after the end of previous round.

→ Ответить

Binary_Thinker

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

same

→ Ответить

45654

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

Downvotes on the tester's comment? I don't recognize codeforces.

→ Ответить

Emil_Aliyevv

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

potato

→ Ответить

Go8

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

Score distribution??

→ Ответить

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

+31

Is cat an official problem setter?

→ Ответить

45654

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

+15

Interesting scoring distributuion

→ Ответить

123asdf123

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

← Rev. 2 →

+12

Indeed it is 5 problems.=)

→ Ответить

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

+30

Please give some easy and good questions :)

For Me

→ Ответить

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

← Rev. 2 →

-7

Doubt solved :) Thanks for the help

→ Ответить

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

Two Problems with some slight modification, Second one will be tougher than the first one

→ Ответить

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

Thanks for your answer :-)

→ Ответить

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

how can one have idea about the rating of problem from the score ? any idea

→ Ответить

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

Well if you have given the contest.

Now you know, We don't have one XD

→ Ответить

biximo

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

There are two subtasks for the given problem. If it is marked as (a+b), a points for the easier variation, and b additional points if you solve the harder variation.

→ Ответить

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

Thanks for the reply :)

→ Ответить

athiest07

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

excited!!

→ Ответить

Graphical27

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

← Rev. 4 →

+61

Is he a tester?

→ Ответить

kai-zen

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

Hoping to become Pupil this round. I feel like today is the day.

→ Ответить

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

It can be today grandma

→ Ответить

subrat0018

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

Catforces incoming

→ Ответить

ChrysanthBlossom

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

So will this contest be rated?

→ Ответить

Karabutsa

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

Subtasks for Div.2 B? Let's see...

→ Ответить

cp_first

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

`Hope to Get `Purple Color` Back Today!!!`

→ Ответить

XiFaN1999

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

-24

Worst DIV 2

Sentence is not clear :(

→ Ответить

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

I am sorry but the statement of problem D is so badly written.

→ Ответить

Sigh

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

They could have just said that you need to cut the string into substrings with <=k length instead of all that word bs...

→ Ответить

https://codeforces.net/contest/1883/problem/E

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

I disagree, transforming the statement is also a part of the problem solving process, however the problem could have been worded much more nicely...

→ Ответить

electric_boogaloo

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

+22

Rare occurrence when I lost any remaining will to solve problems in a contest

See you again never

→ Ответить

liaoyanxu

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

+57

bad B2!

→ Ответить

bigSchrodinger

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

+12

wth is B2

→ Ответить

tyristik

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

+44

Problem D is just a copycat of this problem: https://acmp.ru/index.asp?main=task&id_task=884

Simply copy pasted my old code and got AC in 10 mins, dislike for testers.

→ Ответить

ashank_crazy

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

← Rev. 2 →

-17

Problem C is on codeforces too lol

→ Ответить

foundnt_Alice

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

They're way different! That div3 E problem is much more easier

→ Ответить

vitosevskich

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

+35

In C if $$$a_i$$$ is turned into $$$\text{log}$$$ $$$a_i$$$, it's the same problem as 1883E - Look Back.

→ Ответить

copyPasteCoder

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

I applied the same algo, but for me it is giving WA on TC 5. 272165398. Can anyone tell where my code goes wrong?

→ Ответить

OmarAboutaleb77

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

It overflows. The worst case scenario is that you multiply by 2 every time which clearly overflow.

→ Ответить

AllenAlien0307

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

That's probably why I thought that I've seen the problem somewhere else during the contest.

→ Ответить

34z12000

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

+19

Please don't FST, please don't FST

→ Ответить

tickbird

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

+11

why even make problem like C?

slowing down use of double for TL really make problem little bit fancy?

→ Ответить

ar_u

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

← Rev. 2 →

-20

Questions B2 and C are a hot mess, but I’m crossing my fingers for a positive delta.

→ Ответить

RNG

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

+19

MathForces

→ Ответить

papa-ka-para

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

I don't think, D was mathforces. I couldn't solve it though.

→ Ответить

Pyqe

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

← Rev. 2 →

+14

These are some beautiful problems <3 I especially loved D and E

→ Ответить

papa-ka-para

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

Can you please explain D ? ( since there isn't editorial yet. )

What I tried...

Last letter must be taken.
If there is a letter, that repeats 'k' times consecutively, that letter also MUST BE TAKEN.
Then on the remaining letters, I applied binary search. ( if we can do string split with k letters, then we can surely do with k+1 letters )

But doing this binary search and bitmasking got me TLE on 8th pretest.

→ Ответить

DuongForeverAlone

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

Come back to expert soon.

→ Ответить

red_one_fine_day

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

Is D somehow using bitsets over dp? Did not get any idea!

→ Ответить

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

← Rev. 2 →

Brute force all bitmasks of letters, if I had 1 more minute I would've AC.

→ Ответить

red_one_fine_day

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

Can you please explain

→ Ответить

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

← Rev. 2 →

I have yet to verify the veracity of my solution. Let's say you select some subset of letters to be the cases, let's call them "allowed" letters. Now to verify if that selection is valid, we can iterate over the string and if the current character is "allowed", we can just continue, but if it's not "allowed", it's distance to the next allowed letter must be less than $$$k$$$. The time complexity of this is $$$O(2^{c} \cdot n)$$$. This is too slow, so we have to optimize this by precalculation. We can precalculate for each letter in each mask the maximum distance to the next "allowed" letter.

→ Ответить

Abito

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

-8

My idea is that each character has a set of masks, each mask represnting some set of characters after the character in some index by distance of k. Now when we brute force some mask we have to make sure that all characters in the mask don't have any mask that doesn't have common bits with the mask. To make sure of that we make dp sos for each character and then we just have to make sure that no sumbask of the complement of the mask is there in this char sorry im just explaining in a bad way

→ Ответить

black_big_cock

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

← Rev. 2 →

-10

let d[i] = 2^(s[i] — 'A').(index from 1 to n)

For each subarray whose length is k in d,

let v = sum or of all elements in that subarray.

We will have V = {v(1), v(2),..,v(n-k+1)}. (all sum or of each subarray)

We will try all bitmask of letters. The value mask is satisfied if

min(mask & v(1), mask & v(2),.., mask & v(n — k + 1)) > 0
mask & d[n] > 0

So we can use dp sos to find the answer in O(2^n.n)

→ Ответить

papa-ka-para

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

I have implemented same... but I guess that will give TLE. You can also remove one letter from this bitmask, ( last letter, which must be taken ) . May be the way I implemented could be slow.

→ Ответить

blablabla1803

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

← Rev. 2 →

-10

LOL

→ Ответить

blablabla1803

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

← Rev. 3 →

-7

RESOLVED

→ Ответить

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

← Rev. 2 →

Nah, man... I don't know how to feel about it. I solved B2 still 6000 in the standing XD.

and C is ####

→ Ответить

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

How did you solve it?

→ Ответить

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

← Rev. 2 →

Maps. I stored no of occurences as Value and Just use the same code as used for B1

→ Ответить

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

Used a similar approach but still got WA in B2.

→ Ответить

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

I looked at your code and now I get it, it was quite stupid of me to not solve that problem.

→ Ответить

Me_as_coder

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

← Rev. 2 →

You could have submitted the B1 first with a less-optimized solution as it has a higher score.

→ Ответить

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

True, I tried to solve both of them together. And with how low the points was for B2. After solving I should have just moved to C sed :(

→ Ответить

MKasirloo

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

I think B2 has a binary search solution (just turn B1's brute force into binary search)

→ Ответить

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

I solved both using maps. I hope they pass System Tests

→ Ответить

zaixo

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

272157143 here check my solution does that using simple linear traversal

→ Ответить

SXZZ5

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

← Rev. 3 →

Yes it has one. Its a little nasty but I like it. Spent one hour during contest on it, but implementation had so many tricky "details" that I kept hacking my code with a half hearted belief instead of giving actual thought to it.

Spoiler

Solution is as follows. Basically we want to spend as much as money as possible because each spent coin = 1 extra petal in the bouquet. So, we can say our goal is to maximize the cost function.

We will use binary search to find out maximal achievable cost supposing that we have chosen flowers of $$$k$$$ and $$$(k-1)$$$ petals. Let $$$cost(a,b)$$$ be the cost function where $$$a$$$ is the number of $$$k$$$-flowers chosen (k-petals one) and $$$b$$$ is the number of $$$(k-1)-$$$ flowers.

Then, we have $$$cost(a,b) = a\cdot k + b \cdot (k-1) = (a + b) \cdot k - b$$$

We notice that $$$k$$$ is a constant and the function is monotonic in $$$(a+b)$$$,i.e, the "sum". The "sum" lies in the range $$$[0, cnt(k) + cnt(k-1)]$$$.

However, the issue is to satisfy constraint $$$cost(a,b) <= m$$$. Here, we use nasty math tricks.

For a chosen midval of sum $$$(a+b)$$$ in Binary search, we don't know what a or b actually is. But, $$$cost(a,b) <= m$$$ gives us that $$$b >= sum \cdot k - m$$$. That is to say $$$b_{min} = sum \cdot k - m$$$ is known and required to respect the constraint.

What's left now is to find maximum value of $$$cost(a,b)$$$ given that $$$sum = (a + b)$$$ has be chosen and $$$b$$$ should be atleast $$$b_min$$$. We, can do this greedily/mathily. The term $$$((a+b) * k)$$$ is already fixed at this point. Only the second term $$$(-b)$$$ is variable. We want to keep it as small as we can while still respecting $$$b_{min}$$$ criteria and also ensure a valid $$$(a+b)$$$ pair is actually possible for whatever $$$b$$$ we choose.

So, we have the key: $$$a_{actual} = sum - b_{actual}$$$. AND $$$b_{actual} >= b_{min}$$$.
Set $$$b_{actual} = b_{min}$$$ and check if corresponding $$$a_{actual} \in [0,cnt(k)]$$$. If yes, hurray.
If not, then it must be because the found $$$a_{actual} > cnt(k)$$$.
What is the next best thing we can do ? Keep $$$a_{actual}$$$ as big as we can or $$$b_{actual}$$$ small.
So, now set $$$a_{actual} = cnt(k)$$$ and $$$b_{actual} = sum - a_{actual}$$$. This is the best we can do.

Now, recheck the following two conditions one last time $$$a_{actual} \in [0, cnt(k)]$$$ AND $$$b_{actual} \in [b_{min}, cnt(k-1)]$$$.

If both, conditions are valid then are $$$sum$$$ is valid. And we can do the Binary search thingy.
If sum is not valid we claim that this $$$(a+b)$$$ pair just doesn't cannot exist (think about it we have checked both boundary conditions already and it failed for both).

Not so pretty code, only look at the bins() function: 272214802

→ Ответить

misaki646

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

only solved 2 and very slow, there goes my rating. Sad

→ Ответить

misaki646

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

math skill issue, have to git gud next time

→ Ответить

Vivek_Dubey

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

IS B1 is of Dynamic programming and if yes how 9k people manage to solve dp question ......leaving garden of green back to concrete layer of grey

→ Ответить

Zahad_2706

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

I used binary search with prefixes.

→ Ответить

ishan_exe

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

it was sliding window

→ Ответить

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

+16

It's not DP, just brute force.

→ Ответить

Laksh21262

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

I solve it using sliding window + Sorting

→ Ответить

AdunAdunov

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

no, it's not. linear algorithm

→ Ответить

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

Not sure if you can do it with dp, but you can brute force it. So that explains the 9k submissions.

→ Ответить

KindaGoodGames

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

It was actually a two pointer task. It does have similiarities to knapsack dp, but the constraints are too strict for that.

→ Ответить

AdunAdunov

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

+28

worst contest last time

→ Ответить

Laksh21262

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

D was an amazing problem

→ Ответить

ExpectoPatronum

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

My idea for problem D came from here: 1767E - Algebra Flash. Fortunately, I remembered it just in time

→ Ответить

Erering

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

found out the bug for c was that i put < instead of <= when there were 5 seconds left of the contest

→ Ответить

diobrando97

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

If the contest had 5 more minutes, I might have solved problem D. What a pity!

→ Ответить

deydhananjoy5

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

← Rev. 3 →

-10

My Approach

    int n, m;
    cin>>n>>m;
    vi v(n);
    for(auto &it : v)cin>>it;
    vi c(n);
    for(auto &it : c)cin>>it;
    vector<pii>a;
    for(int i = 0; i < n; i++)a.pb({v[i], c[i]});

    sort(al(a));
    int mx = 0;
    for(int i = 0; i + 1 < n; i++)
    {
        int l = a[i].ff, r = a[i + 1].ff;
        int c1 = a[i].ss, c2 = a[i + 1].ss;
        int canBuyL = (m/l), boughtL = min(c1, canBuyL);
        int allL = boughtL * l;
        if(allL > mx)mx = allL;

        int canBuyR = (m/r);
        int boughtR = min(c2, canBuyR);
        int allR = boughtR * r;
        if(allR > mx)mx = allR;

        if(r - l > 1)continue;

        int Rneed = (m - allL);
        int extraR = Rneed/r; 
        int boughtExtR = min(c2, extraR);

        int LnR = allL + (boughtExtR * r);
        if(LnR > mx)mx = LnR;

        int Lneed = m - allR;
        int extraL = (Lneed/l);
        int boughtExtL = min(c1, extraL);
        int RnL = allR + boughtExtL*l;
        if(RnL > mx)mx = RnL;
        debug(LnR); debug(allL); debug(RnL);

        int need = m - LnR;
        int canGive = min(boughtL, (c2 - boughtExtR));
        int opt = LnR + (min(canGive, need));
        if(opt > mx)mx = opt;
    }

    cout<<mx<<endl;

Similar Approach for B2 anyone?

update : Got AC. I was missing an edge case when n = 1. 272176756

→ Ответить

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

horrible to read

→ Ответить

piaolianggg

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

sneed

→ Ответить

NusGhy

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

+40

B2 with 500 pts is just not worthy doing... To many cases make it not beautiful.(in my algo) And C is mostly a Elementary mathematics prob.

→ Ответить

ExpectoPatronum

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

+11

Agreed, I wasted 30 minutes on it and what I got was ~250 points.

→ Ответить

beyondpluto

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

score distribution in codeforces is always a joke

→ Ответить

https://codeforces.net/contest/1995/submission/272169593

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

← Rev. 3 →

True Very True

Cause of it didn't get much time for C (Well that's just my skill issue)

→ Ответить

takopi

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

-32

literally the worst, worst problems I've ever seen

please don't ever make contest again.

→ Ответить

Parsa_Abolhassani

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

-12

so true

→ Ответить

GUNNER19_2.0

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

Can someone please tell difference in fmin() and min() , almost was knocked out by B2 pretest 3

→ Ответить

Atma_

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

Literally finished B2 2 mins after contest is over. Figured out that we only need to look at previous flower only after a long time :(

→ Ответить

Osama_Fahim

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

-10

Can someone Please tell me where did I go wrong for problem B1, I am unable to find the case or understand what did i do wrong in my implementation, Thank you

Submission : 272170306

→ Ответить

Osama_Fahim

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

Update: Initialized the answer to max initially which was wrong

→ Ответить

kalakaar

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

-10

can someone please tell me what am I missing? what is wrong with my following submission?

to problem B1 (https://codeforces.net/contest/1995/problem/B1) I could only pass my pretest 1 and wrong answer after that.

thank you

→ Ответить

anup_nayak

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

I couldn't understand your solution completely, but I think you are simply returning the maximum value in the array in case there are no consecutive numbers, this is wrong since this maximum number also has to be <= m. I don't think you are checking for this, even after correcting this mistake your logic might not work since the solution seems to be wrong.

→ Ответить

anpaio

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

+40

I don't like math :(

→ Ответить

Jagnath_Reddy

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

Is there something else in C apart from prev*(log(arr[i-1])/log(arr[i])? gave me a tle

→ Ответить

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

mine

include <bits/stdc++.h>

using namespace std; typedef long long ll;

bool cp(double a, ll x, double b, ll y) { double log_a = log(a); double log_b = log(b); double left = x * log_a; double right = y * log_b;

return left <= right;

} int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

int t;cin>>t;
while(t--){
    int n;cin>>n;
    double a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    double preBase=a[0];int prePow=1;
    ll cnt=0;
    for(int i=1;i<n;i++){
        if(cp(preBase,prePow,a[i],1)){
            preBase=a[i];
            prePow=1;
        }else{
            int z=1;ll num=a[i];
            ll pow=2;
            if(a[i]==1){cnt=-1;break;}
            while(!cp(preBase,prePow,a[i],pow)){
                pow=pow*2;
                z++;
            }
            cnt+=z;
            preBase=a[i];prePow=pow;
        }
    }
    cout<<cnt<<'\n';
}
return 0;

}

→ Ответить

anujanthwal98765432

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

Can someone explain the squaring problem?

→ Ответить

Raks_splunk

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

-8

Is C combinatorial? Like counting unique values of difference where an inversions exist then the answer will be m*(m+1)/2?

→ Ответить

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

Bruh what XD It's not

→ Ответить

Raks_splunk

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

Guessing problems don't work no more :(

→ Ответить

polosatic

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

Has anyone tried simulated annealing in E?

→ Ответить

bevigilantheiscomingback

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

I read A wrong... Sat there for a while trying to understand it before moving to B1... Turns out I should have started with C... Which was by far much easier to understand. Unfortunately. I sat around and did nothing most of this contest.

→ Ответить

hyman00

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

why wxbqwq is banned

→ Ответить

foundnt_Alice

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

+118

It seems that it's your alt account.

→ Ответить

macope6375

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

-81

@MikeMirzayanov Don’t think that because you are an administrator, you can slander people, and don’t think that you can’t do it so you can slander others. You have no evidence! ! ! You don't even have a reasonable excuse that one person can only have one account. Codeforces means that the administrator has the highest power. If you think wxbqwq is weak, you can deduct points from him, or even ban his account. However, the eyes of the masses are sharp! ! ! !

If you ban him, you will let all codeforces users around the world know that Codeforces administrators are corrupt! ! !

Codeforces will be infamous! ! ! ! !

→ Ответить

NusGhy

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

+37

show show way

→ Ответить

gehirndoper

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

Didn't enjoy this contest at all. Problems B1 and B2 took all my time. It's easy to see that an O(n log n) solution exists but I didn't succeed in implementing it.

→ Ответить

Captainfly

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

← Rev. 2 →

For problem D.Why my solution written by Python TLE10 ?my code

→ Ответить

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

← Rev. 3 →

-35

my humble request to problem setters , plz add the definition of diagonal in first problem, take me a long time that we have to consider diagonals in one direction only

→ Ответить

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

+12

well they have mentioned (i+j) thing.

Although it would be good if we had a figure

→ Ответить

kalakaar

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

but brother, do you think the value of (i+j) is the same in the other types of diagonals? think.

The definition provided in the problem is perfect.

→ Ответить

m_nature

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

A diagonal is the set of cells for which the value i + j is the same

That's literally the definition. I know maybe you mean something like top-right to bottom-left diagonals but if you take a long time to figure out it's one direction only then it's your problem tbh...

→ Ответить

flakes24

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

I don't think they should be redefining existing terms because there's potential to make it confusing. If you say diagonals consider it both ways else use some other term.

→ Ответить

accord

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

+33

B was pretty bad imho. Why did B2 have so less points? It was much harder than B1

→ Ответить

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

-13

is there any chance of points getting increased. Has it ever happened before??

→ Ответить

losXxh

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

how to solve D?

→ Ответить

CrH2

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

I have this idea about question D,but I'm not sure about its correctness:

        cin>>n>>c>>k>>s;
	vector<int> a(n+1),lst(19);
	vector<vector<int>> f(c+1,vector<int>(c+1,0));
	for (int i=0;i<n;i++) a[i+1]=s[i]-'A'+1;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=c;j++)
			if (lst[j])
				f[a[i]][j]=max(f[a[i]][j],i-lst[j]);
		lst[a[i]]=i;
	}

The original problem has become a duplicate overwrite problem based on the "ok" array in the code, which we can solve with Dancing Links.

→ Ответить

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

← Rev. 2 →

any optimizations for this submission , i m getting TLE

submission 272171232

→ Ответить

naruto__18

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

← Rev. 2 →

Shouldn't B2 have more points than B1?? 500 for B2 and 1000 for B1. It might be very less incentive for people who invested their time in coming up with general solution for B2 than just doing easy way in B1

→ Ответить

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

that means B2 values 1500 points.

→ Ответить

naruto__18

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

← Rev. 3 →

But coming up with an efficient algorithm was just 33.33% rewarding while brute force is 66.66% rewarding. I mean, at least 50-50 distribution makes sense.

Also, the max score of not just one but both B1 and B2 decreases with time while someone is implementing for B2.

→ Ответить

henshin

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

← Rev. 2 →

anyone, how to solve b1 ?

→ Ответить

crystaI

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

You could use a sliding window. Suppose when the right bound is $$$i$$$ we can choose any left bound within range $$$[j,i]$$$. Then we only need to ensure that

sum of $$$a_j,a_{j+1},\cdots,a_i$$$ is not greater than $$$m$$$;
$$$|a_j-a_i|\leqslant1$$$.

Also we should maximize the number, therefore just update $$$j$$$ for each $$$i$$$ and choose $$$j$$$ as left bound.

→ Ответить

24x7coldd

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

Same idea, and i managed to implement it :)

→ Ответить

DuongForeverAlone

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

After thinking more carefully, I was dumb to resubmit B1 as I thought it was wrong. My rank was downed like 700 after doing that.

→ Ответить

sashshaikh12

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

anyone approach for B2?

→ Ответить

accord

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

← Rev. 4 →

You need to check lone flower types and two flower types with petals of form $$$(a, a+1)$$$. Let $$$x = a$$$, $$$y = a + 1$$$ and $$$c_1 = count(x)$$$, $$$c_2 = count(y)$$$.

Then you need max value of $$$ax + by$$$ such that $$$ax + by \leq m, x \leq c_1, y \leq c_2$$$. With some math, you can do this in $$$O(1)$$$.

If $$$ac_1 + bc_2 \leq m$$$ then answer is simply $$$ac_1 + bc_2$$$.

Otherwise, we must subtract as many $$$x$$$ as we can from $$$m$$$. Then in remaining $$$m$$$, subtract as many $$$y$$$ as we can. Now we see if we can convert from $$$x$$$ to $$$y$$$ to get closer to the answer. Since $$$y = x + 1$$$, we need to figure out how much $$$1$$$'s we can add to reach the remaining $$$m$$$.

Code

ll f(ll x, ll y, ll c1, ll c2, ll m) {
	ll n = m;
	// first keep adding xs, then ys
	// then note number of c1 added and remaining c2
	// can convert x -> y by that much

	if(x*c1 + y*c2 <= m) {
		return x*c1 + y*c2;
	}

	if(c1*x == m) return m;

	if(c1*x < m) {
		m -= x*c1;
		ll subb = m/y;
		m -= y*subb;
		m -= min(c1, c2 - subb);
		m = max(m, 0ll);
	}

	if(c1*x > m) {
		ll subx = m/x;
		m -= x*subx;
		m -= min(subx, c2);
		m = max(m, 0ll);
	}

	return n-m;
}

→ Ответить

sashshaikh12

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

thank you!

→ Ответить

Aswineeey

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

← Rev. 2 →

read this bansalarpan4

→ Ответить

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

bro , i m stuck on B1 , can someone help what is wrong with this submission , i m getting TLE 272174109

→ Ответить

Aswineeey

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

man same logic is used here

→ Ответить

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

Yeah exactly, still I m getting TLE Thats the problem

→ Ответить

Aswineeey

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

← Rev. 3 →

no,im mean an logic for this ax+by≤m is done in O(1) where you used a Linear Time Approach thats the reason for TLE or Please refer Shayaan's Video for this,he also used similar approach as you did for ax+by≤m some what a logN approach.

→ Ответить

hzx12345678

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

-24

I think the problems are nice!

→ Ответить

takopi

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

-45

please unrate this round

→ Ответить

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

why?

→ Ответить

takopi

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

-53

my solution to problem C which clearly should be executed in O(nlogn) but receive TLE verdict, it must be the case codeforces server experience severe DDOS attack or similar which slowing down my solution during execution lead TLE.

→ Ответить

dotsdog

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

+11

You have a mistake though: if you return -1 mid-array, you still need to read the remaining numbers to go to the next test case.

→ Ответить

Screencast with commentary

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

Always check your code before blame.

→ Ответить

antiMathforces

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

-48

please unrate this round

→ Ответить

crystaI

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

Your handle is nice :)

→ Ответить

happybobby

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

-38

please unrate this round

→ Ответить

henshin

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

why?

→ Ответить

dotsdog

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

Damn. I tried passing the problem C with simple long double arithmetic after going to log(a_i), and it failed (for numerical precision, I guess) on some test. A tiny modification to use log2 log2 a_i right away -- and the solution passes. Oh well :)

→ Ответить

legendaryICE

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

← Rev. 3 →

Can you explain why this change fixes your code? I did similar idea and just happened to use log2l but why does using logl not work, shouldn't it all be the same since were just using change of base idea, any base should work no?

Edit: I changed my code to use logl and it worked.

→ Ответить

dotsdog

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

It should be all the same if the precision permits, yes. But if in the log2 case I need to square a number, say, 100 times, it still means that I deal with the numbers like log2(ai)*2^100. If I go to log log though, it just leads to log2(log2(ai)) + 100. So I have much much less numerical precision bs.

→ Ответить

legendaryICE

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

That makes sense thanks, guess it was just lucky that I got it AC even with logl. Probably should have tried to do it without doubles anyway.

→ Ответить

OmarAboutaleb77

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

Can you explain why log10l(log10l(x)) does not work but logl(logl(x)) works? Also, shouldn't 2^100 overflow?

log10l(log10l(x)): https://codeforces.net/contest/1995/submission/272196817

logl(logl(x)):https://codeforces.net/contest/1995/submission/272196697

→ Ответить

slabi

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

What? I tried log2(log2(a)) and it didn’t work :(

→ Ответить

Sigh

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

I got WA with log first, then AC with log2. And after contest I tried again with log and EPS, that also worked.

You can take a look at my submissions.

→ Ответить

AyushK22

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

I got WA with log2(log2(a_i)) in CPP — 17. After Contest I submitted same code in CPP — 20 and It passed.

→ Ответить

Ternary_Tree_

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

+68

thank you for giving me such a special experience of eating s**t.

→ Ответить

cwz2024

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

+22

Thanks to this hack, 272142115 , dozens of cheater failed system test! Even caught an expert cheater NavneetKumar123 =)

→ Ответить

MonoLith

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

How can you say he is a cheater

→ Ответить

cwz2024

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

He failed system test like any other guys who added a non-sense 1<<13 in their codes. So why they added this into their codes? Because they just copy paste the delibrately leaked code without thinking. Even they convert it into other languages using ChatGPT, ChatGPT won't erase the 1<<13:D

→ Ответить

kai-zen

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

For problem B, I used sorting + sliding window and from the discussion it seems to be the correct approach but I got WA.

Submission link

→ Ответить

Um_nik

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

+45

→ Ответить

Le_Gusto

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

speedran A B1 and spent the whole contest trying to fix my implementation for B2 just to get 150 points :(

I think it could have had a higher score, considering that it's more difficult than A and B

→ Ответить

krism

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

+17

Strange score distribution... B1 shoule be 500 and B2 deserves 1000.

→ Ответить

DeathbringerY

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

My Submission for C (In PyPy) : https://codeforces.net/contest/1995/submission/272154355 It seems to be working fine on first 5 tests but seems to be giving RUN_TIME error on 6th test case (Logic seems fine to me since it passed first 5 test cases)

Can someone help ?

→ Ответить

harsha_.05_

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

you get "OverflowError: int too large to convert to float" for this test case:

1
200000
1000000 999999 999998 999997 ..... upto 800001

basically your numbers are getting too big

→ Ответить

expertaq

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

Hello.

→ Ответить

divyansh.mishra

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

this was my first contest , I got one question accepted still am unrated how ?? can somebody help

→ Ответить

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

Wait

→ Ответить

xenophage

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

best round for me!

→ Ответить

lingehhhc

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

Very humorous round.

I spend almost 1 hour to solve B2 but failed, then I came to C hoping to solve it. But I got WA on #5 because of precision. I thought that my solution is wrong so I continued work on it to find another solution but failed.

Also, I've heard that some participants discussing about the duplicated problems. So I think this is a very humorous round.

Hope that I won't participate in the round like this and this round will unrated.

→ Ответить

ChickenInKitchen

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

Yes I did not like this round either and I only solved A and B1 after submitting WA on C. But this does not justify the round to be unrated sometimes you have to take a hit. And the fact that others realized a problem looks same as some other problem comes to their practice which is also a pivotal factor when it comes to performing well in contests.

→ Ответить

sam__in07

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

No Bangladeshi given contest today :(

Spoiler

→ Ответить

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

Down with all brutal leaders all over the world

→ Ответить

My post contest discussion stream for AB1B2C

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

Thanks for the round. I finally became blue. C was kinda cool

→ Ответить

Heisenberg2020

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

Guys, pls release the editorial!!

→ Ответить

aryanc403

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

+13

→ Ответить

Nirajk

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

Can anyone have a look at this solution for B. Fails test case — 3

Spoiler

while(t--){
  ll n,x;
  cin>>n>>x;

  ll a[n];
  map<ll,ll>m;
  for(int i=0; i<n; i++){
    cin>>a[i];
    m[a[i]]++;
  }

  ll ans = 0;
  ll petals = 0;
  ll prev = 0;
  ll cost = x;


  for(auto [f,s] : m){

    if(prev == 0){
      ll flowers = cost / f;
      petals = min( flowers * f , f * s);
      cost -= petals;
      prev = f;
      ans = max (ans , petals);
      continue;
    }

    if(prev + 1 != f){
      cost = x;
      ll flowers = cost / f;
      petals = min( flowers * f , f * s);
      cost -= petals;
      prev = f;
      ans = max(ans , petals);
      continue;
    }


      ll flowers = cost / f;
      petals += min(flowers * f , f * s);
      cost -= min(flowers * f , f * s);

      if(cost > 0){
        ll mini = min(flowers , s);
        mini = s - mini;

        if(mini > 0){
        int add = min(mini , cost);
        petals += add;
        }
      }
      ans = max(ans , petals);

    prev = f;
    cost = x;
    flowers = cost / f;
    petals = min( flowers * f , f * s);
    cost -= petals;
    ans = max(ans , petals);
  }
  cout<<ans<<endl;
}

}

→ Ответить

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

is this one b1 or b2? I can try fixing it if u want

→ Ответить

Nirajk

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

it is for B1 thanks for checking out!

→ Ответить

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

ok, i will do it in 10 minutes when I return home. Hope it's ok for u

→ Ответить

Nirajk

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

I got it bro, thanks though!

Spoiler

while(t--){
  ll n,x;
  cin>>n>>x;

  map<ll,ll>m;
  ll a[n],b[n];
  for(int i=0; i<n; i++){
    cin>>a[i];
    m[a[i]]++;
  }

  ll ans = 0;
  ll petals = 0;
  ll prev = 0;
  ll cost = x;
  ll prevFlowerCnt = 0;


  for(auto [f,s] : m){

    if(prev == 0){
      ll flowers = cost / f;
      petals = min( flowers * f , f * s);
      cost -= petals;
      prev = f;
      ans = max (ans , petals);
      prevFlowerCnt = min( flowers , s);
      continue;
    }

    if(prev + 1 != f){
      cost = x;
      ll flowers = cost / f;
      petals = min( flowers * f , f * s);
      cost -= petals;
      prev = f;
      ans = max(ans , petals);
      prevFlowerCnt = min( flowers , s);
      continue;
    }

      ll flowers = cost / f;
      petals += min(flowers * f , f * s);
      cost -= min(flowers * f , f * s);

      if(cost > 0){
        ll mini = min(flowers , s);
        mini = s - mini;

        if(mini > 0){
        int add = min({mini , prevFlowerCnt , cost});
        petals += add;
        }
      }
      ans = max(ans , petals);

    prev = f;
    cost = x;
    flowers = cost / f;
    petals = min( flowers * f , f * s);
    cost -= petals;
    ans = max(ans , petals);
    prevFlowerCnt = min( flowers , s);
  }
  cout<<ans<<endl;
}

}

→ Ответить

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

good job, feel a little sorry for being a bit late =)

→ Ответить

I_LOVE_TZP

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

B2 is a piece of shit！C<<B2

→ Ответить

dwj601

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

I think B2 is too hard on it's greedy :(

→ Ответить

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

eager to see editorials

→ Ответить

_mg23_

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

Can someone tell me how to hack a solution?

→ Ответить

dwj601

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

Good div2! This is my first time to solve 4 problems without tutorial! Although 2 was after system testing :)

→ Ответить

_Kee

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

← Rev. 3 →

My approach for problem C.

Spoiler

→ Ответить

akshat_17

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

I had the same approach as well :)

→ Ответить

MelodiesForever

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

I had same solution. I was surprised it passed, because if $$$\frac{\ln a_i}{\ln a_{i+1}} = 2^x$$$ and it gets calculated slightly too large, then it might be rounded up.

Not sure if there is a hack that can break this solution.

→ Ответить

_Kee

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

← Rev. 4 →

I was curious about this and tried to bruteforce all the combinations of $$$a, b$$$ ($$$1 \le a, b \le 10^6$$$) where $$$\displaystyle \frac{\ln a}{\ln b}$$$ is an integer and ceil(log(a) / log(b)) produces a wrong result. Actually there are some bad cases, but none of them are a power of 2.

Spoiler

ln 125 / ln 5 = 3.0000000000000004
ln 15625 / ln 5 = 6.000000000000001
ln 216 / ln 6 = 3.0000000000000004
ln 46656 / ln 6 = 6.000000000000001
ln 16807 / ln 7 = 5.000000000000001
ln 5832 / ln 18 = 3.0000000000000004
ln 15625 / ln 25 = 3.0000000000000004
ln 46656 / ln 36 = 3.0000000000000004
ln 59319 / ln 39 = 3.0000000000000004
ln 103823 / ln 47 = 3.0000000000000004
ln 287496 / ln 66 = 3.0000000000000004
ln 421875 / ln 75 = 3.0000000000000004
ln 512000 / ln 80 = 3.0000000000000004
ln 636056 / ln 86 = 3.0000000000000004

(Note: I used Python to find these results. Also, in my solution, it's possible to replace $$$\ln$$$ with log with other base, like $$$\log_2$$$, and if you do so, you'll have a different set of bad cases.)

So I was just lucky that I didn't get caught, and I actually should have subtracted an epsilon before applying the ceil function.

→ Ответить

aryamsingh7676

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

can you find error in my code. I had done the same thing but changed this log2(log(a[i-1])/log(a[i])) with log2(log(a[i-1))-log2(log(a[i])).

272229285

→ Ответить

MelodiesForever

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

My guess (without reading your code) is that log2(a) — log2(b) was incorrectly rounded up due to precision.

→ Ответить

debashishnayak2005

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

← Rev. 2 →

For B1, my code in contest got WA but when i resubmitted the same code after contest, it got AC.
I cannot understand why it is happening and have made a post about it.
Please clear my doubts.
Blog link
Edit -> Understood my mistake, please ignore the above comment

→ Ответить

sy799529

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

-23

can anyone help me please debug why am i getting wrong ans on pretest 4 102nd test case i have provided my code what am i doing is checking for element less than 1 if present and element greater than 1 if present and doing calculations. please help anyone!!! Thank you.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vect;
typedef map<ll,ll> mo;
typedef unordered_map<ll,ll> um;
typedef vector<pair<ll,ll>> vp;
typedef unordered_map<string,ll> ums;
typedef set<ll> setint;
typedef set<string> setstr;
#define pb push_back
const ll mod=1e9+7;
const ll fact_max=1e6+2;
ll fact_arr[fact_max+1];
ll invfact_arr[fact_max+1];

ll power(ll a,ll b){
    ll res=1;
    while (b>0){
        if (b&1){
            res=((a%mod)*(res%mod))%mod;
            b--;
        }
        else{
            a=((a%mod)*(a%mod))%mod;
            b=b>>1;
        }
    }
    return res;
}
// call to include factorial ans inv_factorial
void fact_store(){
    fact_arr[0]=1;
    for (int i=1;i<=fact_max;i++){
        fact_arr[i]=(fact_arr[i-1]*i)%mod;
    }
}

void invfact_store(){
    for (int i=0;i<=fact_max;i++){
        invfact_arr[i]=power(fact_arr[i],mod-2);
    }
}

ll ncr(ll n,ll r){
    if (r>n){
        return 0LL;
    }else{
        return ((((fact_arr[n]*invfact_arr[r])%mod)*invfact_arr[n-r])%mod);
    }
}

bool compareFirst(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first < b.first;
}

bool comparesecond(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	ll t;
	cin>>t;
	while (t--){
	    ll n,m;
	    cin>>n>>m;
	    ll a[n];
	    map<int,int> mp;
	    for (int i=0;i<n;i++){
	        cin>>a[i];
	        mp[a[i]]++;
	    }
	    sort(a,a+n);
	   // for (int i=0;i<n;i++){
	   //     cout<<a[i]<<" ";
	   // }
	   // cout<<endl;
	    set<ll> ans;
	    int i=0;
	    while (i<n){
	       // cout<<"ELE "<<a[i]<<endl; 
	        if (mp.find(a[i]-1)!=mp.end() && (a[i]-1)>0){
	           // cout<<"less ";
	            ll ct1=mp[a[i]-1];
	            ll ct2=mp[a[i]];
	            ll sum=0;
	            if (ct2>=m/a[i]){
	                sum=(m/a[i])*a[i];
	            }else{
	                sum=(a[i]*ct2);
	            }
	            ll rem=m-sum;
	            if (ct1>=rem/(a[i]-1)){
	                if ((rem%a[i]==a[i]-2) && (ct1-(rem/(a[i]-1))>0)){
	                    sum=sum+rem;
	                }else{
	                    ll q=rem/(a[i]-1);
	                    sum=sum+q*(a[i]-1);
	                }
	            }else{
	               sum=sum+(a[i]-1)*ct1; 
	            }
	           // cout<<sum<<endl;
	            ans.insert(sum);
	        }
	        if (mp.find(a[i]+1)!=mp.end() && a[i]+1<=m){
                ll ct1=mp[a[i]];
	            ll ct2=mp[a[i]+1];
	            ll sum=0;
	            if (ct2>=m/(a[i]+1)){
	                sum=(m/(a[i]+1))*(a[i]+1);
	            }else{
	                sum=((a[i]+1)*ct2);
	            }
	            ll rem=m-sum;
	            if (ct1>=rem/(a[i])){
	                if ((rem%(a[i]+1)==a[i]-1) && (ct1-(rem/(a[i]))>0)){
	                    sum=sum+rem;
	                }else{
	                    ll q=rem/(a[i]);
	                    sum=sum+q*(a[i]);
	                }
	            }else{
	               sum=sum+(a[i])*ct1; 
	            }
	           // cout<<sum<<endl;
	            ans.insert(sum);
	        }
	        ll sum=0;
	        ll ct=mp[a[i]];
	        ll num=m/a[i];
	        if (ct>=num){
	            sum=num*a[i];
	        }else{
	            sum=ct*a[i];
	        }
	       // cout<<"A[i] "<<sum<<endl;
	        ans.insert(sum);
	        i++;
	    }
	    auto it=ans.end();
	    it--;
	    cout<<*it<<endl;
	    
	}
	return 0;
}

→ Ответить

SashaT9

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

The definition of a diagonal in problem $$$\text{A}$$$ is incorrect.

→ Ответить

Abito

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

How?

→ Ответить

codeWithDarshan

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

-17

Problem C I solved using dp.

static PrintWriter out = new PrintWriter(System.out); static FastReader s = new FastReader();

public static void main(String[] args) {

    int T = 1;


    T = s.nextInt();


    outer:while (T > 0) {
        T--;

        int n = s.nextInt();
        long arr[]  =s.readArrayLong(n);

        long count = 0;

        for(int i = 0 ; i < n; i++){
            if(arr[i] > 1)count++;

            if(arr[i]==1 && count > 0){
                System.out.println(-1);
                continue outer;
            }
        }


        long ans = 0;

        long dp[] = new long[n];

        for(int i =1; i<n; i++){

            if(arr[i]>=arr[i-1] && arr[i-1] !=1 ){

                long a = arr[i-1];
                long sum = 0;
                while(a < arr[i]){
                    a = a*a;
                    sum = sum+1;
                }
                long b = 0;
                if(a > arr[i])b++;
                if(sum <= dp[i-1]){
                    dp[i] = Math.abs(sum  -dp[i-1])+b;
                    ans = ans+dp[i];
                }


            }else if(arr[i] < arr[i-1]){

                long a = arr[i];
                long sum = 0;
                while(a < arr[i-1]){
                    a = a*a;
                    sum++;
                }

                dp[i] = sum + dp[i-1];
                ans = ans+dp[i];


            }



        }


        System.out.println(ans);




        // end of while loop
    }
}

→ Ответить

Fireborn25

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

rainboy orz

→ Ответить

Scr4pp3r

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

Can someone help me with debugging this submission: https://codeforces.net/contest/1995/submission/272209517

The failing testcase is giving correct answer locally.

→ Ответить