ikrpprppp's blog

Codeforces Round 961 (Div. 2)
By ikrpprppp, 4 months ago, In English

Attention! Attention! Attention! Don't miss this opportunity!

Codeforces Round 961 (Div. 2) will be held on Jul/23/2024 17:35 (Moscow time)!

Problems for this round were prepared by a team of Neapolis University Pafos (yes, you've seen its logo in Educational Round announcements) students: Vitaly503, goncharovmike, ikrpprppp.

You will be given 5 problems some of which will be divided into two subtasks and 2 hours to solve them.

Important disclaimer! Some problems of this round were also used in CPFED x JetBrains Training Camp 2024. NUP Contest in Kazakhstan this June. If you've participated in this camp or seen the problems from there, please do not participate in this round.

We would like to thank:

Not-so-important not-so-disclaimer. If you're interested in getting a Bachelor's degree in computer science in the indefinite future, you might want to take a look at Computer Science and Artificial Intelligence program in our university administered by JetBrains.

UPD. Scoring distribution: $$$500 + (1000+500) + 1750 + 2250 + (2500 + 1500)$$$

UPD2. Congratulations to the winners:

Div 2:

  1. rainboy

  2. GidrAcH

  3. toma_ariciu

  4. biximo

  5. zhengjc

Div 1 + Div 2:

  1. tourist

  2. Ormlis

  3. potato167

  4. risujiroh

  5. kotatsugame

UPD3. Editorial.

  • Vote: I like it
  • +84
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope I get positive delta ;(

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

As a tester, I wish good luck to participants!

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

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

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

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

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

As a tester again, I tested today.

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

As a tester , The problems are worth solving !

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

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

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

hopefully I'll Solve First two problems

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

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

→ Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it -46 Vote: I do not like it

.

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

As a tester, contest is amazing

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

What is the point of using existing problems?

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

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

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

As a participant, i shall wake up on time

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

As a tester, the problems were really nice 👍

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

cat

→ Reply
»
4 months ago, # |
  Vote: I like it +72 Vote: I do not like it
Poor kitty got photobombed...
→ Reply
»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester

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

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

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

      well i guess, we found a legendary cheater prompter

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

        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

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

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

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

            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.

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

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

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

As a participant, please give me positive delta!

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

score distribution?

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

As a participant ikrpprppp 's hair is majestic!

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

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

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

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

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

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

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

as not a tester hoping to get color change today

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

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

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

Very excited for this round!

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

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

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

Hoping to become specialist in this round:)

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

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

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

orz

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

pic goes hard

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

Scoring distribution when??

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

As a tester, I tested the round!

All the best, problem is nice which I solved.

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

As a normal user, i wish i can be CM

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

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

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

scoring distribution when?

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

cute cat

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

What are the score distributions?

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

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

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

potato

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

Score distribution??

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

Is cat an official problem setter?

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

Interesting scoring distributuion

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

Indeed it is 5 problems.=)

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

Please give some easy and good questions :)

For Me

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

Doubt solved :) Thanks for the help

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

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

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

      Thanks for your answer :-)

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

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

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

        Well if you have given the contest.

        Now you know, We don't have one XD

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

    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.

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

excited!!

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

Is he a tester?

Screenshot-23-7-2024-19472-codeforces-com

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

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

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

Catforces incoming

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

So will this contest be rated?

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

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
`Hope to Get `Purple Color` Back Today!!!`
→ Reply
»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Worst DIV 2

Sentence is not clear :(

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

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

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

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

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

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

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

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

See you again never

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

bad B2!

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

wth is B2

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

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.

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

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

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

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

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

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

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

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

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

Please don't FST, please don't FST

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

why even make problem like C?

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

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

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

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

MathForces

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

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

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

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

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

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

    What I tried...

    1. Last letter must be taken.

    2. If there is a letter, that repeats 'k' times consecutively, that letter also MUST BE TAKEN.

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

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

Come back to expert soon.

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

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

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

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

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

      Can you please explain

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

        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.

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

          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

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

        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)

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

      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.

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

LOL

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

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

