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

Автор vovuh, история, 5 лет назад, По-русски

UPD: Спасибо Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву и Артему Rox Плоткину за помощь с подготовкой раунда!

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

<almost-copy-pasted-part>

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

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

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

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

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

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

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

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

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

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

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

I wish you all good luck

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

hope this contest becomes my last official participation in DIV3.

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

I hope become pupil

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

Good luck to everyone. I hope this round will be an exciting contest without dots attacks and lots of hacks. Finally I hope the problems will be solvable and understandable.

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

Div-3 is Love... True Love... Pure Love...

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

Love Vovuh's Contest

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

Fitness challenge: I'll do one pull up for every rating point lost and I'll do 3 pushups for every point won. Feel free to join the challenge under your conditions.

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

I think you should take part in some contests to become master. It's more beautiful ^^

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

Why Div3 get so little upvotes :(

Are we just used to them?

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

Which problem has two subtasks? @vovuh

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

    Look, I really don't think it is important information before a round. I prefer vovuh will spend time improving problem statements and tests.

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

Why do Vovuh conducts only Div.3? I don't like him.

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

Hi! I decided to simplify one of the problems and divided it into easy and hard versions. That's why I increased the round duration to 2:15. Don't afraid of formally too many problems in the round. You shouldn't think about easy/hard versions as about two independent problems. And good luck!

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

    Very good idea to divide problems into parts. Sometimes, even after solving the problem, it requires additional data structures or optimizations. This way even partially correct solutions that are slower than intended get partial points.

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

      Another idea is creating one problem with different types of tests. Solutions can first get tested on small tests, and then on bigger numbers. And if it passes small tests, contestant can get partial verdict. This has been done in several rounds, to it is possible. It is just easier to navigate this way, instead of solving 2 same problems

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

I will AK this contest !

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

Vovuh, the half-quarter!

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

Good luck!

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

I want to improve myself~

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

There's an expert participant in the trusted participants rankings, by the way.

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

Contest is over. It was a good contest.

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

I solved 7 problems for the first time. Feel amazing >__< !!

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

    I solved 6 but still. Which 6 did you solve?

    I didn't solve D1, D2 and F. Is D1 just straight bruteforce? I didn't try because it seems like it'll be something like O(n^4) :(

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

      I believe you can see his submissions

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

        Oh ye. Problem E is awesome, I tried a dp-greedy method and it worked. I can't even convince myself that it is true, but complexity-wise it passed.

        dp[i][elevator?(bool)] = Minimum total time to reach ith floor, with last move taking the elevator (or not, depending on the bool)

        dp[1][false] = 0, dp[1][true] = c

        dp[i][false] = min(dp[i — 1][false], dp[i — 1][true]) + a_(i — 1)

        dp[i][true] = min(dp[i — 1][false] + c, dp[i — 1][true]) + b_(i — 1)

        output *(min(dp[i]) for i in range(1, n + 1))

        Can someone prove this .-.

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

      Ummm I used Segment Tree with Lazy Propagation for D1 & D2. (Segment Tree is really useful >__<!!

      But I think there will be more easy way (maybe)

      I thought adding Persistent Segment Tree for D2 at first, but I'm so scared to coding it, fortunately it was solved by priority_queue.

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

    I solved 7 problems too. I wish this contest is rated.

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

Can somebody explain test case 2 in F?

Thanks

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

How to solve C2 ?

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

    It's just ternary numeral system.

    My solution:

    precalculate all values 3^n (0..38 powers), it's 100..000 preseentation of number

    next I check first X that 3^0 + 3^1 + ... + 3^X (presentation of 111..11) >= n, if yes subtract from n 3^X, and add to result same number

    do while n > 0

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

      What about n = 10^18? In the first test the answer is 1350851717672992089, but 3^38 > 10^18 and less than test's answer

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

        You are correct (10^18 — 3^38) < 0 and loop stopped.

        But first I compare with (3^39-1) and subtract (3^(39-1))

        upd: sorry, not 3^X-1, but 3^0+3^1+..+3^X and if this value greater or equals than n I subtract 3^X from n and add to result

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

How to solve D2?

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

    I solved it using line sweep algorithm. Iterate through the points [1,2e5]. Keep a set that includes current line segments. Whenever you find a condition where the number of line segments exceeds k in the current set, remove the line segments which have higher ending point.

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

What was test case 14 of D1?

Also, how where you supposed to solve D2? I thought using a BinaryIndexedTree, but I wasn't sure how to implement.

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

What is Test 11 for Problem E?

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

Isn't Meet in the Middle expected solution for C2. My solution got TLE on test 7

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

I solved only 2 problems. Will my rating will increase or decrease? The problems were easy but I couldn't cope up with the constraints leading TLE

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

How to solve F?

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

    dp on tree

    dp[i][j] is the max sum can be obtained from the subtree of vertex i

    with the nearest picked vertex from this subtree is at distance j from vertex i

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

I think this round is easier usual Div 3 round.

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

Any Penalties on Unsuccessful Hacking Attempts?

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

The moment I realized that the comparator used by me is wrong in D1/D2 after printing all the values for an hour...........

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

Anyone tell me why this code gives TLE? 63189145

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

What's wrong with this solution for F — dp[node][level] = answer for subtree rooted at 'node' such that among all selected nodes the smallest depth is at 'level'? This recieved WA-3

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

After seeing constraint I thought greedy won't work for C2 so wasted one hour to implement Bit Mask+ Meet in the middle.Lesson learned. -_-

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

My solution for $$$F$$$:

Root the tree at node $$$1$$$. Let $$$dp[i][j]$$$ be the maximum subset weight for the sub-tree rooted at node $$$i$$$ if the nearest node in the subset to $$$i$$$ is at distance $$$j$$$ from it. Let $$$mxdp[i][j]$$$ be $$$max(dp[i][k])$$$ for $$$k$$$ from $$$j$$$ to $$$n$$$.

How to fill $$$dp$$$?

$$$dp[i][0]=a[i]+\sum_{c}mxdp[c][k]$$$ where $$$c$$$ is every child of $$$i$$$.

$$$dp[i][j]$$$ (for $$$j$$$ from $$$1$$$ to $$$n$$$) $$$=max(dp[c_1][j-1]+\sum_{c_2!=c_1}mxdp[c_2][max(k-j,j-1)])$$$ where $$$c_1$$$ is every child of $$$i$$$, and $$$c_2$$$ is every other child of $$$i$$$.

The answer is $$$mxdp[1][0]$$$.

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

In D why remove segments from longest to shortest length is wrong?

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

    Imagine three segments [1, 1000] [1001, 2000] and [1000, 1001] and k = 1. There are two points that have k = 2 : 1000 and 1001. If you remove longest segments, then you will need to remove both of the big ones. In another case, you can just remove the third one and m = 1

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

Сложные у вас задачи в Div 3, несколько лет назад такие в Div 2 давали. F точно лишняя, да и D и E далеко не подарок, если за новичка катать. Может, Div 4 надо делать?

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

    Толсто, чел. Между делом, я помню, что ты как-то хотел сделать свой "образцовый" Div. 3, чтобы показать этим саратовцам, как их нужно делать правильно. И что-то я его до сих пор не вижу.

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

      Что толстого-то? Эти соревнования позиционируются как соревнования для новичков, а чтобы решать D и E с сегодняшнего, надо не меньше года заниматься.

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

        Толсто то, что ты не видишь корреляции между количествами AC в Div. 2 и Div. 3. Сколько ни занимался, почти во всех Div. 2 раундах закрывалось несколько официальных участников и около сотни-двух решало все задачи, кроме одной. Можешь посмотреть по ранклисту, что и в этом, и во многих других Div. 3 раундах именно так и есть. Неужели ты предлагаешь сделать Div. 3 такими, какими они были в самом начале, где закрывалось 600+ человек и про них начали говорить "о, очередной Div. 3, ну это изи 1600+". В чем смысл этой затеи и в чем проблема со сложностью сейчас?

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

          Мне кажется, что не круто, когда новичок впервые заходит в Div 3 и решает в нем 1 из 6.

          Отвечая на предыдущий коммент, я не хотел сделать образцовый Div 3. Его уже сделали, смотри: Codeforces Round 481 (Div. 3)

          А если человек решает в "изи 1600+" раунде все задачи, почему бы и не дать ему эти 1600?

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

            Ладно, возможно, у меня уже едет крыша, но я почему-то помню предложение то ли от тебя, то ли от кого-то другого, что "я сделаю нормальный Div. 3 и залью его в тренировки". Но это не важно.

            Если новичок приходит на раунд и решает одну из шести, учитывая, что задача B1 из сегодняшнего раунда — это задача "просто напиши хоть как-нибудь то, что сказано в условии", то, может быть, ему стоит задуматься, правда ли он знает хотя бы основные конструкции языка? Потому что единственное, что нужно было, чтобы сдать B1 — это знать циклы и массивы. Тогда, возможно, это должно мотивировать становиться лучше, чтобы решать хотя бы те задачи, в которых просят просто написать.

            Видимо, ты хочешь превратить сайт с олимпиадными задачами по программированию (часть сайта) в курс "научись писать хоть какой-то код"? Какой в этом смысл?

            И чем раунд, на котором закрывается 200 человек, а еще 300 решают все, кроме одной, так хорош, когда он почти никак (кроме скорости печатания) не может отделить топ-500 участников друг от друга?

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

Is there anyone else, who used meet in the middle in C2. my solution

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

how to solve B2?

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

    use dfs, to travel continuously until u get end point of cycle.then update all the travelled value to max distance you have travelled until now.see my code.submission

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

    You could use disjoint sets too... Just put i and arr[i] in same set (union) and like size find size of each set, the answer is same for all the elements in the same set, ie, size of the set.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
 ll n;cin>>n;ll temp=n;
        int idx=0;ll mn_diff=LONG_MAX;
        while(psm[idx]<n)idx++;
        // dbg(pt[idx]);
        for(int cnt=idx;cnt>=0;cnt--,idx--){
            mn_diff=min(mn_diff,pt[idx+1]-n);
            if(n>psm[idx])break;
            if(n>=pt[idx])n-=pt[idx];
            if(n==0)mn_diff=0;
        }
        cout<<temp+mn_diff;nl;

i was getting wrong answer using mn_diff=LONG_MAX, is it wrong to use LONG_MAX for std::min function in c++, but also it gave correct answer on my compiler.

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

    LONG_MAX gives you a "long long" value, but you are storing it in an "int".

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

    UPDATE :: never use LONG_MAX on codeforces as LONG_MAX is same as INT_MAX on Windows, and codeforces uses 32 bit windows, so always use LLONG_MAX it is universal (2^63-1).

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

For problem E, could anybody tell me why PyPy 2 TLEs but PyPy 3 ACs?

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

My approach for problem D1 is keep removing the segments intersecting with maximum number of bad points .Is this approach correct ? My submission is giving wrong answer though My Submission

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

    I got WA on 9. Switched to iterate from left to right on bad points and keep removing segment with largest end point, and that passed.

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

      Your approach is also nice.Still wondering what is wrong with our first approach .

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

        I found out whats wrong.

        Take the following case

        5 1
        1 2
        2 5
        3 10
        7 14
        14 15

        Here if we try deleting segments with most bad points, we will first delete 3 10, then 2 5, then 7 14. But the correct approach is to delete 2 5, and 7 14.

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

Hack case for B?

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

The problem-set contained better stories than all of my films combined.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to prove this solution ?
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C2

	// Wrong Answer 
	/*
	for(int i = 0 ; i < 40 ; i++){
		my[i] = (int)pow(3LL,i) ;
	}
	*/
	// Accepted Solution 
	my[0] = 1 ;
	for(int i = 1 ; i < 40 ; i++){
		my[i] = my[i-1] * 3LL ;
	}
	//

This is my AC Code 63196491

what is wrong with this line my[i] = (int)pow(3LL,i) ;

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

    Overflow, my[i] can be greater than INT_MAX

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

    pow returns double, which can't represent all values of a long long (think about it: both are 64 bit types, therefore pigeonhole principle etc etc)

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

    I could suggest you one thing, if I may.... Don't use inbuilt pow function, it's very deceptive sometimes..... Just to be on the safe side, you could make your own pow function using fast exponentiation....

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

    pow(x) returns double, which is not enough for 1e18. Try using powl(x), which returns long double instead.

    P.S. Both pow and powl are inaccurate, try to avoid using them

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

thanks for this amazing contest:)

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

thanks for this amazing contest :)

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

