Блог пользователя vovuh

Автор vovuh, история, 4 года назад, По-русски

Привет! В 04.09.2020 17:35 (Московское время) начнётся Codeforces Round 667 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда. Также спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за обсуждение идей и тестирование раунда!

Удачи!

UPD: Огромное спасибо Ивану Gassa Казменко за тестирование раунда и исправление некоторых проблем в условиях и в раунде в целом! Также спасибо nuipojaluista, kocko, Ilya-bar и infinitepro за тестирование раунда!

UPD2: Разбор опубликован!

  • Проголосовать: нравится
  • +365
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

are technocup rounds rated ?
can someone tell rules of these rounds?

»
4 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

with "with ratings up to 1600" so me a 380 rating can participate right?, sorry this is my second contest still a noob, is div 3 problems easier than div 2 last time where I participated?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Yes div3 problems are easier than div2

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    yes div3 is easier than div2 and don't worry about your low rating .Initially you start from 0 according to the new rules but over a span of 5 contests you are provided with 1500 extra rating (500 rating is added for the first round which you have already given xD).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      Sometimes,it is really difficult to understand why you got downvoted

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Well, I didn't downvote you, but I think that's because that guy didn't say he is worried.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        yeah but he had written "still a noob" and it was pretty evident that he did not know about the new rules so.. But yeah, even then I think you have a point

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

<too-old-joke-about-copy-pasted-part>

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Can anyone explain how this penalty is calculated?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It is the time in minutes for each solved problem. Plus 10 minutes for each submission but the last of one of those submissions per problem.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      So if one has a wrong submission for a particular problem and he is not able to make an AC until the round ends how will that penalty be calculated?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        if he does not make AC till round ends then no penalty ,else 10 minutes for every incorrect submission till AC.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Are you sure Sundaram_Sharma that if one makes many wrong submissions to a problem and is not able to get an AC for that problem will he be exempted from these penalties?

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            Yes

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              So penalties work for question wise and not total score wise?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Primary tie break is # of questions solved. Secondary tie break is time penalty, calculated based on submission time plus any penalties for wrong submissions on only solved problems by adding 10 minutes per wrong submission

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Is this true for Div 2 rounds as well?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  This is only true for rounds specifically held with "educational rounds (extended ACM-ICPC)". This is how ACM-ICPC contests are held, and usually tend to be true mostly for educational rounds. Most Div 2 contests are held with point penalties subtracted from pre-defined scored distributions.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Primary tie break is # of questions solved. Secondary tie break is time penalty, calculated based on submission time plus any penalties for wrong submissions on only solved problems by adding 10 minutes per wrong submission Will this be valid there as well?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  No. Score distribution can give harder problems higher point values such that a Div 2E might be worth 2500 points, while Problems A and B are only worth 500 and 1000 points. For example's sake say that Person A solves Problem A and B instantly, getting 1500 points. They would score less than a person who solved Problem E instantly, getting 2500 points. Notice that person A solved two problems, but would have placed worse in a regular Div 2 round. In a round held with ACM-ICPC rules, person A would have placed better than person B, having solved more problems, despite them being easier problems.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится +2 Проголосовать: не нравится

                  Actually, I'm asking about penalty. If till the end of the contest there all WA to a problem will there be any penalty?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  In both cases, only solved problem penalties are applied. If you had 10 wrong submissions on a problem, they are not applied if you do not solve it. If you solve it at the last second, the penalties are applied. However, note that there is no case where it is more beneficial to not solve a problem, even with lots of penalties on it. Solving a problem in an ACM-ICPC round with a hundred penalties would still move you ahead of everyone who had solved the number of problems you had solved minus 1. Likewise, in Div 2, you are comparing 0 points for not solving to a positive number of points, no matter how many penalties.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What does it mean by -"I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over." Are the pretests too weak or are they strong enough so that there would hardly be changes in the accepted solutions before and after the contest in the main tests?

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

My rating is 1603, is this round rated for me? base on description I am a "trusted participant of the third division", but I don't understood It is rated for those who have rating lower than 1600 "and" the trusted participant of the third division or just for first group.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +67 Проголосовать: не нравится

    "trusted participant of the third division" != "the contest is rated for you"

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +68 Проголосовать: не нравится

      If you are trusted participant of the third division,your name will be on official standing.(Because there are so many fake accounts,u n r a t e d = L G M)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Being a trusted participant of the third division means your name will appear in the standings.

    This round will be rated for you if your rating is strictly less than 1600.

    Because your rating is higher than 1600, this will be not rated for you, but because you are a trusted participant if you join the contest your name will be displayed in the rankings.

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Костры рябин

