NercNews's blog

By NercNews, 6 years ago, translation, In English

Hello friends!

text

This weekend, on 8-9th of December — St. Petersburg, Barnaul, Kremenchug, Tbilisi, Almaty and Sochi will host the XIX Russia Team Open High School Programming Contest. Competition will be attended by more than 250 teams. Contest is held for the first time in Sochi this year -Educational Center “Sirius” will host nine teams.

The main contest will start on 9th of December at 10:00. You can follow current results by the link. Link to the tasks will be able right after the start of the tour.

A mirror will be available on Dec/09/2018 11:05 (Moscow time) – this is for those, who are not a participant, but also want to solve interesting problems! Do not join our broadcasts if you plan to take a part in the mirror. We warn you that, because of spoilers. And, of course, do not open the problem conditions before the start of the round.

If you do not want to participate in a mirror, be sure to join our broadcasts — in video format from the ICPCLive team and in text format in our Telegram-channel!

And if you want to come to the Russia Team High School Contest in St. Petersburg as a guest – just fill in the guest form and get your badge at the registration!

Our friend ismagilov.code has a post – follow this link to see a large set of commands with their total rating. Thank you for interesting information!

And please welcome some teams that stand a good chance to become Cup winners:

Team City Participant 1 Participant 2 Participant 3 Rating
Мертвые души Kazan + SPb scanhex 300iq Крамник Сергей 5641
Вова спит дома Moscow voidmax Aleksandr2754 Jatana 6854
Чудо Зверята! Almaty YaKon4ick 998kover ruslanjan 6727
danya.smelskiy Kremenchuk Sonechko MaxZubec Nazikk 6701
Проблемы с Поллардом? SPb, Vsevolozhsk kkarnauk receed forestryks 6660
Komarovi+Mziuri 1 Tbilisi saba2000 Temotoloraia baqargam 6597
Пурпурный виноград Moscow cookiedoth Kuyan TheWayISteppedOutTheCar 6558
Пыльная Испания Chelyabinsk Mlxa sava-cska liriKl 6529

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's gonna be cool^^

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What is testcase 2 in problem Minimal product

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In F How to prove solution is always unique given you ask all nC3 queries.

  • »
    »
    6 years ago, # ^ |
    Rev. 6   Vote: I like it +43 Vote: I do not like it

    You can ask all 10 queries for 5 elements of the array. Let those element in sorted order be a,b,c,d,e. Let xi be sum of returned values in all queries in which ith element was involved. Sort them, Then, you can form 5 linear equations using the returned values.(6e+3a+2b+c=x5, 3e+3d+3a+2b+c=x4, 3e+2d+2c+3a+2b=x3, 3a+3b+3e+2d+c=x2, 6a+3e+2d+c=x1) If you solve those linear equations their solution is always unique for any xi. Thus, we can uniquely determine these 5 elements. Similarly, thus you can uniquely determine all of the elements for the constraints(n>=5).
    My solution with precomputed inverse matrix of above linear equations 46821561

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem I Minimal product

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    You are given an array of size N, now your task is two find two indices i and j such that i < j, A[i] < A[j], and A[i] * A[j] is as minimal as possible across all possible valid pairs. Since an O(N²) solution is straight forward, we will discuss how to solve this in O(N).

    The final state of the answer is dependent on whether the answer is positive or negative, so we will split the answer in three cases, and solve individually for each.

    Answer is negative, so A[i] * A[j] < 0 for optimally chosen i, and j. In this case, it is easy to solve as only one element can be negative, which follows that it must be A[i], since A[i] < A[j] from the problem conditions. Solving this is simple, we need to maintain a prefix minimum across all the array, then for every element A[i], it can contribute to the above case iff prefix_minimum[i] * A[i] < 0, then for all valid indices, we need to minimize the answer over prefix_minimum[i] * A[i], where prefix_min[i] is equal to minimum(prefix_minimum[i — 1], A[i]).

    1. Answer is positive, with A[i] ≥ 0 and A[j] ≥ 0, for optimally chosen i, and j.

    This case is easy to solve as well, for each element we just need to minimize over A[i] * prefix_min[i], if A[i] > prefix_min[i].

    1. Answer is positive, with A[i] < 0 and A[j] < 0, for optimally chosen i, and j.

    This is really the interesting case, since both numbers are negative, we should greedily try to multiply numbers with minimum absolute value. For example, multiplying -3 by -2, is more beneficial than say, multiplying -20 and -25, even though -3, and -2 are larger numbers. This makes the greedy approach used in case #1, and #2 fail to arrive at an optimal solution.

    Let’s try to come with another strategy, we can notice that once a negative number A[j] appears in the array, it will never be beneficial to pair any element less than A[j] at position < j, with any element after j. More formally, Let’s denote our indices as i, j, and k, where i < j < k, A[i] < A[j], and A[i], A[j], A[k] < 0. Then, A[k] * A[j] < A[i] * A[k] for all k.

    In another words, we should try and match each index with every non matched yet index to it’s left that is less than it. At first sight, this looks like O(N²), but with careful implementation we can achieve O(N) in amortized time. We will be using a monotone stack ( a stack where every value is increasing from bottom to top). Before we push an element to the stack, we keep popping every element less than it, and minimize over this pair, otherwise we stop, and push that element. We are essentially simulating the idea in the previous paragraph. This is a smart brute-force that combines greedy to only iterate over possibly interesting pairs.

    Here’s a snippet: https://ideone.com/FxK16x

    You still have to construct the array using a generator, here’s a spoiler on how to do it efficiently, you can use an unsigned int data type for your array.

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem I: unsigned int l and r (very stupid mistake (must be int)) and O(N2) solution passes 12 test cases...

Is this a coincidence or on purpose?

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Why is it not possible to submit in practice mode? I wasn't registered for the round.

»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

When will the solutions become available?

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve L?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Let's make a function f(x) that will tell us how many lections we can provide for each student in group of x students.

    One of the possible optimal schedule patterns is greedy: fill empty slot in it with the number of student with least lections attended. Consider x = 6, n = 5, a = 5, b = 3: schedule is:

    Day 1: 1 2 3 4 5
    Day 2: 6 1 2
    Day 3: 3 4 5 6 1
    Day 4: 2 3 4
    Day 5: 5 6 1 2 3
    

    This way each student attends at least 3 lections. So f(6) = 3 in this case. We can show that result of this function is equal to , where slots is the sum of students capacity over all days. Note, that in case when a > x or b > x we cannot put more than x students in one day. So the final formula is:

    This function is monotonic. f(v) ≤ f(u) for v > u. Now we can make a binary search over x to find maximum amount of students that each student can attend at least k lections.

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Can you please provide an editorial?

»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

In question I Minimal product the array b has to be declared as unsigned long long

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem J? Definitely brute force isn't gonna work.

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone explain why my hash code can't get through the test set 12 in problem K even though I have changed the hash value so many time ? Is it some kind of ati-hash test or something ? I changed the code to store the whole string and it got AC.

AC code : 46843561

WA code : 46843449

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain their approach for J?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Solution, Part 1:
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

why my O(n) solution is giving tle on testcase 13. code — https://codeforces.net/contest/1090/submission/46848255

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Here's a puzzle for you: try to find the difference: 46856549 and then explain why this is significantly faster.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The only difference is making mod1 const , i tried to search about it and i found since we cant change the value of a const so compiler can perform optimised operations and since i am using mod1 many times in my code , so overall it makes a significant difference . Although i am not completely sure thats the reason ..

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        That's correct! And yes, it can make a big difference.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I see the editorial for the problems?