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

Привет, Codeforces!

2 февраля в 17:35 по Москве начнётся Educational Codeforces Round 37.

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

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

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

Задачи вместе со мной готовили Михаил PikMike Пикляев, Владимир Vovuh Петров и Адилбек adedalic Далабаев. Одну из задач на раунд предложил unbelievable02.

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

У меня также есть сообщение от наших партнёров, Harbour.Space University:

We are happy to announce the addition of two new coaches to our Hello India x Russia Programming Bootcamp: Gleb GlebsHP Evstropov, Artem VArtem Vasilyev and Filipp DPR-pavlin Rukhovich will all be attending at our India location, Amrita School of Engineering.

We look forward to seeing you all there this spring! For those of you who haven't registered, there's still time.

The Early Bird discount will be set at 20% for those who register before February 12th, 2018.

If you have any questions we can help you with, please connect with us:

Phone number: +34 674 291 422 Email Address: hello@harbour.space

UPD. Разбор задач.

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

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

:)

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

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

I like BledDest's contests.

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

Please make sure that it is rated , sometimes it becomes unrated for some statement/data system mistakes , an that is very painful

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

please make sure that the contest is rated for div-2 , sometimes it becomes unrated for some statement/data system faults , please check them again

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

3rd rated in this week <3

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

Will Educational Rounds from now on will always be rated for Div.2?

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

Sadly, it coincides with Hackerrank's HourRank 26 :(

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

Once upon a time, educational rounds used to be unrated.

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

guess who forgot to thank Mike

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

Now who will give HourRank 26 on hackerrank. wait what no one..!! :)

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

Is it rated?

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

System Tester halyavin haven't registered yet.:)

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

Привет Codeforces, как я могу предложить новые задачи для Educational Round!!!

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

clash with HourRank on hackerRank. :| .

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

clash with HourRank on HackerRank .

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

Woooow!!!

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

Since CF made Educational round rated ,"That 24 hour long waiting for standings and staying at your toes" makes it so exhausting to participate in a round :'( .

Anyway that's the beauty :D .

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

Hello Codeforces, how can I suggest new challenges for Educational Round !!!

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

It will be the best Educational Round!!! Because, in list of authors have unbelievable02!!!

;)

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

নিরাপদ সড়ক চাই

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

The contest will be rated for me if I only do hacking?

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

    I thought you couldn't hack without lock (and submit)? Has something changed?

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

      In Educational, after that 2 hours for solving, hacks are open for 24 hours. What I was asking was if I register but not solving anything and just do some hacks in that 24 hours period, will my rating be modified.

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

        NO, the hacks in educational don't give any rating and don't affect on your final result.

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

        Your rank gets modified indirectly... If you hack a person who is ranked above you, your rank decreases. So the more hacks the better.

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

    No, hacks gives nothing

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

    No. If you didn't register, it isn't rated for you.

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

Что по баллам за задачи?

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

I wish, This time I will get " Plus Rating " by solving 3 problems.

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

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

wow more than 7200 registration..:)

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

wish you high rating~

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

Я надеюсь вы после системной проверки не выложите все тесты ? в прошлый раз после системного можно было отсылать свое решения и посмотреть пройдет ли все тесты (А тесты были выложены все) или нет если не пройдут то можно взломать себя. Если выкладовать все тесты , какой толк от этого раунда .

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

    В чем проблема? Взломщики не получают никаких плюшек напрямую.

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

F is very similar to gss4 on spoj.

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

halyavin Please hack my A,B,C.

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