»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Hope no long queue :>

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello! I have got a question: do pretests too light to catch wrong solution? Why another person has an opportunity to make tests, which will "kill" solution of the problem?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

how to register for this? this will be my first one

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

no side story ?

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

rating has taken a major dip :(,hope to improve it in this round

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

During my school time :(

No worries better luck with next div.3 contest

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really waiting for Div3..

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Let's hope this time finally I am able to break the 1599 barrier after falling back from 1590+ rating many times

SPOILER
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please tell me why is there a trusted participant definition created when the contest is rated for non trusted participant too. Is there a difference beside the official standing table or anything i am missing?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Trusted participants will appear in the official standing but non-trusted participants will not. But it will still be rated for both of them.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

what is the fastest set solve for div3? william lin did today in 23 minutes!! that's just amazing!!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to approach problem E ?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +2 Проголосовать: не нравится
    Spoiler 1
    Spoiler 2
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is Y coordinate of any use in E?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    No use at all

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I don't think so

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Then it is solvable using segment or Fenwick trees I have an approach! PS: Solved using Binary search 91881046

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you kindly tell me why BIT and BITS are used for?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Actually Earlier my thoughts were to use Binary Indexed Tree but on further look I left that approach and tried something easier then binary search came to my mind. BIT is an array which is used to store the maximum point till which we can go from current point to next point if we were to place the board of exactly k length at this point lets say this maximum point till we reach is represented by BIT[i]. BITS[i] is just the suffix maximum array for array BIT[i].

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B solution please?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There were two cases first try to decrease a to minimum possible then try for b. The minimum of both case is the answer

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Any proof for this? That this will yield the minimum product?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        To minimise the product we have to maximise the difference between two numbers. Hence the two cases

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Hint — For a particular sum, maximum product happen when both numbers are as close as possible.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          kazuya and ctyx you two are mentioning completely opposite things

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            They are saying the same thing, read carefully.

            Basic premise here is the fact that, given a fixed perimeter, the area of rectangle is maximised when the rectangle is a square.

            Since you want minimum area, try to keep the two edge lengths as far apart as possible.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              I thought of doing a ternary search on the possible interval but realized that min can occur only in one of these three points including mid-point as the curve formed will be a regular parabola. Now realized that checking mid is not necessary as interval lies strictly either to the left or right of mid.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Always we need to try one element at least minimum value.then try to reduce other one at least minimum if n positive  !!
    step 1 : try to reduce a value till x,,, until n operation finish..if n exist then try to reduce b till y,,, until n finish..
    step 2 : try to reduce b value till y,,,, until n operation finish..if n exist then try to reduce b till y ,,, until n finish..
    
    ans=min(step-1 a*b value,step-2 a*b value);  // I copy a,b,x,y,n, value for step-2
    

    My accepted (till now) solution

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Was E solvable with two pointers? I tried so but getting WA on test 2.

code

Providing testcase would be great help

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried two pointer but it does not account for test cases like this: 1 5 10 1 3 8 13 20 where two pointer finds the 3 8 13 on the first rod, when 1 3 8 and 13 20 are optimal. I tried to come up with additional cases, but ran out of time. Trying to look at your code, I am not sure you even used two pointers? Seems as though you calculate the second pointer each for all i, which would likely fail in terms of time complexity.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For each b[i] you need to replace it with the maximum b[i] among all b[i] from i to n-1 as it is not necessary that both segments have no points between them.

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Great contest. Thanks vovuh

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Help me with E and F

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Though F is easier to think, E is easier to explain. So I will try to explain E first

    Spoiler

    What can be the best way to store x coordinate to proceed ?

    Spoiler

    Let's sort the vector of pairs as per x coordinate. One more precalculation that will be useful is, prefix array on frequencies, basically on .second of pairs in vector.

    Now let's make a dp table size of vector * 2 Either we take the current index or we don't. So if we are at i, and we take the current index, we need to find the other index, so that .first at current + k <= .first at end index for current platform. How ?

    Spoiler

    So once we have the end index, dp(i,j) = max(dp(i+1,j), prefix (end) — prefix (i-1) + dp(end+1, j-1)

    Implementation of above idea is 91831346.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Idea for F : let's us assume that we have a 3-D dp table 200*200*200 where at i,j,k we store the number of subsequences of t, in first i characters of s, using j exchanges and having occurence of first charcter of t, k times.

    To proceed to next state we 3 options, Set the current character as first letter of t, as second letter of t, or let it be same.

    We need to handle few cases carefully

    Spoiler

    A little effort and the following code will make sense. 91846302

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Idea behind F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How did you solve E?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Well it's obvious that our two segment mustn't overlap. Now lets sort our dots by their x coordinates and calc ans[i] for i dot. ans[i] — a number of dots, that belong to the segment that starts at position x[i]. We can calc it using binary serch in O(nlogn). Lets second segment have larger cords that first one. Lets calc max_suff[i] — max dots that can belong to segment, that have the same or larger coordinate than x[i]. We can do it in O(n) just max_suff[i] = max(ans[i], max_suff[i + 1]) Lets calc now_max — the position of first dot, that have larger coordinate than the end of our current first segment. tmp_ans_i — answer if first segment start at i position Now look over first segment start coordinate and calc dots belong to it with binary search then add their number to the tmp_ans_i. Now update now_max: if (x[now_max] < (end of first segment)) now_max += 1 then update tmp_ans_i: tmp_ans_i += max_suff[now_max] Now choose the greatest tmp_ans_i — it is the answer. Code: 91848373

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Very nice problems. Solved all but F (WA39). Any ideas about F? Maybe some dp? Greedy didn't work

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to pick the two segments in E after coordinate compression? Will greedy work?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    You can ignore the y coordinates. First sort the points according to the x coordinate, we'll call this array pts (for points). Then create two arrays suffix[n] and prefix[n]. They will store the maximum number of points you can save if you use one platform for points with x <= pts[i] for prefix and x >= pts[i] for suffix. These can be calculated in O(nlogn) time using binary search. Your answer would be max(prefix[i] + suffix[i+1] , where i=0...n-1) , also suffix[n] = 0

    See my submission : 91851604

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think there is a tricky edge case in problem D

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Did you check if sum of digits of n is already less than or equal to s. I solved this one but still unable to figure out the corner case in test 3

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone help to solve 2nd question?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    You can just check both possibilities first try decreasing a then b (till their limits and n obviously) then other poss would be decrease b and then a. Find min of both you got ur answer...

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone pls tell what was wrong with my D? https://codeforces.com/contest/1409/submission/91874703

»
4 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Problem E: you(y coordinate) vs the guy(x coordinate) she tells you not to worry about.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How did you solve E?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      using queue to find how many points are there from i to i-k and i to i+k for each x coordinate

      then find how many max points you can cover from left and same for right

      answer will max of sum from both sides for every point

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

E was nice!

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится
Useless cheating, but still
His code.

91803529

His alt code

91859832
Same situation at B and C

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Imagine coding the shit out of myself with digit dp just to realize that people get AC'd with simple greedy

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Is there a greedy approach that works for F? I spent a bunch of time on a few ideas but couldn't get them to work.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I can share the solution of Gassa but I didn't get deep into details. It's also $$$O(n^4)$$$ but he said it can be optimized.

    Code
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Yep I also had an $$$O(n^4)$$$ greedy, but it gets TLE. It should be optimizable to $$$O(n^3 \log n)$$$ with a Fenwick tree, but at that point it gets much more complicated than the DP solution (and is still slower).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will an unsuccessful hacking attempt increase my time penalty in this round? I tried 2 hacks both were unsuccessful.

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I like the contests by vovuh because the statements are clear and precise :)

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Anyone else solved E by binary search?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes! So for finding out how many points you can catch from a point with x-coordinate value A with K length, you can binary search the point with x-coordinate with value A+K. This can provide you with points you can catch while standing at ith position in nlog(n) time. Assuming that you sort the array of x-coordinates

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

are these cheaters phamquan-cbg and papaya.ahaha?: 91808904 91812659

I found these two VERY similar submission (when I was looking for people from my country to hack): + same strange input and output file name + exactly same loop

If you cheaters read this, please stop this immediately !!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My screencast + live commentary, enjoy watching :)

https://youtu.be/nloGFTpdTJo

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    can you Explain cnt + (i == t[0])) + cnt * (i == t[1]) part in your F solution?

    Edit: I understood

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone tell the idea how to solve E efficiently if we have $$$k$$$ platforms?

  • »
    »
    4 года назад, # ^ |
    Rev. 8   Проголосовать: нравится +4 Проголосовать: не нравится
    it can be solved by dynamic programming dp[i][j] that mean is what is the maximum number of points you can get from the first i points using j platforms .. the transition is 
    1-either use a new platform and go to the i->nxt[i] {that is the index of the point that x[nxt[i]] > x[i]+k }, you should precalc this array to keep your solution complexity is O(n*P) where P is the number of platforms and j->j+1 
    
    2-or ignore this point and go to  i->i+1 , j->j
    
