sum's blog

Codeforces Round #919 (Div. 2)
By sum, history, 13 months ago, In English

Hello Codeforces!

omeganot and I are excited to invite you to participate in Codeforces Round 919 (Div. 2) which will start on Jan/13/2024 17:35 (Moscow time). You will be given 2 hours to solve 6 problems. One of the problems is divided into 2 subtasks.

This round will be rated for participants of Division 2 with a rating lower than 2100.

We would like to thank

The score distribution is $$$500 - 1000 - 1500 - 2000 - 2250 - (2500 - 2500)$$$.

We hope everyone will enjoy the round!

UPD 1: Editorial

UPD 2: Congratulations to our winners and first solves!

Div 1 + 2
Div 2
First solves
  • Vote: I like it
  • +658
  • Vote: I do not like it

»
11 months ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

As a tester the round is delicious palatable luscious mouthwatering delectable toothsome succulent juicy dainty appetizing inviting tempting piquant.

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

    I keep getting negative deltas. The middle problems get tricky

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

As a tester, the problemset is even better than pokémon diamond & pearl

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

As a tester, I can confirm that this will be the first div 2 round of 2024.

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

As a tester, the round is delectable.

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

As a tester, this round is certainly an amazing round!

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

As a tester, I think this round is very interesting and problems are very cool :)

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

As a tester, the round brought positive curvature into my life.

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

It clashes with COCI :(

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

As a tester, this round is certainly a round.

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

Hope to reach cyan rank

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

exited......

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

Fully prepared to drop back down to specialist

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

    You have been on a steady rise. Keep it up!

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

It is first Div.2 round in 2024.

I hope this round is fun.

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

$$$5000$$$ score Div2F is 💀

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

Hope the problem statements are as long as this blog post

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

Excited for this round! Hoping to achieve green. Best of luck to all contestants! :)

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

damn they prepared it 2 month ago?

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

    That was when the blog was made. sum has been working on this contest for longer than that :). Orz!

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

    IIRC the hello 2024 round was being prepared in 2022

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

Wont this round be based on (or coincide with) BelOl like last year same time? Asking just in case, cuz took part

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

I just wish to solve A-D this time.

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

Thanks Codeforces for another contest!

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

This will be my first Div.2 round in 2024. I wish this round can have short problem statements

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

How much time did you spend for solving your the most difficult problem?

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

Can someone help me with the problem, I am trying to solve it for several days, I think for you it will be a mere task: https://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=37&id_problem=1840

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

As a participant i will try to enjoy the questions :)

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

I hope my brain don't lag at the time of contest and I am able to give my best in this winter season without my hands getting freezed :)

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

Looking forward to crying in a fetal position after round ends

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

I'm a freshman,I want to know how difficult div.2 is?if it's possible for me to become green?

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

    You have participated in Good Bye 2023 and Hello 2024 — the difficulty should be comparable to those (except that the very difficult last problems are missing here, but that won't affect you).

    Is it possible for you to become green? Yes. But is it likely? Probably not. I see that until now, you've only gained rating from contests. Remember that in some contests you will lose rating and you shouldn't get demotivated by it. But anyway, good luck, hopefully you perform well!

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

    As another freshman, it seems doable

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

As a participant, I want a positive delta :3

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

Do you know why others (mathematicians, physicists, chemists and...) doesn't have such big communities like codeforces?

Because we didn't make one for them...

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

    Because the most of Math, Physics, Chemistry problem solutions are required checking by people. Here all solutions are checked by the computer.

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

My Gut tells me it will be a good contest >⁠.⁠<

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

Hoping to get better at problem solving. Will try my best.

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

hope to solve 5 problems this round!!!

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

Hopefully the problems will be short and precise just like the announcement

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

Atleast this time leetcode ain't clashing.

Anyway it doesn't matter as always would have done codeforces ;)

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

I need two points to reach pupil :)

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

Briefly and to the point, it would always be like this

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

Is it rated?

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

    This round will be rated for participants of Division 2 with a rating lower than 2100.

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

As a participant I hope I get non negative delta.

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

(Wait this might be the shortest announcement I have ever seen.)

Hope I can enjoy this round!

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

Here it is, first div-2 contest of 2024

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

Hopeful

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

I hope i get positive delta <3

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

Excited for this round! First div-2 contest of 2024.

I hope you all get positive deltas.

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

How to become a tester? I am new here and would definitely appreciate the help!

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

Was feeling alone without cf contest ;

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

as a round the participant is i am .

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

Worst contest in a while! Congrats, it is quite an achievement to surpass gb2023!

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

Wtf is rainboy doing? Why doesn't he solving first three problems after solving the rest??? Somebody explain this to me.

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

    He is doing what he wants, actually you shouldn't care

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

    He doesn't care about rating or placing high in contests. Why solve easy problems if they aren't a challenge for you?

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

Enjoyed the problem set.

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

Weird problems, not as good as should be

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

lol

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

need to improve debugging skill

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

Thanks for contest, I really liked problem $$$E$$$!

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