LOL, solved F but cant solve C XD

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

    how did you solve F ? I tried to use Segment tree but couldn't update or get divisors in short time .

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

      D(x) decreases very fast. And if x <= 2 we can dont update this position. So i have 2 segment trees and precalced all d[x] in NLoG :

      for(i=1;i<MAX;i++) for(j=i;j<MAX;j+=i) dp[j]++;

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

        yes but how to update a range using different values . I don't think lazy propagation can work .

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

          In this problem you can use set instead of range update. It will be very fast because d(x) decreases fast too

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

          Lazy propagation can be applied by keeping track of the number of time you want to apply D(ai) operation on the range. For each range [l : r] store the numbers who have values > 2 because D(2) = 2 & D(1) = 1 and it's redundant to apply update operation on these 2 numbers. so when you are updating the range of numbers, pass the value of Lazy[range] as argument so that you can apply D(ai) operation on numbers > 2 in the range Lazy[range] of times and then return the updated numbers in the range. i hope this helps.

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

        Thanks for this I got this observation but couldn't apply :(

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

        I understand that this solution will run fast enough, but how to analyze its running time complexity?

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

          I think that x has max log3(x) dividers, so complexity is about qloglog3(max(ai))

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

            , O(k1 / 3) in practice. Then we perform at most operations per index, resulting , is that it?

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

              Yes, you are right

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

                Actually, the O(k1 / 3) factor should be replaced by the maximum number of times you can make ai <--- d(ai) before ai becomes 1 or 2. For ai ≤ 106, this number is around 4.

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

    wow lot of coder cant solve F,

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

So, what's the testcase 18 in problem D???

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

in problem F what is the maximum number of updates on ith index till value of a[i] becomes equal to 2, if not initially equal to 1.

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

is the idea for G to use inclusion exclusion for each query observing fact that there will be atmost 8 distinct prime factors.

Or any better??

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

In problem F what is maximum number of updates on ith index till value of a[i] becomes equal to 2,if not initially equal to 1.

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

Spend an hour in Question B, wrongly understood the question.

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

Idea for E ?

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

    My idea is, first form a graph with the non edges. Insert every element from 1 to n into the set. For every element from 1 to n if it is in the set perform the dfs. DFS: In dfs we take a vertex and then iterate through all the remaining elements in the set and check if there is no edge between this vertex and the vertex in the set. if yes, continue. else delete this vertex from the set. Now keep track of all the elements you deleted from the set. Main: Now for every element you pushed into the vector or deleted, perform the dfs. Now this is one connected component. Now repeat the procedure for the remaining elements. Here is the solution https://ide.geeksforgeeks.org/0JuIOaiKWO But i dont know if it is correct.

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

      i tried to do same thing as you told.can you please check my code 34866232 ?

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

        What i think is 1: You are not erasing from the set. So it will be O(n2); You need to erase in the dfs. And actually it is not dfs. I gave name as dfs cuz i din think of any other name. You are doing it by brute force. As you are calling for each vertex. Just check my code https://ide.geeksforgeeks.org/0JuIOaiKWO.
        2: You are using map. it has O(logn) while vector has O(1).

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

    i) n < 2000 Just solve using BFS/DFS

    ii) n >= 2000 We can easily know that there is a largest connected component and small size connected components if n >= 2000.(Since eliminated edge is smaller than 200000)

    except largest connected component, let size of connected components = k Then (n-k)*k edge must eliminated to make that cc becomes alone. Since n >= 2000, k is smaller than 150.

    So first we think set of all vertex which has more than n-150 eliminated edges. Then that set's size is smaller than 150.(roughly)

    BFS/DFS on that set.


    It is my idea but i cannot sure it is right. Because I'm failed to implement.

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

    Assuming node X has anti-edge with {u1, u2, ..., uk}. Then, there are two thing we need to handle:

    1. Union X with u1, u2, ..., uk.

    2. Union every node inside each of the following segment: [0, u1 - 1], [u1 + 1, u2 - 1], ..., [uk + 1, $n$].

    Which is reduced to this problem from VK Cup 2015 Final.

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

    If the component graph is not connected , then the original graph is connected => number of connected component is 1. else , start bfs in the complement graph in a different manner , start from a vertex push in the queue all the unreached vertices and continue like this and for each node we use DSU to count number of sets which in result is the number of connected components.

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