and C is ####

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

    How did you solve it?

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

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

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

        Used a similar approach but still got WA in B2.

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

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

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

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

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

      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 :(

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

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

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

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

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

    272157143 here check my solution does that using simple linear traversal

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

    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
    → Reply
»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

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

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

    I used binary search with prefixes.

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

    it was sliding window

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

    It's not DP, just brute force.

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

    I solve it using sliding window + Sorting

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

    no, it's not. linear algorithm

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

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

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

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

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

worst contest last time

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

D was an amazing problem

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

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

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

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

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

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

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it
My Approach

Similar Approach for B2 anyone?

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

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

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.

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

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

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

    True Very True

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

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

literally the worst, worst problems I've ever seen

please don't ever make contest again.

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

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

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

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 :(

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

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

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

    Update: Initialized the answer to max initially which was wrong

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

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

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

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

thank you

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

    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.

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

I don't like math :(

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

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

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

Can someone explain the squaring problem?

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

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

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

Has anyone tried simulated annealing in E?

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

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.

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

why wxbqwq is banned

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

    It seems that it's your alt account.

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

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

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

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.

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

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

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it -35 Vote: I do not like it

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

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

    well they have mentioned (i+j) thing.

    Although it would be good if we had a figure

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

    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.

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

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

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

    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.

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

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

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

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

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

how to solve D?

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

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.

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

any optimizations for this submission , i m getting TLE

submission 272171232

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

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

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

    that means B2 values 1500 points.

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

      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.

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

anyone, how to solve b1 ?

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

    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

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

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

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

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.

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

anyone approach for B2?

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

    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
    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you!

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

      read this bansalarpan4

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

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

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

          man same logic is used here

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

            Yeah exactly, still I m getting TLE Thats the problem

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

              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.

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

I think the problems are nice!

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

please unrate this round

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

    why?

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

      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.

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

        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.

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

        Always check your code before blame.

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

    please unrate this round

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

please unrate this round

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

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

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

    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.

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

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

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

      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.

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

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

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

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

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

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

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

    How can you say he is a cheater

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

      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

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

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

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

Screencast with commentary

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

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

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

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

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

My Submission for C (In PyPy) : https://codeforces.me/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 ?

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

    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

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

    Hello.

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

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

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

best round for me!

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

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.

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

    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.

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

No Bangladeshi given contest today :(

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

    Down with all brutal leaders all over the world

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

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

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

Guys, pls release the editorial!!

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

My post contest discussion stream for AB1B2C

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

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

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

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

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

      it is for B1 thanks for checking out!

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

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

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

          I got it bro, thanks though!

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

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

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

B2 is a piece of shit！C<<B2

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

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

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

eager to see editorials

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

Can someone tell me how to hack a solution?

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

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

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

My approach for problem C.

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

    I had the same approach as well :)

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

    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.

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

      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

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

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

    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

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

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

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

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

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

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;
}
→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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
    }
}
→ Reply
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

rainboy orz

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

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

The failing testcase is giving correct answer locally.

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

    Check if a[i-1]==1 then 0 operations for a[i] else if a[i-1]!=1 and a[i]=1 then return -1

    Otherwise continue calculating with that formula

    for example see

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

can someone help me why iam getting WA in test 1951 ? mu sub: 272212018

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

SOSdp.....

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

problems were good..

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

why does the below code TLE for D?

int solve(int i,int prev,auto& f,int k){
    if(i>=f.size()) return 0;
    int ans=INT_MAX;
    int l=i,r=i+k-1;
    for(int i=0;i<26;i++){
        if(((prev>>i)&1)){
            if(f[l][i]<=r)
                return solve(f[l][i]+1,prev,f,k);
        }
    }
    for(int i=0;i<26;i++){
        if(((prev>>i)&1)==0 && f[l][i]<=r){
            ans=min(ans,1+solve(f[l][i]+1,prev|(1<<i),f,k));
        } 
    }
    return ans;
}

void helper(){
    int n,c,k;
    cin>>n>>c>>k;
    ignore;
    string s;
    line(s);
    vector<vector<int>> f(n,vector<int>(26,n+10));
    int t=s.back()-'A';
    f[n-1][t]=n-1;
    for(int i=n-2;i>=0;i--){
        f[i]=f[i+1];
        int t=s[i]-'A';
        f[i][t]=i;
    }
    t=s.back()-'A';
    int v=(1<<t);
    cout<<solve(0,v,f,k)+1;
}
→ Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Seems like B1's tests were too weak against naive quadratic approaches and simple mistakes...

