awoo's blog

Educational Codeforces Round 171 [Rated for Div. 2]
By awoo, history, 18 months ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Curious? Join the livestream on Tuesday, October 29 at 5:00 pm UTC to learn about the CSAI program’s curriculum, course structure, scholarships, student internships, and their hands-on learning approach.

Want more experience in coding and math competitions?
JetBrains Youth Challenge returns in November 2024!

Who can join?
Ages 13–18
Anyone currently enrolled in secondary education
Register now

On Oct/28/2024 17:35 (Moscow time) Educational Codeforces Round 171 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (196)
| Write comment?
»
18 months ago, hide # |
 
Vote: I like it -82 Vote: I do not like it

qp

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

I got a question, the penalty of time i.e. 10 minutes is the format of div. 3 and it is in this contest which is div. 2 so will the hacks have -ve points on unsuccessful attempts?

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

If I get minus again in this contest,I will leave CP.

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

I haven't lately been able to see any of the other users' submissions. Everything I see is "N/A" for source code, even for problems I have solved. Any solution to this very annoying issue? Thanks!

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

Today is my debut contest with Rainboy strategy , gonna start from $$$D$$$

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

Doing contest, problem B feels weird AF so imma skip it. Please correct me if it's skill issue.

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

$$$A$$$ is hard ._.

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

What the hell is this Problem B?

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

took 2 minutes for A and 2 hours for B

hardest B i've ever seen fr

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