can someone plz tell me why this solution doesnt work ? https://ide.geeksforgeeks.org/eN7gAAmHB0

I gave this solution just 5 min after the contest. but it got rejected on test 4. Althouh i solved using queue and bfs after 15 min, i still cant find what is wrong with this.

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

34860361

sorry for my mistake :(

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

Damn the feeling when you get A and E but not B and C due to overthinking >:(

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

Shit! "cnt x y" I thought that we get water from y then pour to x :(

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

Will unsuccessful hack result in decrease in points ?

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

I know that to solve problem F,we are able to use segment tree and I can't solve this problem.I need someone help me to solve it.Need we use some skill?

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

    check any accepted code.

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

    My solution: build 2 segment trees, one to maintain the sum of elements in segments of array a, one to maintain the count of floor numbers in segments of array a.

    Here, let's say that floor numbers are numbers which D(x) = x. (People say only 1 and 2 satisfied that rule, but I'm not so certain about that, so, just check the criterium manually — it won't cost much actually ;) ).

    You can do both REPLACE and SUM queries without lazy propagation — simply traverse throughout the trees. However, to avoid TLEs, you can skip traversing if all elements in a segment are floor numbers.

    For example, if a segment is from the 3rd to 6th element, and the floor numbers count is 4, you can skip the following traverse (since these numbers can't be replaced by any distinct integers anyway). If you're working on a REPLACE query, simply ignore it and break, otherwise, add the sum of elements in the segment represented by the node, then break the current traverse.

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

      Or you can notice that each element will be processed no more than times and do type one operations explicitly.

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

        I'm not sure if I get what you meant, can you clarify more?

        I knew the maximum processes possible for an element, this is why I said I don't need lazy propagation for my segment trees, just traversing with worst complexity O(segment_length) (but the average complexity is whole lot lower thanks to the notice of no-longer-processed-elements in a segment).

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

I see that it said Accepted rather than Pretests Passed for this contest. So does that mean there are no Systests? Not quite sure as its my first Educational Round.

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

    For educational rounds system tests will be run which include the hacks as well.

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

the very tough contest... unclarity with the statement

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

Submitting a problem was harder than solving it!!

Please repair the server

P.S. posting this comment as well

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

Submitting a problem was harder than solving it!!

Please repair the server

P.S. posting this comment as well

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

in E can there be ever more than 100000 components?
I think for that you have to provide something like 100000*(100000-1)/2 forbidden edges.
I actually overlooked the constraints.
If there can be more than that components then there is a free hack for You.
submission link

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

I did an overkill for C, which resulted wrong as well.

Can someone point out the mistake : CODE

Logic : I build an index array for input, and stored the indices with 0 in a vector. I traversed the array and if I found an element with lower index than a smaller element, I checked if there's a zero between them.

Ex : 1 3 4 5 6 2

Here, 5 has 2 (smaller element) with greater index, so I checked if there's a 0 (unswapable element) between them

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

Submitting a problem was harder than solving it!!

Please repair the server

P.S. posting this comment as well

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

    I had no problems. Maybe some latency issues on your side. Check by pinging.

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

E and F are copied. Make the round UNRATED.

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

Why do div1 users have predicted rating on cf rating predictor? Will this mess up the prediction?

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

That moment when you have the idea to solve F (failed during contest, but finally got it AC-ed after), and you completely have no ideas in D and E...

Well, with the insanely poor performance in 3 first problems, goodbye rating (again)...

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

Any idea why this is not working ? https://cf-predictor-frontend.herokuapp.com/contestSelector.jsp

It was working the previous educational round even during the hacking phase.

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

That moment when you finish solving E 30 seconds after contest ended :))

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

Try to hack me, please.

This is my submissions page. :)

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

Why is this invalid input for B? I don't see any constraint that is not fulfilled

1
2
5000 5000
5000 5000

edit: Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=l_1] equals to 5000, violates the range [1, 2000] (stdin)]