Not only did I hack various $$$\mathcal{O}(n^2)$$$ solutions in 4 different ways (not counting an unordered_map hack), but also this hack was meant to be against TLs but it's just causing so many runtime errors within a short time, even a day after the contest.

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

    I have also noticed that problems B1 and B2 were certainly harder than normally for Div2 rounds. Also, problem C is very specific. Actually, for me problem D looks easier than both B2 and C.

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

the cat look sooo cute

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

Ques 1995B1 was easily solvable with the help of chatgpt's initial suggested code with some minute changes used the same code for solving the problem and its an open source for coders to consult, so it not a violation of rules

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

Hello I have recently attended contest div 2 hosted by you. However this is first time my solution has been flagged for B2. I did not share my code with anyone during the contest, nor did I use any public or shared platforms. My development process was entirely local, and I have always adhered to the contest rules. I have written my code using sublime text editor. I have attached screenshots of my previous approach which i was thinking. I would like to request you to see that approach and the approach that i have submitted you will see a lot of similarity in code and will get to know my thinking process on how i approached the solution

My First approach Part 1 -: https://drive.google.com/file/d/1kdNOj823bkaOoTDYQgNWV0Q9wKVVbJMg/view?usp=sharing

Part 2 -: https://drive.google.com/file/d/1zo6zaNNjXbYbRB7AiIzzbdQLoXevoaUA/view?usp=sharing

My Second Approach https://drive.google.com/file/d/1zjdolNAiufLnNPz7NDy-Y1MPEgQ8ss_f/view?usp=sharing

And then eventually i figure out the way on how to remove x — 1 petal flower cost value to buy more x petal flower and then i posted the solution

My only mistake was to use ChatGpt to rephrase the solution as i used a lot of if/else statement and was running short of time

Please consider my solution

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

I am being accused of cheating for no reason at all in this contest, what happened with problem B is that i had a time limit exceed on my first submission , i tried to ask chatgpt for ideas to make it faster and more optimal to the time limit , and i dont know how and since when chatgpt is considered cheating, what i got as a notification is that i copied someone else solution, but i think what happened is we both used the same tool.

**Solutions and test generators can only use source code completely written by you, with the following two exceptions:

1 — the code was written and published/distributed before the start of the round.

2 — the code is generated using tools that were written and published/distributed before the start of the round.** this is what the rules stated , the tool i used were written and published before the start of the round, i hope if you guys can change the rules if thats considered cheating (using chatgpt), and i hope my solutions get unskipped because i was following the rules and i have no intentions of cheating in comp programming or doing such things.

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

this is the response due to unintentail leakage of my code. here the explaination: The maxPetals function leverages a popular algorithmic technique often seen in competitive programming: the sliding window approach combined with sorting. This method is effective for problems that require finding the longest or largest subarray meeting specific constraints, like maximizing the number of petals without exceeding a given cost. The function sorts the array first, making it easier to manage constraints such as the difference between the largest and smallest values in the current window. By incrementally building and adjusting this subarray, the function ensures it remains valid, a strategy that's both efficient and straightforward.

This approach is familiar to many competitive programmers because it is frequently taught in textbooks, online courses, and tutorials. The sliding window technique is a well-known solution for a variety of optimization problems, and its efficiency makes it a go-to method.

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

Sorry I have use Chat GTP to clear TLE and summited same code. I summited it and many people would have done same so i apologies for this and promises not to do it again.

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

"Hello sir[user:MikeMirzayanov], since nobody is addressing my petition to check on my submmited codes nor answering why i got flagged as a cheater, i will then send this message and hope you can answer me. Sorry for the inconvenients but i am really mad about this situation.

Problem B1;

Since it is the same exact problem without any twists i just used my already AC solution, it is not my fault that the problemsetters did not want to place any kind of twist to the problem nor i care, if the problem was that and i did not copy it from anybody in the contest i am 100% sure that can't be counted as cheating, so please remove the skipped flag since this makes me look like a shady contestant, but i have never cheated in any CF nor any contest in my life... Thanks to the best site ever, CodeForces, From Kiavash

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

Hey, sorry but pls check my submitsion for 1995C - Squaring. I didn't share my code or post it on any websites but I received talk that say my code coincident with khoaa659 :<

btw sorry if bad english

→ Reply