»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Guys, could anybody help me understand whats wrong with my code for problem D? It gives the correct answer for all test cases in my machine, but it does not work at the Codeforces' server.

I'm sure the logic is correct, but don't know what happened. And unfortunately it was a valid submission in contest time.

MikeMirzayanov 91865709

https://codeforces.com/contest/1409/submission/91865709

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

https://codeforces.com/profile/enigma_13 Looking at this user, all his submissions have been hacked, because each of his codes has statements like if(t==xx). Although I think this way of raising ratings is very witty, should it really be encouraged?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How will it raise his/her rating?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I am not sure that this method can improve the rating in div3 and edu round. I am also a novice. But in ordinary div1 and div2 (especially div 2), you can use a small id and submit such a program. If the algorithm is correct, it can easily pass the pretest, and then you can hack it with your large id. After being hacked, you can change the value of the condition in the if and resubmit. Then you can use your large id to hack it again. This process can be repeated almost countless times. So you can get rating easily?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Nice contest, thanks. Got stuck on C until late in the game when I discovered the constraints were easy, then ran out of time. See you next contest.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

this type of hack should be banned right ?
91859832
91860660
91861276
91817628
91879637
91879985
91880404
91880766

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Such a nice round it was! It deserve more upvotes...

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

nice contest

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How can we solve E using DP?

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