why 2000???

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

halyavin is coming !

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

Когда разбор выйдет?

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

System testing will be done by halyavin

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

Мне кажется halyavin создал бот который взломывает других. Почти нереально же взломывать так быстро.

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

System Tester — halyavin is on fire !

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

can someone explain the Idea of D , Please?


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

    given that if you sum all the tanks water in one tank, then you can take whatever you want water in amount multiple of k. now, the problem is to bring the (V%k) amount. make a knapsack from all the tanks on an array of all values under K. The cruel idea is that you maybe need to module over k when you are summing tanks values in knapsack process.

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

I have a silly (post-contest) solution for problem E.

First of all, it is mathematically provable that if G is non-connected OR if diam(G) >= 3, then !G is connected (where !G is the complement of G). So if any of the above hold for !G we draw the conclusion that G is connected. We quickly eliminate these cases.

Now we are left with only cases in which !G is a connected graph with diam(!G) <= 2. If we analyze it, we can draw the conclusion that the original G is almost connected (i.e. it has one very big connected component). We want to brute-force the answer for the original G, but we can't do that yet (it might have a large number of edges). We choose some number (O(M)) of random edges from G and brute-force on this partial graph. We remove all nodes in the largest component and all nodes adjacent to nodes in the largest component (we remember the size of this component). Finally, build the sub-graph of the original G which has only the remaining nodes. Brute force on this sub-graph and output the answer + the size of the big component we discovered before.

This is the submission: 34873106

It seems like this always give the correct answer and the run-time shouldn't be too high provided that we discover a large enough part of the big component during the brute-force on the partial graph. I'm curious if the idea is hackable.

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

    It seems to work (get AC) without the initial elimination (I guess the condition that one very big component exists holds anyway for larger graphs), but it might be easier to hack with RNG prediction. Maybe.

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

Will a successful hack be considered valid for me in any of these cases ?

  • Hacking a solution which was submitted after the contest time.
  • Hacking a solution for a problem that I didn't solve during the contest.
»
6 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Editorial?

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

    It will be posted after the hacking phase and the system testing are over

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