Sorry for my bad english, but the user named AHR9N has cheated, he asked me for the code of the problem B2, but I did not send. I think he needs to be severely punished

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

Oh,I can't get problem c2,problem c2 and problem e by using m2.codeforces in this contest. It told me that the statement is available.

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

Can anyone give me the solution of Problem B2 using DSU?

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

In question https://codeforces.me/contest/1249/problem/A A. Yet Another Dividing into Teams from equation it means that difference should not be 1. Statement says difference should be strictly greater than 1. And test cases are aiming just for difference not equal to 1. There is a bit ambiguity . As for input 1 1 1 1 1 1 Answer should be 5. In test cases answer is either 1 or 2.

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

    All students have distinct programming skills!

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

    The second line of the query contains n integers $$$a_1,a_2,…,a_n$$$ ($$$1≤a_i≤100$$$, all $$$a_i$$$ are distinct), where $$$a_i$$$ is the programming skill of the i-th student.

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

Is the round unrated? Why the ratings are not updated ?

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

    Cause you are not rated in this round. You have to participate at least 3 contest in div2.

    and your solution was skipped-- probably you have break any Terms of agreement of codeforces.

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

Problem F is basically the same as BOI 2017 day 2 "Cat in a tree"

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

Edit: I was mistaken, please ignore.

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

    No, distance between any pair of selected vertices should be greater than k

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

      Oh right, I misread the prose in the problem description and thought there was a contradiction.

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

