Автор PikMike, история, 7 месяцев назад, перевод, По-русски,

Привет, Codeforces!

В Jun/10/2018 13:05 (Moscow time) состоится Educational Codeforces Round 45.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Роман Ajosteen Глазов, Иван BledDest Андросов и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

Поздравляем победителей:

Место Участник Задач решено Штраф
1 KrK 7 225
2 isaf27 7 231
3 BigBag 7 325
4 Motarack 7 327
5 TangentDay 7 331

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 halyavin 202:-52
2 2014CAIS01 26:-2
3 djm03178 20
4 saw.ai 19
5 antguz 25:-17
Было сделано 549 успешных и 525 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A tzuyu_chou 0:01
B DoomzDay 0:05
C 562225807 0:08
D teja349 0:12
E eddy1021 0:18
F nhho 0:45
G AChen142857 0:14

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

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

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

Good luck to all!

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

Starts at unusual time :)

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

    I can finally participate in a contest without staying up late as a Chinese.

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

Welcome back BledDest!

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

During 20:00-20:05(BJS), I have my left hand on a computer that open Codeforces, and my right hand on a computer that open Atcoder.

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

Sometimes only for unusual time many regular participants can not participate...!!!

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

Thank MikeMirzayanov for codeforces and polygon platform. :)

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

Tester halyavin haven't registered yet)

»
7 месяцев назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

Is it rated for Div. 3 then?

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

Finally, a contest after more than a week of non-practicing :D

»
7 месяцев назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

very short statement hope problems too.

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

Contests with hacking phase make me nervous before even participating.

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

The one in which solution can be hacked on some base cases rather than edge cases :: Educational round.
So, think 4 times before submitting

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

Done with semesters finally!! Wishing higher ratings to everyone including myself :P

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

For me, it is first time contest starts in reasonable time zone. (19:05 KST) I was struggle on midnight-beginning contest heretofore :)

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

float ship; // must be a float otherwise ship sinks

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

I couldn't help but notice that people with rating >= 2100 are not marked as out of competition.

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

    "Educational rounds are rated for users with rating below 2100, but it doesn't mean other users are unofficial. I think, In those rounds all users are welcome to participate officialy."

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

This time is friendly for Chinese!

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

Can someone explain what are the extended ACM ICPC rules? In what do they differ from the regular ACM ICPC?

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

I only solved 2 in the game.I am too weak.

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

For problem D.. the only "NO" testcase is n > 1 and b > 1 .. is this true ?

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

    I think answer is NO for n = 2 and a=1, b=1, also n=3, a=1,b=1, and min(a,b)>1.

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

    I think its NO when neither of them is 1 or if both of them are 1 (except when n=1) The rule here seems to be that either of G and H will be connected (either of a and b must be 1) ^Not sure if it's entirely true though

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

      Both of them can be connected at the same time also. (Consider the graph 1--2--3--4 with 4 vertices and 3 edges)

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

I wonder what's the matter with problem D?

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

    I forgot when the a==1 and b==1... how foolish I was!

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

Give me some strong test case for problem C

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

What's the 3rd test case for problem D?

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

Can anyone tell me how many points will I get for successful hack and how many I will lose for an unsuccessful one?

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

    none. in educational rounds there is no points for hacking

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

      Then I don't get what's the point of giving 12 hours for the hack, if there is no point for hacking, I mean at last they will check each code on their test code then why 12 hours for hacking. @Infinite_M can you please explain. I am actually a beginer here.

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

        There is a point. You can increase your rank if you hack solutions of people ranked above you ;)

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

        All successful hacks will be added to system tests. existing test cases don't guarantee that program is correct.

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

          [user:killer_good] Can you please clarify this point? I was in an impression that codeforces provide some basic test cases to check code during contest.But they do have a test file including all corner test cases(like other websites , codechef,etc) after the contest they run every code through these test files(including corner test cases). is it true?? Or They just prepare base test cases on which they check submissions during contest and let participants find the corner test cases during hack??I mean don't they have test files for possible corner cases?

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

            for normal contests what you said is true. but for educational round system test will consist of successful hacks from users that's why we have a separate hacking phase unlike other contests.

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