This is correct solution for Problem B. But when I use sort function, it gives me wrong answer on Test 5. I am not able to figure out the reason. Please Explain.. (http://codeforces.com/contest/920/submission/34874806)

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

    The problem in your sort function is that it compares the data only based on the L values, that fails in case of two students with the same L.

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

      But my 4 test passed in which same value of L exist. The sort function manage the same order if Both L are equal. Still Not get it.

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

How to solve E?

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

    search for the node with adjacent nodes fewer than sqrt(n). let it x. there must be at least one , or the overall graph is small. Now, connect all the nodes (which are not disconnected with x) with x. Now, you have a component that has more than or equal (n-sqrt(n)) nodes. brute force on the rest nodes.

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

    using brute force.Now there are (n-1)*n/2-m edges.If n less than 200,it's easy to solve,or we can prove that connected components never exceed 200.so we can sort the edges in order.And using union-find set to merge connected components.This is my submission 34858691.

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

    There is a simple way like this: You use set A to store vetices, set B to store pair of vertices which is not edge. Then we will do dfs, for every vertex u, push all v which are in set A and pair <min(u, v), max(u, v)> doesn't in set B into a vector. Of course all vertices in the vector are adjacent with u. Then you erase all of vertices in vector from A and start dfs from each of them. Complexity: log n for std::set, n for visiting n vertices -> o(n log n)

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

      Sorry there was a mistake. My solution was accepted so i though it's complexity was o(nlogn). It was o(n^2 logn) for the worst case (for every vertex, we check all the vertices remain in the set, so it should be n^2), but somehow passed pretest (maybe because of the constraint).

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

        No it's not. :)

        Each time, you time you meet a vertex, you either erase from the set ( cost 1), or you don't.

        Notice that you don't only if it belongs to the given E given edges, so you have at most O(E) pairs, and their cost is O(E).

        Totally complexity is linear in number of edges and nodes multiplied by a log factor.

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

In CF Educational R 37 in Problem C, I had written the following code, where I have done cumulative sum of 1's and checked if all bits in the string between i and arr[i]-1 are 1 (& if arr[i] < i, then between arr[i] & i-1).

It is failing for Case #5 and the test case is of length 200,000 !

I have spent close to 5 hours to figure out why it is failing :P. It will be really helpful if someone can help me figure this out (maybe provide a simple test case !)

http://codeforces.com/contest/920/submission/34883063

include

include

include

include

using namespace std;

int main(){ int n; cin>>n; vector arr(n); for(int i=0;i<n;++i){ cin>>arr[i]; --arr[i]; }

string str; cin>>str;

vector<int> cum(n-1);

cum[0]=str[0]-'0';

for(int i=1;i<n-1;++i){
    cum[i]=cum[i-1]+str[i]-'0';
}
int f=0;
for(int i=0;i<n;++i){
    int &val=arr[i];
    if(cum[val-1]-cum[i-1]==val-i) continue;
    else { f=1; break;}
}
if(f) cout<<"NO"<<endl; else cout<<"YES"<<endl;

return 0; }

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

    5 5 4 3 2 1 1111

    Answer — "Yes"

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

      sigh..sorry i was wrong

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

        Yes. All n numbers should be between 1 and n and must be unique....

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

          Also, I have tried all permutations of numbers till 10! and all 2^10-1 bits combinations for these and compared the result of my incorrect program with a correct program but could not find any test case that would produce a different results. (The program took 30 mins to run)

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

            check this input

            5

            2 1 4 3 5

            1010

            output should be YES

            but your solution produces NO

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

              Apparently, my incorrect program produced "YES" for this test case.... This would be due to memory overflow and non-handling of zero values.... as pointed out by halyavin....

              Thanks for helping out !

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

          Yeah, I also missed it.

          The input is correct, but my program also produces the correct output "Yes"

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

        Why my test does not meet these conditions?

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    cum[val - 1] - cum[i - 1]
    

    So what happens if val == 0 or i == 0 ?

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

      halyavin — YOU ARE JUST AWESOME! and thanks to Sokurov329 & supervillain !

      Zero handling is what I was missing & just did not realize this... and spent close to 7 hours on all sorts of other things....

      Really thanks for identifying this!

      Next time, I will post here earlier!

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

Could anyone provide any small but tricky test case for problem F? I am having trouble understanding the bug with my logic/implementation ( submission link: 34884739 ) and all test cases except #1 seems to be intractable.

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

Can someone explain the DSU solution for E, in details? An example would be really nice. Thanks.

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

Looks like it is legal to transfer water from tank to itself in problem D. Is that supposed to be allowed?

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

Could anyone please help me why i'm getting WA on problem F ? Here is my submission 34886833

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

Could someone explain why am getting TLE on E with O(m·log(n)) algorithm?Here is my code 34891034 and here is explanation of algorithm and proof of complexity:So I will use set to save nodes that are adjacent to current node,and not marked yet.Note that with BFS I only need one set ,every time node is visited I delete it from set,and when it's turn to traverse adjacent nodes for node A we will delete all nodes that aren't adjacent with A and after that we will add them back.Proof of complexity:Deleting and adding nodes that aren't adjacent to current node will take at most O(m * log(n)) time where constant factor is 4 because we will add and erase those nodes.Note that we will iterate exactly once for every node in set possible so that part is linear.So maximal number of operations is 4 * m * log(n) + n < 15 * 105.What I got wrong?

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

I see that there is a few people on the top 50 got their solution hacked, but the leaderboard still show that their solution is accepted.. is there something wrong?

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

Few hours ago halyavin did 190 hacks.
Now it shows 187 :/

Also, why is eddy1021's rank shown as 1(3) in common standings?

Is there any issue?

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

Why the rates haven't been updated? :(

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

To those who solved E.Connected Components, how do we use DSU??

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

Right now maybe Codeforces is having some issues. It's very slow, I can't submit my solution and (maybe) the leaderboard in Educational Codeforces Round 37 is showing the results of about 10 hours ago.

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

And now we have Internal Server Errors on the hack and submission pages.

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

Is there no penalty for wrong submissions in this contest ?

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

In statement of problem 920E - Connected Components? it is said "denoting that there is no edge between x and y. Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test)". But in test 85 we can found edges 1 2 and 2 1 in one test. Why?

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

Problem E is not new : http://codeforces.com/contest/190/problem/E Also in the statement they say that "Each pair is listed at most once" but in test 85 they are not ! This round should be unrated!

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

    oh i see you're in edge of falling back to cyan. (and didn't solve E though ). I think the problem E should be rejudged not unrated.

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

      I think they should rejudge E regardless.

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

      did you read the problem "Counter attack" ? They are the same !

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

        Well, did you ever try just solving problems instead of trying to google them during the contest? :D

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

          Come on! if a problem is copied from another, does this not affect the rating?

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

            You're partially right, ya. But this claim is correct only presuming many people have seen this problem beforehand.

            It would be kinda tough to persuade me that all div2 participants remember the problem that took part ~350 rounds ago :D

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

            Its an educational, its literally written in the description that problem might look similar to some in the past..

            p.side.note: this drafts button needs to be placed somewhere else.

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

              I'am against that for a rated contest the problems could look similar to some in the past.

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

      Agree with you. Rejudge the problem E and not unrated.

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

      Now he solved E ;)

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