If I modify problem A to..like find minimum number of teams you can form if no two students i and j such that |Ai-Aj|<=k may belong to the same team (i.e. skills of each pair of students in the same team has the difference strictly greater than k).
So if N be the no of students then I can solve it in O(NlogN + Nk^2). is there ant faster approach if any one can suggest???

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

    Maintain a sorted array. Pick the first element(lets say a), then find the upper bound of a+k. Keep on doing the same thing for this new element until you reach end of array and also maintain the elements which have been allocated a team. Pick the next element in the sorted array which has not been allocated a team yet and repeat the above steps and increment the number of teams. This approach should be O(NlogN).

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

      No worst case complexity of your idea is O(N^2) Consider the case of N consecutive numbers with k=N;

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

        How?

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

          just apply your idea and see... pick your a(first element of sorted array) in search of a+k (i.e. a+N here) you will traverse the whole array(end of array) but you will not find it.. Note1 you have picked just 1 element in 1 traversal do same for 2nd, 3rd and so on... so N(N+1)/2... O(N^2)complexity……. also Note2 you can't say here for this very case to use binary search(however here may work) bcz in general solution binary search will not work.

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

            I won't traverse the whole array. I would just binary search and why would it not work in general?

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

              not work means complexity will become even worst bcz at every such a+k you need to do binary search prev=a; curr=a+k; next a+k+k;..... so on and every time cost is logarithmic time. Also there might be case that a+k doesnot exist but a+k+2 or a+k+5 exist here these will be included in the same partition but then how you will handle those cases using binary search.... Just think once what is your complete idea and check the complexity... once done I will be thankful and love to know that.

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

Why have the rating changes been temporarily rolled back ?

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

Stop naming test cases as "queries", ffs.

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

    This is not the first time you are saying this. But I don't think it makes any difference. It is okay until and unless it is not creating any confusion in the problem statement. Isn't it?

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

So when on earth can our rating be back?

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

I got plagiarism mail for the following solution coincided https://codeforces.me/contest/1249/submission/63187125 with another guy solution. However my first accepted solution for this problem was https://codeforces.me/contest/1249/submission/63184980. So the thing of plagiarism, I guess is completely irrelevant.

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

    Don't use IDEOne for coding.

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

      Is there any way to restore my credits for this round, I was unaware regarding Ideone thing.

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

        Try appealing to the problemsetters and the organizers. I tried a few contests back, didn't help. Now I only use my personal IDE.

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

Is it ok, what a few participants 1600+ rating got it updated after contest?

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

i try to solve D1 by using activity selection problem but it gives me WA on test case 14.

so i would do activity selection for K times and of course for each activity selection it will gives you as many as segments which not intersect with each other.

if you do it for K times then you will get points which covered at most K times, i couldn't think the corner case for my solution.

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

Can someone please check my F code. Its failing on the 38th case. https://codeforces.me/contest/1249/submission/73195435