System testing is in quarantine.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why the ratings has not been updated yet..?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think it s because of the new update of this great condition of being a "trusted participant".. While waiting for the rating too, I ve seen some friends of mine getting higher places in the final standings.. the reason is maybe non trusted participants got banned from the official participation.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is rating change taking time?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The round will be hosted by rules of educational rounds (extended ACM-ICPC) Educational rounds usually takes roughly 20 hours. (12 hrs of hack period +a)

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

why is this solution giving time limit exceeded?...i just ran it now...it got accepted

include <bits/stdc++.h>

using namespace std;

define endl "\n"

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

int t; cin>>t; while(t--) { long long int n,x,y,i,j,num1=0,num2=0,mn=INT_MAX; vector v; cin>>n>>x>>y;

if(n==2)
     cout<<x<<" "<<y<<endl;

   else
   {
       for(i=1;i<=x;++i)
       {
           for(j=1;j<=10000;++j)
           {
               if(i+(n-1)*j>=y)
               {
                   if((x-i)%j==0 && (y-i)%j==0)
                      {
                          if(mn>(i+(n-1)*j))
                           {
                               mn=(i+(n-1)*j);
                               num1=i;
                               num2=j;
                           }

                           if(mn==y)
                              break;
                      }
               }

           }
           if(mn==y)
                   break;
       }

       cout<<num1<<" ";
       n--;
       while(n--)
       {
           num1+=num2;
           cout<<num1<<" ";
       }

       cout<<endl;
   }

}

return 0;

}

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

waiting for rating change.. solved 5 of 6 problems

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is it rated?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this code is giving wrong ans.can someone please help me to find the bug.? this code is for question 3rd.

include<bits/stdc++.h>

using namespace std;

define ll long long int

int main() { int t ; cin >> t; while(t--) { ll n,x,y,i,j,dif=0,ans=0,i1=n,j1=n,k; cin>>n>>x>>y; vector<ll,ll>v1; // ll long long int ans=y-x; dif=ans; if(n==2){ cout<<x<<" "<<y; } else{ for(i=n-1;i>1;i--){ if(ans%i==0){ dif=ans/i; break; } } // cout<<dif<<" "; v1.pb(x); for(i=1;i<n;i++){ if(x+i*dif<=y){ v1.pb(x+i*dif); } else{ i1=i-1; break; } } // cout<<i1<<" "; for(j=1;j<n-i1;j++){ if(x-j*dif>0){ v1.pb(x-j*dif); } else{ j1=j-1; break; } } // cout<<j1<<" "; for(k=1;k<n-i1-j1;k++){ v1.pb(x+(i-1+k)*dif); } ll r=v1.size(); for(i=0;i<r;i++) cout<<v1[i]<<" "; } cout<<endl; }
return 0; }

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

My Java solution for E is just like everyone else's and the provided tutorial O(N Log N) and yet it keeps getting a TLE on test 5. Can someone have a quick look?

https://codeforces.com/contest/1409/submission/91970662

I've used FastIO, tried Java 8 and 11, nothing worked so far.

EDIT: I added some conditions to narrow down the problem, turns out Arrays.sort(A) is taking too long, which is very weird. Not sure if I'm doing something obviously wrong. Solution

EDIT 2: Turns out, randomly shuffling the array before sorting it worked!! Why would the unshuffled array take WAY longer?!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

93053565 To solve problem F, I use an dp algorithm which has O(n^4) time complexity. It spend 1996ms, when this problem limits 2000ms. Lucky.