the 85th test case of E is wrong. 7 20 4 6 6 7 4 5 1 2 2 4 1 7 3 5 2 1 6 2 6 1 7 3 3 2 3 6 3 1 3 4 2 5 1 6 7 4 6 3 7 5

(6,3) and (3,6),(6,1) and (1,6),(1,2) and (2,1) are all listed but (x, y) and (y, x) are considered the same (so they are never listed in the same test). will rejudge?

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

Repeated later.

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

Here, in the latest hack for problem E, the verdict to this hack had to be "invalid input" instead of processing it.

And since this is the last test, it's pretty easy to accepte all the solutions which failed on this test and not make it unrated.

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

Unfortunately, test 85 in problem E was invalid.

I don't have any permission to rejudge the whole problem, so I tried to find all solutions that failed on this test and rejudge them manually. If your solution still fails on test 85, please tell me so I can rejudge it.

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

    Filter the status page by setting the problem section to that problem, and the verdict to "WA", and the test to ">= 84", it may help.

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

      I did exactly this, but maybe I missed something?

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

        True.

        And I am wondering, was that hack state the only one which was processed instead of telling that it had "invalid input"?

        If there are other ones it will be harder to rejudge manually.

        Is it efficient to rejudge only the hack states that successfully passed? so it will detect the wrong tests.

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

When will the system tests start?

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

When will halyavin finish testing us?

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

Why the FUCK are the ratings not updated still??

I could have asked politely but the system testing has been over for over 4 MOTHERFUCKING HOURS and i am going FUCKING CRAZY !!!!

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

E — Connected Components?

is it possible to use dfs instead of bfs here ? Solution Accepted

if possible then why i get WA when I use dfs here in the following code WA using dfs


shortly my idea: i insert all node from 1 to n in a set/vector then remove it one by one when they are visited by using dfs/bfs.

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

I think the data of problem E in Test#85 is wrong. In the description of problem E, you said " Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test). ", but it seems both (3, 6) and (6, 3) are in Test#85.

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

For problem E, My Submission I am getting Time Limit exceeded. Can anyone please help me where I am going wrong?

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

wrong thread i am sorry ):