User Fortza_Gabi_Tulba submitted F(39097227) at 00:28, and submitted E(39097570) at 00:29.

Since it is (almost) impossible for human to solve and code problem F in only one minute,

does it mean he submitted problem F while coding problem E?

Or he coded E and F, and then submitted F and E?

Or, is he a genius?

same thing for problem B(39091953) and D(39092747)...

I doubt if Fortza_Gabi_Tulba coded with friends...

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

    Тhe style of these codes is also different.

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

    Some coders such as tourist use this strategy sometimes.

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

      tourist does not do this in codeforces. It only makes sense to do this in judges where the penalty is calculated by the time of the last submission, which is not the case of codeforces where the penalty is calculated as the sum of times of all accepted submissions.

      So here it is better to submit a problem as soon as you coded it, and not doing that is suspicious.

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

    Fortza_Gabi_Tulba is a joke account.... Gabi Tulba is purple on codeforces. Take the joke

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

Bloody build stupid graph for a=1,b=1 and n>=1,damm i should have check more carefully for problem D :(.

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

Test number 31 on problem F is not correct. It has n = 1, while this is not possible. According to the statement m >= 1 and you can not have non-zero m for n = 1

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

    Yes, sorry, there was a mistake in the statement. Luckily, no one got problems on that test during the contest.

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

test case 10 in C?

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

    Just open any solution which has reached to test case 10.

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

      It is almost impossible to understand from someone's solution what I am failing at as my logic can be different than to the referred code.

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

        When you open a solution you can see test cases it has reached:

        in this case

        Perhaps that will help.

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

        If you open a solution, you can view all of the test cases that solution has reached. Just scroll down. That's what Emil_PhysMath meant.

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

    You must not include cases such as )( or )((() in your answer

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

First contest during travelling ^_^

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

I was suffered from the word in problem A "commentary delegation burle demolish blahblah" I should study english more :(

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

How to solve E?

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

    Just precalculate for each street index the index just lower or equal where you can place the lamp-post. Then iterate over all possible values of powers and compute for all values the mincost by directly jumping to the place where you place next lamp-post and take minimum over all these. 39119701

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

      Why O(nlogn)? I can prove only O(nsqrt(n)).

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

        Proving that for power i it needs O(n/i) should be enough. Let us say that we are computing for power i and length n. Now, say there is a lamppost at position l and the next lamppost be placed at r now even next lamppost must be placed at least l+i, clearly except in the case that it is not possible to illuminate the street. So there should be atmost about ~(2*n)/i iterations.So, the complexity should be O(k+nlogn). Please correct me if something is wrong.

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

    First check the maximum count of consecutive blocked positions, if this count (let this count's name be maxcon) is >=k or if the first position (0) is blocked then the answer is -1. Then search for the cheapest power starting from maxcon+1 to k. For power i, you will calculate its cost by putting its lamps greedily starting from j=0 and moving with j+=i, but if you reached some blocked j you should change j to the value of the last unblocked position before j (as if you were putting this lamp in the last unblocked position before j not in j itself).

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

      For the 1st test case,

      6 2 3

      1 3

      1 2 3

      Can't we use the lamp with power 1 to light the whole street?

      If we put it at position 0 , it will cover [0,1] . then at 2 covering [2,3] , then at 4 covering [4,5] and at 5 covering [5,6]

      That way the total cost will be 4, which is cheaper.

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

        You need also to cover the segments [1, 2] and [3, 4]. There was an announcement regarding this during the contest which was:

        "You have to illuminate the whole segment, not only its integer coordinates. For example, if n = 3, illuminating [0, 1] and [2, 3] is not enough."

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

can I get the rating in this round?

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

Does anyone know solution for G? My solution keeps getting TLE on test case 95, and I think mine has O(n log^2 n) time complexity and I can't think of any better solution. I used centroid decomposition

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

    This should work, because there are only log(ai) different values of gcd, so complexity will be n*log(ai)^2.

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

      Thank you. I was thinking too complicated solution, you are very smart

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

      can you please explain the idea a little bit.

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

      Intuitively I felt that there should only be around log(ai) different values of gcd, but I can't think of a good formal argument for why that is true. Do you have any good proof for it?

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

      Hacked huh. There are actually O(divisors) gcd values for paths (think about a leaf for every divisor and the rest of the tree has the same value). What you were thinking about is another thing, there are at most O(log) CHANGES of gcd in a path.

      So your solution is actually O(N * maxDivisors(2e5)^2) along with bad constant from using map (mostly chache misses I guess).

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

        It works, just forgot to clear maps after using ;w;

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
          Rev. 5   Проголосовать: нравится +16 Проголосовать: не нравится

          http://codeforces.com/contest/990/submission/39135974 I submited the exact same solution that got hacked and it passed in the same time as before the hack hmmm.... Looks like that hack didn't get into systests lol

          Edit: we can see the hack now http://codeforces.com/contest/990/hacks/458169/test. I tried to test it locally and the second code crashed in my computer (probably couldn't handle the memory lol). Maybe someone could add this test to the test set? This is a intuitive solution that has already appeared in codeforces but with downward paths only iirc, I wouldn't be surprised if a similar solution passed systests just because it didn't got hacked.

          Edit2: I tested it in a custom invocation and the second submission passes in a bit under 4 seconds (ignoring input) and without the clear it's MLE. Can someone prove a lower bound than what I said for this solution?

          Edit3: the hacker that did this did most hacks for G http://codeforces.com/contest/990/hacks?chosenProblemIndex=G and the test didn't get added. Hopefully he didn't miss anyone :P

          Edit4: this case was added!

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

        Hey, can you explain your approach?

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

          For each i, compute h(i) = number of paths that have value multiple of i. For each i, dp[i] = number of paths that have value exactly i = h(i) — dp[i * 2] — dp[i * 3] — dp[i * 4] — dp[i * 5] — ...

»
7 месяцев назад, # |
Rev. 6   Проголосовать: нравится -34 Проголосовать: не нравится

I was getting wrong answer in D coz I printed
YES
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0
instead of
YES
01000
10100
01010
00101
00010

basically the same result with spaces. Shouldn't that be allowed to pass?

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

what I did in C was ignored all cases of brackets which gave )( this sort of thing, and kept a count of regular expression brackets, then if suppose (())), then this one has 1 closing bracket more, hence it will require any bracket sequence which has 1 opening bracket (such as (, (() or many like this)

I iterated for every sequence if it was a regular one, I added the total number of regular ones in the list given. If it was something like (())), which means it requires one open one, hence I added number of sequences with one open bracket, and when I came to the bracket with one open required, I ignored, hence I only calculated for the regular and closed ones, as open would be covered while doing for closed ones.

Can anyone suggest me what am missing?

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

    I don't understand your solution

    what I did in C was ignored all cases of brackets which gave )( this sort of thing Do you ignore "()( )( "? Then your program won't count ()( )( + )( )() as a regular bracket sequence.

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

    At last I found it. Your program gives wrong answer to this test case. I hope it will help:)

    input
    right answer
    your programs output
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I saw one of the test case of Problem D is 1 1 1, which means a graph with just one node.

The correct answer is "NO", can anyone explain why there is no answer when n = 1?

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

Remember to use long long everywhere, even though you think that it can't be over 2^31. Especially when you can't find your mistake anywhere.

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

    That is my strategy!!!

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

    Once this slowed my solution down to make it get TLE though so it's not a strictly good idea

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

      Yeah you are right. But once on a USACO contest I got WA. Then I changed only one variable(I thought only it could cause a WA) to long long and again got WA. After the contest I read the editorial and the solution was suspiciously similar to mine. I changed all variables and got AC:(

      After that changing int to long long is the first(or maybe the second) thing I do after getting WA.

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

What is the solution for D?

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

    Connecting vertex to all others means that this vertex will make isolated component in graph's complement. So if b > 1, you need b - 1 vertex connected with other vertexes in main graph. If a > 1, you need complete graph on n - a + 1 vertexes, and a - 1 isolated ones.

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

Can one hack this solution with making an anti-hash test? http://codeforces.com/contest/990/submission/39097287

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

    Yes.

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

    Probably not because the constraint on the input is a[i] <= 1e6 so there aren't many numbers to create collisions.

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

    Unordered map doesn't use a fixed hash fucntion so it's "improbable" to find a hack.

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

      I once got several WAs in a problem because of a test designed to break unordered_map hash. Isn't it the same for hacks? Or does testing behaves differently using a fixed seed?

»
7 месяцев назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

PikMike For the Problem B, I submitted this in C++ 11, it gave me a wrong answer. Then I submitted the same code in C++14 this and got accepted.

Because of wrong submission I had to face a penalty. I think this is wrong and it should be removed.

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

    The code has an uninitialized variable. In test 3, there's nothing assigned to the variable 'got' in the binary search code. You can initialize it with a specific value and see what happens.

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

    you're right since your code has a mistake 2nd submission should be ignored.

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

      I don't think any action would be taken by MikeMirzayanov and CF admins. I hope they take decision in my favour, if they do something. Well I enjoyed the contest, though I didn't perform well. I think next round would be favorable.

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

Are there any editorial now?

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

Why this 39120549 fails while this 39119719 passes for problem C?

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

    I don't think op[N]={} initializes an array with zeroes, but I think op[N]={0} do.

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

    You are writing in an empty string (st) without changing its size, so it's undefined behavior. When stuff like this happens it's usually because you allocated the memory badly.

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

How to solve F? i figured i would put in a super source and a super sink to reduce it to a max flow prob. But complexity for solving flow vector is too bad

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

    Notice that if we add a cyclic flow on a valid flow, it's still valid. So, if the graph has cycles, we can use cyclic flow to zero an edge on the cycle, effectively removing it. Repeatedly remove edges from cycles until the graph becomes a tree, and then the problem is pretty simple.(recursively solve it from leaves) Complexity is O(n).

    I didn't solve F at contest but shortly after the contest I figured this out. Hope that I am correct.

    Update: confirmed it works

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

      Beautiful solution, thanks! I just submitted using your idea and can confirm that this indeed works

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

        why if sum !=0 test incorrect? This test looks correct.

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

          Look at the bottom right node, it has a netflow of 9, and not -9. As for why the sum should be zero, you are flowing from one node to the other, so the net inflow must be equal to the net outflow

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

    If you scroll down, you can literally see the test together with the message "wrong answer The number of components in the complement graph should be 84, but found 1"

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

      Ahh finally got My mistake but still can't visualize if a=b=1 and n<4 answer is No except n=1

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

when will the ratings be assigned regarding the educational round.

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

Awesome educational as usual, but I think two hours might have been a bit too little for seven problems. Most people didn't have the chance to work on F or G, which is a pity considering they were good problems.

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

    Yes i worked out problem E as i found it was greedy and almost wrote the code but just needed 5 mins to do some case testing.

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

I can't figure out why my solution hits the time limit. It should be O(nlog(n)). http://codeforces.com/contest/990/submission/39097135

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

    Brother i don't code in java but as i have seen several times in codeforces comments that arrays.sort() has a worst case complexity of O(n*n).

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

    Sorting Primitive types in Java uses quick sort so it takes O(N^2) in worst case. It's actually common for some reason to always include these anti quick sort tests in codeforces problems.

    To get around these you can do two things, declare your types as wrapper class (i.e Integer instead of int) so it becomes an object so runs in O(nlogn), or shuffle the input array.

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

      Thank you, I will try that tomorrow, I have never had that kind of problem before.

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

How to solve E if a lamppost of power l were to cover [x - l, x + l] ??

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

    So it turn out we can shift the lamppost to its left end in this segment to cover [x, x + 2 * l] only if [x + l] was not blocked and the problem just reduces to the same version in here.

    This idea was suggested by lrvideckis :)

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

    Fck myself. I was trying to solve this problem during contest. And couldn't create solution. So I decided to solve G instead.

    Only after your comment I reread the stamenent. (((

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

      trust me you're not alone :'( I had the same misconception about this problem :|

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

The tragedy of every educational round.. waiting for the final test and the rating change.

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

How long do i have to wait to get my rating?

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

    Until the admins of the contest wake up! We need to wait for final tests.

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

      hahahahhaha didn't really expect an answer from you.It seems like you've been checking out my profile.

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

    Well it's 10:10pm here so I will simply go sleep soon and check the next morning instead of worrying about it now. :P Good night!

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

when will rating change ?

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

Well if you cannot wait to see the final result, you may submit your code in the archive and see how it works.

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

Can anybody explain me the strategy used to start solving Problem C or any similar question question's hint or link.

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

    One bracket sequence can be:

    1. Good.

    2. Need some left brackets ( to make it good.

    3. Need some right brackets ) to make it good.

    4. Can never be good.

    Then you can do bracket matching algorithm to determine which type one sequence is and how many left or right brackets that can make it good. You can see my code at http://codeforces.com/contest/990/submission/39098111

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

    A bracket sequence will be regular if, starting count from first character, for any position of that sequence, number of opening brackets "(" is more or equal to the number of closig bracket ")" ,and finaly number of opening bracket is equal to the number of closing bracket.

    Now , if you want to make a regular sequence by concatenating two sequences , there will be some options

    1.choose two regular sequence

    2.choose one sequence that have n more opening brackets(here n=total number of opening brackets-total number of closing bracket) .and for any position of that sequence number of opening brackets are not less than number of closing brackets.and choose another sequence that have n more closing brackets than opening brackets (here n is similar to previous one).and for any position of this sequence number of closing brackets should not be more than n+number of opening brackets. now you can concatenate these two sequences in one way , 1st+2nd will be a regular sequence .

    [Don't know how much I could explain , sorry for my bad English :) ]

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

why my rating hasn't change until now? How long does the change take after the contest finished?

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

Why couldn't system tests start automatically?

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

It’s really annoying to wait for rating changes after completing Hacking phase in every Educational round. please @MikeMirzayanov solve this.

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

    Do you know that there is a chrome extension for codeforces? You can check the expected rate change quite precisely.

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

      The issue, system tests have not happened yet so expected rating change is not final.

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

after round 487 there will be no contest for 5-6 days and it's not good

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

Can anybody explain how to use generators for hacking ?

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

    It requires a code that prints out the test case to stdout. i.e. Use printf / cout to make a test case.

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

http://codeforces.com/contest/990/submission/39138201 can anyone help me finding whats wrong with my code for F?

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

Will the ratings beupdated after today's contest?

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

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

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

@ MikeMirzayanov regarding submission for the question b.microworld my submission is http://codeforces.com/contest/990/submission/39094917 it is getting correct answer(in local g++ compiler) for the test case which is showing as wrong output in the system run for one test case. this is looking very odd.

can you please look into this, and also wanted to know if any one facing same.

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

    adedalic Ajosteen BledDest can anyone respond to this.

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

    ar.size() - 2 can underflow (unsigned), which results in a large value and you access the array at that value, i.e. undefined behavior

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

      i think that case wont be arrising. please check by running , i checked it.

      test case: 1 1 1 output: 1

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

        @yassin_ reply please??

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

          It's undefined behavior, results can vary for different runs or compiler versions

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

        Test 15 as you can see is: 1 1 1 and your solution gives: -1199 what is definitely UB. It seems like it is caused by ar.size() - 2.

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

          @adedalic I checked it using local compiler and some other online as well which are working well for that input. can you once check it once by running the code. since i dont feel some thing undefined should be occuring for this code.

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

            who are down voting this,..please explain me whats wrong in the code.(which is working fine in other compilers )

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

          yassin_ adedalic

          so you guys are saying problem arise at ~~~~**~** while(n1>=0&&ar[n2]-ar[n1]<=k&&ar[n1]!=ar[n2]) ~~~~~ line 30 of code where compiler runs differently for this line. is it??

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

when will ratings get updated???

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

How is rating change determined here?? Pls help.

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

I want to become purple...

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

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

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

My following normal cin, cout solution for problem E timed out on test 6 as it was not able to read the input.

http://codeforces.com/contest/990/submission/39115276

whereas the following solution with ios sync passed.

http://codeforces.com/contest/990/submission/39145593

Is this justified?

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

Your crafting.oj.uz ratings are also updated!

We are seeking for a way to somehow differentiate the performance between the first and the 100th user, since currently both are the same because of the low $RATEDBOUND$s. If we just raise the bound, everybody's rating seems to be increased and this problem just occurs again.

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

Can anyone explain the logic behind the editorial of Problem C?