Problem B felt rather easy, but took me 1 hour to implement :(

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

    I got stuck with the time limit on the 4th test, and the best time complexity I managed to implement was approximately O(k*(x+a.size)). Damn... How do you guys even come up with fast solutions? Haha.

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

      Greedy Approach worked just fine. Since the order of the array doesn't matter, sort it out in O(n).

      for B: he would like to multiply x largest elements with -1. You can pre-calculate this. for A: Max Sum if he doesn't perform any deletion? Max Sum if he deletes 1 largest element? Max Sum if he deletes 2 largest elements?............Max Sum if he deletes k largest elements? Compare answers each time and get the max. You can do this in O(n).

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

Any counter test for D https://codeforces.net/contest/1920/submission/241485595

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

One of the best rounds in a while

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

why the fuck are problems made so that contestants have to handle overflows during contests

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

    it is absolutely insane

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

      Only $$$1$$$ such problem, so i don't think it's bad. $$$D$$$ and $$$E$$$ are really good problems.

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

NOOOOOOO! I just finished debuging the F1 samples!!!

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

Any ideas for D?

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

    You have to consider at most first 64 operations of type 2 (because after size surely is larger $$$10^{18}$$$). So you can handle each query in 64 steps.\

    P.S. Out of stupidity I used size_t and 32x c++17 compiler. And i was late for fixing it, therefore I don't know whether my implementation is correct:)

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

      Why not use __int128? Its usage is the same as int and long long, except for input and output.

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

        I prefer to use standartized features/types. So really I should use int32_t, int64_t and so on.

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

what is the intended solution for c aside of the bruteforces one? edit : never mind the editorial is out btw is the bruteforces solution (looping over all valid m from 2 to n) for every k intended to pass?

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

How to do C?

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

      Doesn't help me much, because I always struggle with GCD problems.

      For this problem, my approach was that I create an array of every element in the original array mod 2. Then I see if I can group these modulos. Basically fixing m = 2.

      Stuck at WA on test 2 :(

      I'm still happy though. Going to get at least +70 :)

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

        To find such m, my idea was that if all the elements at the same position of each subarray would have same remainder, then subtracting the minimum value (among these elements) from all of them would make them divisible by m.

        Taking gcd of the elements-minValue would get us the required m, if it exists.

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

          That makes so much sense! Thank you!

          Actually, the root cause of my error was that I misunderstood the meaning of the word "partition". I thought you could rearrange the array elements, but it turns out you can't :=(

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

    Just do literally what is said in the description, split the array and compare corresponding elements to find suitable m : 241459859

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

Problem D test 7 ))))))))

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

Most enjoyable round since I can remember.

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

Why is D considered an original problem? Isn't it a very simplified version of persistent treap (cartesian tree)?

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

A really interesting round <3

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

For C, I had to ask ChatGPT because I had no idea how to determine if we can make the subarrays equal. Well-known maths are too hard for me.

https://chat.openai.com/share/f7668e07-29c9-4963-9140-d6d963858131

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

    chatgpt should be banned imo its not like other online resources

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

https://codeforces.net/contest/1920/submission/241485816 All testcases are passing on vscode but not on codeforces

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

    Where is #include <bits/stdc++.h> using namespace std; ?. I think you forgot to copy smth.

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

    Next time I recommend using the flags -g3 -fsanitize=address when compiling your solution as it will halt your program when it gets stuff like address boundary errors, that is, your program tried to access memory you have not allocated. Without these your program will peform undefined behaviours, which are very unpredictable, and sometimes it will give you the illusion of a correct solution.

    Notice that in the for loop when calculating the answer at line 42 you have i >= n - 1 - k. In the case of $$$n = 1$$$ and $$$k = 1$$$ you'll have at some point $$$i = 1 - 1 - 1 = -1$$$, so you'll try to access the vector pref at index $$$-1$$$, which is undefined behaviour, and can have any value depending on how you compile the program. That's the reason for the wrong answer.

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