how to solve E?

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

    How to solve D? Is it a Segment Tree?

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

      It's just some prefix sum stuffs

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

      prefsums + binary search. you can check my sol https://mirror.codeforces.com/contest/2026/submission/288582700

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

      (assuming 1-based indexing everywhere) consider the b array as divided into blocks as this: (n size block) (n — 1 size block) (n — 2 size block)..... now consider one block which has starting element of pair as i. what is the sum of this block? s(i, i) + s(i, i + 1) + s(i, i + 2) + ... s(i, n) where s(l, r) is sum of a from l to r. you will see that in this expression, a[i] is added n + 1 — i times. so calculate suffix array on a[i] by this rule (a[i] * (n + 1 — i))

      now if i want sum of k blocks, i need sum of block 1, sum of block 2, ... sum of block k i.e. suff[1] + suff[2] + .... suff[k] so create a prefix array on the suffix array created before.

      now consider this problem: we want to find sum 1 to x, in array b:

      first find number of blocks that are completely covered say k — 1 (use binary search) add pref[k — 1] then we are at block k, now if this block has l as left point of the pairs. we want to find (l, l) + (l, l + 1) +.... (l, l1) (l1 depends on where x lies in this block. now for this we can add suff[l] — suff[l1 + 1] directly. but note : this followed rule (a[i] * (n + 1 — i), but now a[i] has not been added (n + 1 — i) times. you will see that now a[i] has been added (n + 1 — i) — (n — l1) times. so you need to subtract s(l, l1) * (n — l1). again have a prefix array on original a for this say this answer we calculated for sum of b from 1 to x, is given by f(x), then given query is answered by f(r) — f(l-1).

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

    I saw lots of max flow solutions.

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

    answer is n — max pair matching in the graph, where left side vertices are 1,2...n and right side 0,1,2...59 ,edges i <-> j where a[i]'s j-th bit is set.

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

B?!!!! Why is n < 2000? Is it really n^2 for odd n? How to solve B?

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

    Yepp just brute force for every index For every index I push a[I] +1 just after a[I] and then check the minimum among all maximum You can see my code

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

      Thanks, can you give a case where the picking the either last or first doesn't work for odd n? I couldn't come up with such a case

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

        For n= 7

        1 2 3 1000 1001 1002 1003 It's optimal to add answer is 1 If I add 4 after 2nd index (0 based) And then pair (1 2) (3 4) (1000 1001) (1002 1003) But If you add in begining or end it will be 997

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

    I did it in O(N). You can check out my solution: 288539510

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

What is the solution for B?

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

    You can binary search for each k from low = 0 and high. = (arr[n-1] — arr[0])

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

      why return cnt >= n/2;

      how you got this idea?

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

        I will try to explain it here, let me know if you get it or not.

        cnt is the count of pairs, number of pairs should be n/2, as 2 elements make up a pair. Also imp thing is we only have to check diff between conseq elements as least diff of any j with current i will be when j = i + 1 as array is increasing. eg: if n = 6. there should be 3 pairs. if n = 7, there should be 3 pairs and the remaining 1 we can match by adding our available "atmost one addition case".

        n is even : Lets say a = {1, 5, 8, 10, 13, 14} and k = 3 here 1 and 14 would not get a pair (as (5-1) = 4 > k & 14 doesn't have a pair to match with), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2. As we can only add atmost 1 number, we can't make pair for both 1 and 14. So k = 3 is not feasible. if cnt was 3 (= n/2) then that means all the numbers have pairs. So its feasible.

        n is odd : Lets say a = {1, 5, 8, 10, 13} and k = 3 here 1 would not get a pair (as 5-1 = 4 > k), whereas (5, 8) and (10, 13) can make up pair. So cnt = 2 (= n/2). As we can only add atmost 1 number, we can make a pair for 1 by adding 0. So k = 3 is feasible.

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

    observe if we have n==even , then we cant take the extra element as that can't be compensated by any other element while making pairs so just find the max difference b/w consecutive elements, if n==odd , we have the choice to leave one element and find an extra new one for it, we can do this for each element and store the max diff to the right of it and to the max diff b/w consecutive elements to the left of it and take the max of both the overall answer for this case would be minimum of all such cases

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

c's gonna make me cry when i see the case im failing on

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

please don't write problems like B again

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

    Actually, I think it's a very good and tricky problem. No one on my friends list got it on the first try.

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

      after the first WA2, i waste about 50mins. at WA5 bcos i were minimizing the ans with 1e15 :(

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

    What? It's just a standard binary search problem.

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

after the contest, i felt like it is somehow harder than the last div1+2

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

Many low-rated people solved D in the last 15 minutes, I don't know if it's my skill issue but I don't think it is an easy problem. So please skip those who cheated.

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

couldn't solve any thing I'm mad but at least the problems are not guessing problem

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

I mean I like prefix sums, but prefix sums of prefix sums of prefix sums is too much man.

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

AC D at 1:59 :)

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

I spent close to 38 minutes for problem A and got one wrong on B just in hurry of choices Struggle is real kn geometry problems

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

today D feels like a buffed version of 2009F - Firefly's Queries.

Which I regret haven't upsolve the problem yet...

But idk maybe I'd stuck on this anyway.

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

E: Build a bipartite graph with n vertexs on the left and 60 vertexs on the right. For each 1<=i<=n and 0<=j<60, we add an edge if a[i] has j-th bit set on. For any subset of left nodes, the score is (number of chosen left vertexs )-(number of right vertexs with edge connected to chosen left vertexs ) = (number of chosen left vertexs )+(number of right vertexs without connection to chosen left vertexs )-60, then the answer is (Size of maximum independent set)-60. By the Konig theorem: In any bipartite graph, the size of maximum matching is same as minimum vertex corver, and (size of minimum vertex corver)+(size of maximum independent set)=n+60, we can calculate answer by any maximum matching algorithm.

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

If i've submitted twice of one problem which one will be counted? If first one is hacked then second one counted?

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

    the last submission that passes pretests will be counted

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

There is nothing educational about B.

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

B reminds me with this problem

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

im really confused why my binary search submission failed on B, and then my brute force one passed. obviously n is 2000, so i kinda knew it was brute force, but i didnt come up with any counter test case for my binary search one, can someone give a counter example?

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

In problem E, what does "set bit" mean ?

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

https://mirror.codeforces.com/contest/2026/submission/288585044

can someone help why this is wrong?

Greedy solution. Logic is that I store all the i where s[i] == 1 in a greater int set. ans = (n*(n+1))/2

I iterate over them{ count = 0; I have 2 variables l and r, I iterate over l from n->0. if I find s[l] == 0, then count++; if I find s[l] == 1 then I check on count, if it is 0 then I move more left.

When my 0s are exhausted, I move to r and only check the 1s from 1->n, if there is a 1 corresponding the I make count++, if there isnt then I break,

if there is a count then I reduce the answer by the indes of the one in the starting loop}

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

    The algorithm I used:

    1. Greedily scan from right to left
    2. If s[i] = 1, pair it with rightmost '0' (pos<i)
    3. Else pair it with the leftmost '1'

    In 2,3 just store the i, in these cases only, you will be saving money.

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

    If s[i] = 0, the value $$$i + 1$$$ would be added to the cost no-matter what.

    Go from right to left. The idea is to greedily exhaust the rightmost $$$1's$$$ with the first encountered $$$0's$$$ from right to left. If we exhaust in pairs, we will be able to remove as many $$$1's$$$ as possible.

    Use a std::deque to store the cost generated by $$$1's$$$. Larger values are stored in the front.

    if s[i] == 0,
    if !dq.empty() do pop.front(); if it is empty, we can pair it with the already exhausted $$$1's$$$.
    do cost += i + 1

    if s[i] == 1 do dq.push_back(i + 1). Finally when the dq contains $$$1's$$$, we can greedily exhaust the largest(front) and smallest(back) values.

    https://mirror.codeforces.com/contest/2026/submission/288593783

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

PD I know prefix sum. But just too heavy implemention... run out of time. :(

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

Do I understand right that problem F is just:

Code persistent queue on 6 stacks, in stacks we store knapsacks, so when answering the query we can just take left and right knapsacks and bruteforce the sum on each edge

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

Is large number in cpp necessary to solve problem D?

Is there a great large number template in cpp? emmmmm

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

how to solve C?

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

    I transverse the array from back to front and use deque to be able to pop front efficiently. The greedy part is to match higher indexed '1' with any first '0' found and pop it. Then, if there are still '1's remaining, just pick the lowest half.

    → Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it
    • think of a number 0 can carry the most expensive 1 (right most one)
    • after eliminate all the 0, the array is left with all the 1, then again, a left most 1 can carry the right most one. (*)
    • the answer is sum of all 0 index and all 1 index left in (*)

    main take away is just greedy and 2 pointers

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

      I was knowing it was greedy and came up with this idea but couldn't implement again. Fck my implementation skills fk it

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

        Chill mate, look at me hard stuck in pupils for 4 months already and still die trying. You peaked in specialist is a good stuff, keep going.

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

          ahh mate I peaked there I am trying really hard right now solving 1300-1500 range alot hoping to improve soon

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

wrong A why cant long long ? https://mirror.codeforces.com/contest/2026/submission/288534007

0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0 0 0 68724335200 68724335200 0 68724335200 68724335200 0

wrong output format Expected int32, but "68724335200" found (test case 1)

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

Can anyone try to hack this submission? I think greedy cannot pass this problem.

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

In these contests, is wrong answer on Test 1, considered as a penalty ?

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

Either I am getting dumb day after day, or A,B,C are actually getting difficult contest after contest.

Yesterday was Div (1 + 2) contest.

Today it is simply Div-2 contest.

I felt like today's ABC were more difficult, than Yesterday's ABC.

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

    Nope

    Today I solved ABC, but yesterday C was giving me an insomnia...

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

    I also found yesterday's B much easier than today's A or B. Both today's and yesterday's A were a bit more complicated written than usual. Today's C was much easier (at least for me) than yesterday's C, sadly I ran out of time. :D

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

A had a really nice hint for the idea that AB, CD are diagonals of a square with side min(x,y) i.e. K<=1414 , hinting the appearance of root of 2

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

Problem E seems familiar

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

Could anyone please explain how to do B? I used binary search, but it didn't work.

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

Miss chance to become master AGAIN by declaring $$$a_i$$$ of Problem E as int, not long long.

Note: shifting more than bit width is an undefined behavior, so I get WA1, not WA2 or WA3, which is confusing to me.

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

D is very reminiscent of Mosaic from this year's IOI.

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

Can anyone please explain why my solution fails:

Method: For even n, directly calculate the max distance between all pairs (a[0],a[1]), (a[2], a[3]).....

For odd n, calculate min(max(((a[0],a[1]), (a[2], a[3]).....), ((a[1],a[2]),(a[3],a[4]).....))).

Submission

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

Spent a lot of time thinking about E after coming up with the obvious Maximum Matching algorithm, not able to believe its actually the intended solution.

While not having a template for it cost me today's E, I am really surprised Maximum Matching was allowed to appear in E, especially when the idea that each bit should have atleast one unique entry is quite simple.

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

    I agree that it is too much for E. But it seems to me that we have no right to complain, since this is Educ and in fact it is intended for this: you know an algorithm — 3 minutes will be enough for you, if you don't know — you are cooked for the next two hours.

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

"Euclidean or Manhattan" missing from "A"s statement.

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

Are there any ways to solve problem E with dp? I tried to solve it with dp but get WA.

Let dp[i][j] represent the value of mask such that the number of 1-bits in mask is minimized when constructing a subsequence of length j with i as the last element of the sequence.

I think we can combine with some greedy tactics, such as save more than one mask for each dp[i][j] at a time.

Sorry for my bad English.

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

    No it's not possible because even a mask where the bits might not be minimized might be better for bigger j and many other stuff

    → Reply
»
18 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

Using random to solve E: (This is gonna WA on test 2) (OMG, it's running on test 10!) (OMG, it's running on test 20!) (OMG! It ACCEPTED!!!) (I'm going to submit a lot of them to ensure I can pass main test) (passed 6/27) (ALL 6 AC submissions are hacked, rank 103->511 QAQ)

So is there a way to hack these submissions at a high possibility? Or it was just because I was to silly when randomizing? Can these submissions be hacked? 288611596 288611196

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

for problem B this case 

2
1 3

why the answer is 2 and not 1

if k=1 then we paint 1 and 2 and then we can easily paint 2 and 3 ??????????? why I'm reading the statement wrong every time ????

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

    You can only paint WHITE cells. So, after you paint 1 and 2, cell 2 will be black, so you can't use to paint 2 and 3 since you can only paint white cells.

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

Seems that problem F only have operation 3 in the sample. See here

code copied from jiangly's code and add one assertion on operation 3. Only have 96 tests during the contest while the verdict is RE on 97.

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

    My bad :( We only discovered that during the contest. Somehow all incorrect solutions we had were incorrect even on that set of data and all correct were still correct after the generators got fixed. Luckily, not a lot of people got affected by the incomplete tests.

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

      I now got affected due to some runtime error that only fires if there's actually operations of this type in the input.

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

could someone provide counter example for this submission , im getting WA on test 5, and the solution seems kinda silly but it runs in O(60*n^2) in worst case scenario, and it seems correct to me. basically what i do is for every element i, lets call it valid, if for every bit that is set in in a[i], it has atleast 1 valid neighbour. first we assume all indices are valid, and then we check if there is an element that isn't and if there is such an element we delete it, and also since it may have made some other indices valid, but now doesnt anymore, we have to repeat this until no changes occur. this runs in O(60*n^2) in the worst case where we delete 1 element per iteration, and every element will be deleted, so its fast enough. but its getting WA on test 5 and i cant seem to find a simple counterexample.

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

Educational contest educated me that I know nothing. Nothing: No, you don't know me. Me: He knows me. He: Who, are you? Who: No, I am not "?". Not: No, your not Not. No: I know.

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

C was easier than B, also A was weird. not a balanced contest tbh,

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

What the hell was that B question ?? After several incorrect submissions, I came to a conclusion that its a BS + DP problem.

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

    For even numbers, it is only possible to paint them pairwise from left to right. For odd numbers, you can delete one element and solve it as even numbers.

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

I can't figure out why this code got WA on D. How mysterious.

#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
typedef long long llong;
llong n,q,L,R;
llong a[MAXN],presum[MAXN],sumsum[MAXN],press[MAXN],ppsum[MAXN];
llong find_pos(llong p) {
	llong l=1,r=n+1;
	while(r!=l+1) {
		llong mid=(l+r)/2;
		if (n*(n+1)/2-(mid-1)*mid/2>=p) l=mid;
		else r=mid;
	}
	return l;
}
llong query(llong p) {
	if (p==0) return 0;
	llong len=find_pos(p),order=n-len+1;
	llong starting=n*(n+1)/2-len*(len+1)/2+1;
	llong minus=presum[order-1];
	llong ans=ppsum[p-starting+order]-ppsum[order-1]-minus*(p-starting+1)+press[order-1];
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (llong i=1;i<=n;i++) {
		cin>>a[i];
		presum[i]=presum[i-1]+a[i];
		ppsum[i]=ppsum[i-1]+presum[i];
		sumsum[1]+=presum[i];
	}
	press[1]=sumsum[1];
	for (llong i=2;i<=n;i++) {
		sumsum[i]=sumsum[i-1]-(i-1)*(n-i+2);
		press[i]=press[i-1]+sumsum[i];
	}
	cin>>q;
	for (llong i=1;i<=q;i++) {
		cin>>L>>R;
		cout<<query(R)-query(L-1)<<'\n';
	}
	return 0;
}
→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Awesome contest!I am rank 3 and will become IM!

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

Why unrated?

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

problem D makes me feel like I'm not participating in CP …… All of the difficulty is to write the code. Too little about algorithm and too much about coding. Well, maybe it can help us improve our coding ability ……

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

    problem E is also not good. If you know Maximum Weight Closed Subgraph you can solve it quickly, but if you don't know that you are hardly solve it.

    I think Div .2 D and E should have good ideas without too hard code or too hard algorithm.

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

      Isnt the point of Educational Rounds to teach these topics to a wider range of participants?

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

      By your logic, Problem F is also formulaic for those who knows tree division — it is just to decompose the knapsack dp onto a tree. However, in my opinion an edu round is to be formulaic as it aims to educate.

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

        In my opinion, Edu round is more important to teach participants how to solve problem rather than a specific algorithm. In most contests like ICPC, only learned algorithms is not enough, it's more important to know when to use it and how to use it.

        It is acceptable to set problems like E or F. But I think problems which have more thinking instead of hard hard code or hard algorithm are better in a 2 hour edu round.

        → Reply
»
18 months ago, hide # |
 
Vote: I like it -25 Vote: I do not like it

sbsbsbsbsbsbsb

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

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

→ Reply