I got memory limit exceeded on D ( https://codeforces.net/contest/1920/submission/241477487 ), but as far as I can tell, my solution uses O(n + q) memory, which I assumed would be fine. Is the issue that I was using python, or is O(n + q) memory too much (or does my code actually use more than that)?

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

    The numbers you store in $$$len$$$ will eventually become too big to fit into the memory limit. You have to check whether the number is larger than $$$10^{18}$$$ (You can discard it if it's bigger).

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

      Thanks! It's nice to know that the issue wasn't python, but at the same time it's not so nice to know that I was just the issue.

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

amazing contest, I enjoyed a lot solving problem D!

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

W contest, interesting problems

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

Very good contest, send me to expert.

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

I was so close to solving my first DP problem during a contest.

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

Can anybody explain me the approach of satisfying constraint?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. for all queries with a is equal to 1 meaning the range of numbers should be greater than or equal to x then store the highest of them in a variable high
    2. for all queries with a is equal to 2 meaning the range of numbers should be lesser than or equal to x then store the lowest of them in a variable low

    We encompass the range from high to low.

    1. Now for a is equal to 3 store them in an array/set

    2. Now find numbers in the set which lie between high and low including high and low, let them be equal to cnt

    high-low+1-cnt will be the answer

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

Good contest, problem C was interesting

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

why it gives wa ?? 241464609

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

    It looks like you're only checking the factors d that are at most sqrt(n). For each of these, you also need to check n / d. You can do this by just changing the sqrt(n) in your for loop to just an n and it should work (I did that question in python and didn't bother with the sqrt(n) optimisation and it was fast enough).

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

    Fixed. See 241496238

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

Can anyone tell me why i can't change my handle name?

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

Nice contest!

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

nice round

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

A.Maintain a minimum and maximum variable for operation1 and opeartion2 respectively and for operation3 make a vector of numbers that we can’t take. Now the problem converts into the count of numbers that is between min and max and not present in the vector. we will check how many numbers are in the vector which is between min and max we can’t take these. Then the answer is (max-min+1)-the number of elements in the vector between min and max.

B. The first intuition is that if Alice has to remove some k1(0<=k1<=k) element it will remove the biggest element in the array so that Bob can’t make them negative or Bob will multiply -1 to smaller element. Now in the shorted array, we can check for every k1 (0<=k1<=k) alice will remove the last k1 element and Bob will multiply -1 to the last x remaining element in the shorted array and we can calculate this sum using prefix array(Dp) in O(n).

C. We can divide the array into n/k segments of length k, here k is the divisor of n. The count of possible numbers k will be in O(n^1/3). Now for every k we have to check if there is any m>=2 for which updating the array a[i]%=m makes all the segments equal. For some k we have to compute some m for which 1st,2nd…. kth element %m of every segment equalise. we can represent all first elements like a*m+r, b*m+r, c*m +r…… . We can see that if we pair-wise subtract the elements of the first position we will get some (a-b)*m, (c-b)*m. here we can see that m can be the gcd of all elements or divisor of gcd of all elements of 1st,2nd,3rd…. positions.There may be different gcd of different positions, but m can be the divisor of gcd. so we will again take gcd of all gcds on different positions.we will check if gcd that is m>=2 or not. we will count these numbers and give the output.

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

Problem C has weak tests. This submission passed with 140 ms, but it's clearly too slow and should have exceeded time limit. I was able to hack it with a simple test where N has many divisors and all elements are the same, except for the last one.

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

There is a bug in Problem F2 tags, there are double Binary Search and Data Structure tags. (The bug exist when I'm writing this comment)

Tags

Note: Today, the bug has fixed.

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

Damn that was hard

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

I don't quite understand how it is possible that three accounts handed in all the tasks at the same time (with a difference of a few seconds, and the solutions were handed in exactly the order in which the participants are in the table), and as a small additional detail — their nicknames are from the same subject.

Task / LeviAckerman1945 / NarutoUzumaki1579 / ItachiUchiha8569

A / 241427625 / 241427527 / 241427718

B / 241440017 / 241439964 / 241440092

C / 241448078 / 241448021 / 241448153

D / 241454923 / 241454872 / 241454992

All these solutions are similar in style, but contain different initialised classes and completely non-obvious solutions. It looks like bypassing the anti-plagiarism system. Could it be cheating?

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

I wish I got a -9 so that I can farm the div. 3

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

How problem B could be solved if array elements are allowed to be negative as well ?

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

Can someone tell me why is this failing on some hidden case ?241532507 I'm calculating the prime factors of N and then checking for each prime factor if it is a valid divisor or not. If it is possible for some prime A then for all multiples of A which are also divisor of N should be valid. Is something wrong in it ?

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

Correct Output:
2

Your Output:
1

    It is true that if some prime $$$p$$$ works, all mutiples of $$$p$$$ (that are divisors of $$$n$$$) work.

    But the reverse isn't true: even if some prime $$$p$$$ doesn't work, its multiples can still work.

    For example here, you can't split into blocks of size $$$2$$$ but hou can split into blocks of size $$$4$$$ and $$$8$$$.

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

What will be the Rating of C? Great Contest BTW

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

Thanks for the interesting problems!

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

Problem C says 1≤ai≤n, but actually it is 1≤ai≤200000. :( My algorithm is too weak.

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

hm

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

include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() { int t; cin >> t; while (t--) { ll n; cin>>n; vector a(n,0);ll m=-1e18;ll score=0; for(int i=0;i<n;i++){ cin>>a[i]; m=max(m,a[i]); }

for(int i=1;i<=n;i++){
        if(n%i==0){
            ll k=i;

            //cout<<k<<endl;
            for(int j=2;j<=n;j++){
                bool div=true;
                for(int l=0;l<=n/k;l++){
                    ll w=a[l]%j;//cout<<w<<endl;
                    for(int o=l;o<n;o+=k){
                        if(a[o]%j!=w){
                            div=false;
                            break;
                        }
                    }
                }

                if(div){score++;break;}
            }}}

            if(n==1){
                score=1;
            }
            cout<<score<<endl;
}}

Can someone help as to why this is not a valid solution for problem c? i'm getting wrong answer at test 3 line 17 and hence cant see the test case

→ Reply