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

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

1282A - Абонент временно недоступен

Идея: MikeMirzayanov Разработка: MikeMirzayanov

Разбор
Решение (MikeMirzayanov)

1282B1 - K по цене одного (простая версия), 1282B2 - K по цене одного (усложнённая версия)

Идея: MikeMirzayanov, unreal.eugene Разработка: Supermagzzz

Разбор
Решение (Supermagzzz)

1282C - Петя и экзамен

Идея: AdvancerMan Разработка: Supermagzzz

Разбор
Решение (Supermagzzz)

1282D - Заколдованный артефакт

Идея: unreal.eugene Разработка: unreal.eugene

Разбор
Решение (Darui99)

1282E - Тортик - ложь

Идея: MikeMirzayanov, AdvancerMan Разработка: AdvancerMan

Разбор
Решение (AdvancerMan)
Разбор задач Codeforces Round #610 (Div. 2)
 
 
 
 
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

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

Could anyone explain why the problem D answer for the below case is 1?

6 17 2 6

0 0 1 0 0 1

7 6 3 7 10 12

When can the student leave to get 1? If the student leave T=6, he can solve 3th problem, but the 2th problem makes his score 0. Am I missing something?

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

    Petya could solve one of easy problems and leave exam at time 2.

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

    In this case, you should prioritize easy problem over hard problem, which takes exactly 2 minutes.He can leave immediately when he solve a easy one at t=2.

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

    Actually, it's problem C, not D.

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

Solution to problem B is not very clear yet. Can someone please explain it in little more detail?

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

    Sort the items by price. Let us say we wanted to buy only all of the first i items by paying the minimum price possible, call this minimum price needed dp[i].

    If i >= k-1 (0 based index).

    We will definitely have to buy the most expensive item but on purchasing that we can get items from i-k+1 to i-1 for free.

    So dp[i] = cost of item i + dp[i-k]. If dp[i] <= budget, our answer is atleast i+1.

    If i < k-1 the case is simpler, check the code for this case.

    Also if there are n items on sale, there is no point of purchasing an expensive item but leaving out a cheaper one. In essence if you buy some ith item you will definitely buy first i-1 items also. Let me know if you'd like a proof for this too.

    https://codeforces.com/contest/1282/submission/67533829

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

      Thanks , for the explanation. Can you also explain what is said in the editorial,I think it's a little different from this(dp) approach?

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

        I feel it's almost the same.

        Not sure though.

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

        dp is kinda parallel counting for all possible prefixes, while solution from editorial is serial: try first prefix, then run with step k; try second prefix, then run with step k, and so on.

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

      Wanted to ask that for i=1 to k-1 (in ur case: 0 to k-2), we can't apply the offer bcz. we don't have exactly K items to buy. So, in that case shouldn't it be 1 item(not applying the offer). Your code looks like that we can buy less than K items. Can you clarify if we can buy less than K items or not?

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

        We can definitely buy a single item without using the offer. If you buy say g items, g < k, then you have to pay sum of individual cost of those items equivalent to buying each of them one at a time without using the offer.

        In my code dp[i] where i < k-1 is simply the prefix sum.

        Let me know if this clears your doubt.

        You have both the option of applying the offer or not applying it.

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

          can you explain more how offer is used and not used in both the conditions (i >= k-1 and i < k-1 )

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

            You may only use the offer if you buy exactly k items. Say K=5, you want to buy 7 items, you can buy 2 items individually without using an offer and 5 items on offer. Not sure what exactly you are trying to ask but still hope it helps.

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

      t=1 n=5 p=6 k=2 A=1 2 4 5 7

      for this case if we buy price of 5 we have {5,4,1} as purchased items and the optimal buy would be {4,2,1} ,here both types of purchase are optimal.So how can we be assured of the fact that higher purchase will not lead to best result

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

      if dp[i]=min cost to buy first I items,how is it that that is the optimal way to buy max no. of items? I understood your dp, but I would like to have a proof. My dp is quite poor.

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

My solution for problem E is similar but definitely much shorter, the main idea is to take an arbitrary triangle to remove it and recursively solve on the three sides, I have a list with the order of vertices and other for the order of triangles, in my recursive function I have a fixed side(edge) then I find one arbitrary triangle with that edge and solve similarly for both sides

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

I have another approach for $$$D$$$.

Assume length of $$$s$$$ is $$$l$$$. First, query with $$$t$$$ = "a" and let the response be $$$r$$$. There are 2 cases:
1- string $$$s$$$ consisted only of "b" letters, then $$$l = r$$$.
2- string $$$s$$$ had at least one "a" in it, then $$$l = r + 1$$$.

Now query with $$$t$$$ of length $$$r$$$ consisting only of "b" letters and let the response be $$$e$$$. If $$$e = 0$$$ then terminate, otherwise, You have 2 pieces of information:
1- $$$l = r + 1$$$.
2- The distance between string $$$s$$$ and string full of "b" letters of length $$$l - 1$$$ is $$$e$$$.
3- $$$s$$$ has at least one "a" in it.

Now, let $$$t$$$ be a string of length $$$l$$$ of only "b" letters. The distance between $$$t$$$ and $$$s$$$ is also gonna be $$$e$$$ (I think the only case where this is not true if string $$$s$$$ consists only of "b" letters, which we know it already doesn't. Would love a proof for this tho).

Now just like the rest of the solution in the editorial, iterate over $$$t$$$ from $$$1$$$ to $$$l$$$ and try to turn the character to "a" and query. If the distance in the response is less than $$$e$$$, then update $$$t$$$ and $$$e$$$. keep doing this until the response is $$$0$$$

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

For the question, Price of one easy version i tried to solve it using modification of knapsack but it gave tle on pretest 3. Did i miss something, code is as below:-

private static int getMem(int[] a, int n, long w, Map<String, Integer> map) {
    StringBuilder sb = new StringBuilder();
    sb.append(n).append(":").append(w);
    String key = sb.toString();
    if (map.containsKey(key)) return map.get(key);

    if (n <= 0 || w <= 0) {
       map.put(key, 0);
       return 0;
    }
    if (a[n-1] > w) {
       int value = getMem(a,n-1,w, map);
       map.put(key, value);
       return value;
    }
    else {
       int d = Integer.MIN_VALUE;
       if (n-2 >= 0 && a[n-1] <= w) {
         d = 2;
       }
       int val = max(1+getMem(a,n-1,w-a[n-1], map), getMem(a,n-1,w, map), d+getMem(a,n-2,w-a[n-1], map));
       map.put(key, val);
       return val;
    }
}
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Note i sorted array before calling this method.

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

    You can optimize this to linear time, since the values of all of the items are equal. For example, since an item with cost 10 and another with cost 5 are always equal value, you always want to take the one with the smaller cost.

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

In solution to problem B, the sort function is used which takes o(n*log(n)) time complexity. So how come the solution has linear time complexity? Please explain!

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

    It is not, but since the $$$a_i$$$s are only from 1 to 10^4, we can use radix sort or counting sort to sort the numbers in $$$O(10^4)$$$ time

    Update : As the number of testcases is large($$$10^4$$$), so it won't probably pass, so nevermind, just use quicksort.

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

      but the editorialist solution uses builtin quicksort function brother

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

        We can do, the solution is not linear though, it indeed is $$$O(nlog n)$$$

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

      It will take 10^4 iteration per test case,which will give worse time complexity than nlogn.

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

        Not at all, it would give us $$$O(10^4+n)$$$ time which is linear in n

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

          It will surely take O(10^4) to sort the array per test case, and total no test case can be max 10^4. so here worse time complexity is O(10^8) which is worse than nlogn.

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

      radix sort is $$$O(n \log(A))$$$ where $$$A$$$ is logarithm of number of possible values. counting sort is $$$O(n)$$$.

      You can do $$$O(n)$$$ here, but I came up only with offline solution. It's useless.

      Here is comparison:

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

Someone Please Help me Correct my Solution For Problem B. I am unable to find which case I am missing . It would be of great help. My Solution :- (https://codeforces.com/contest/1282/submission/67578229)

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

    PROBLEM B

    Can someone Please Explain this Test Case?

    4 9 2

    2 3 4 5

    How the answer is 4?

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

      You can buy goods worth 4 & 5 for 5 coins and goods worth 2 & 3 for 3 coins.Hence answer is 4

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

      As we can take 2,3 as one pair and 4,5 as another pair so re money is max(2,3)+max(4,5) i.e. is 8 which is less than 9 so we have one unit of money left.. Since we have no other toy this is our final ans;

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

      First buy 5 and then you get 4 for free and then buy 3 you get 2 for free so total cost = 8 but you have 9 and so you buy 2 goods and get 2 for free

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

Could anyone explain problem B in more detail

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

My submission for C giving WA. Someone please help!! Edit:: I think I got my mistake..

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

B1 easy version

include<bits/stdc++.h>

using namespace std;

define ll long long

int main() { int t; cin>>t; while(t--) { ll n,p,k; cin>>n>>p>>k; ll arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; sort(arr,arr+n); ll cnt=0; ll val=p,l; int f=0; for(int i=0;i<n;i++) { if(p>=arr[i]) { val=p; p=p-arr[i]; cnt++;

       l=i;
    }
    else if(val>=arr[i])
    {   val=val-arr[i];
         cnt++;
    }
    else
    {
       break;
    }
}
//cout<<val<<endl;


    cout<<cnt<<endl;
}
return 0;

}

why my code is giving wrong ans .

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

    1) Check the language setting of your comment -- it does not show up in English version of the website.

    2) Please, do not paste the code in the comments, use [submission:67556497] instead. If it is a small piece of code, use "block" style (or manually surround the snippet with ~~~~~).

    3) Look at the test case output. It says wrong answer 26th numbers differ - expected: '4', found: '3', meaning that you fail the 26th test in the second test case. Find that test and go through your algorithm with it. Do what you can before asking others, this will help you to realize why your are wrong next time you come up with a similar algorithm.

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

In problem C, why is the answer of this testcase $$$1$$$ ?

1
6 17 2 6
0 0 1 0 0 1
7 6 3 7 10 12
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For the first problem(temporarily unavailable) in the fifth test case a=-10 b=20 c=-17 r=2 , the coverage will be from [-15,-19].so a to b must added, the answer must be 31, if I'm wrong case someone explain why I'm wrong.

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

    The time taken to travel from a to b is 30 units right? Cause you travel from 0 to 1 in 1 unit time

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

Please find the error in my code i don't know what's going wrong here My Submission for Problem D

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

For Problem B. first sort all the goods by its price.and take this array as p[]; then let f(x) means the least money he should pay to buy first x goods. so if x <= k , f(x) = f(x-1) + p[x] if x > k , f(x) = min(f(x-1) + p[x],f(x-k) + p[x]) // use offer or not then iterater all the f(x),find the most x satifies f(x) <= the money I have. does I make this problem more complex?

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

Задачу B можно решить одномерной динамикой, если считать, что dp[i] — минимальная сумма, за которую можно купить i подарков. Потом можно просто перебрать массив dp и вывести такой индекс i, что dp[i] <= p и i максимален. И да, для него тоже нужно сортировать массив.

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

problem b order is $$$O(N^2)$$$ ?

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

can someone explain C approach briefly?

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

In tutorial of problem 1282D - Enchanted Artifact:

Consider an arbitrary string $$$t$$$ of length $$$l$$$ and let the answer to its query be $$$q$$$. Then if we replace the letter $$$t_i$$$ with the opposite one (from a to b or from b to a), then we may have one of two situations:

  • $$$q$$$ decreased by $$$1$$$, then the letter $$$t_i$$$ after the change coincides with the letter $$$s_i$$$.

  • otherwise the letter $$$t_i$$$ before the change matches the letter $$$s_i$$$.

I think that this is not truth. For example:

$$$s=$$$ abababababababababab

$$$t=$$$ babababababababababa

Edit distance is $$$q=2$$$ (delete the first character and insert the last one).

Let's replace some a in the middle with b (the letter $$$t_i$$$ after the change coincides with the letter $$$s_i$$$):

$$$t'=$$$ bababababbbababababa

Edit distance is $$$q'=3$$$ (replace this letter, delete the first character, and insert the last one).

The letter $$$t_i$$$ after the change coincides with the letter $$$s_i$$$, but $$$q$$$ didn't decreased by $$$1$$$.

Am I right?

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

    does the author means the t is all letter 'a' at first.
    so it can't be babababababababababababa it can only be babababababaaaaaaaaaaaaa so convert from a to b will make difference?

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

      Maybe, but he didn't write it.

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

        but in his codes, he inits the t in this method. so maybe this is what he actually means.

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

      BTW, how can this be proved?

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

        I think because the s and t has same length. So the quickest way to transform from t to s is to replace each a to b where the char in them are different. if a change from 'a' to 'b' make the distance greater(we need more step to make make t equal to s cause our change), it means this position should be 'a', otherwise, it should be 'b'.

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

    You are right. Actually, these statements are not true in general case, but they are valid if your initial string $$$t$$$ is monochrome (consists of letters of a single type) and has the same length so as $$$s$$$. Moreover, it is valid when string $$$t$$$ has a common prefix with $$$s$$$ and the remaining part is still monochrome. It is also can be proven (by induction I guess) that during these actions deletions and insertions are not necessary operations, because what can be done with these operations can also be done with changing letters in no more operations. I'll make the editorial more clean to understand soon.

    Additionally, it looks like when we are increasing a valid prefix in string $$$t$$$ on an initial monochrome string, the edit distance is actually equal to the Hamming distance.

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

      Can you prove these facts or post a link to the proofs for the same, as proving things is as much necessary in a contest(especially for greedy problems) as is intuition?

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

    Yeah I think you are right, take this case also: Edit distance between (aaaa , baba) is 2. The edit distance between (abaa , baba) is also two.Even though only one character has been changed from a to b.

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

Could anyone explain why the solution of problem C answer for the below case is 2?

3 5 2 100

0 0 1

5 5 5

If student leave at 5, he must solve all the problem. Am I misunderstanding?

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

    he can leave at 4, solve problem 1 and problem 2, which costs 4 minutes.he doesn't need to leave at 5

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

    If he leaves at 0, then he will receive 0 points. If he leaves at 1, then he will receive 0 points. If he leaves at 2, then he will receive 1 point for solving an easy question. If he leaves at 3, then he will receive 1 point. If he leaves at 4, then he will receive 2 points for solving both the easy questions. If he leaves at 5, then he will receive 0 points because all the problem becomes mandatory and solving a hard problem takes 100 minutes and You don't have that much time.

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

In problem B2:

t = int(input())
for _ in range(t):
	n,p,k = map(int , input().split())
	a = list(map(int , input().split()))
	a.sort()
	
	ans= 0
	pr = 0
	for i in range(k+1):
		s = pr
		if s>p:break
		cnt = i
		for j in range(i+k-1,n,k):
			if s+a[j]<=p:
				cnt+=k
				s+=a[j]
			else:break
		pr += a[i]
		ans = max(ans , cnt)
	print(ans)

This code is giving runtime error in Test case 2 I know that error is in line 9 for i in range(k+1) but this is similar to the solution provided. What is the reason that this code gives AC in c++14 but RE in pypy3.6 ?

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

In Problem C, can anyone please explain the code after l is declared. I know we need to increase the count as the question becomes mandatory but I am unable to figure out the code. Kindly help.

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

can someone please explain me 8th no test case of 1282C — Petya and Exam if he do the first problem then s=6 which is equal to next ti,so then he have to do next problem because it became mandatory then, so how the answer is one,it should be zero my solution is 67599856

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

explain test case no 8 of 1282C — Petya and Exam how it is 1 it ans should be zero

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

I am getting WA on test 2 on C.

https://codeforces.com/contest/1282/submission/67600070

Can Someone Please Help.

Thanks

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

    instead of starting from the beginning, I have for once solved all the questions and then am deciding from the end, If the solution is permissible or not(depending on time limit, and if the next question is mandatory within that limit)

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

Based on your editorial of problem E, I think one can do simpler things to solve the problem:

  • To find $$$q$$$, consider the fact that whenever we cut off a triangle, we lose a vertex, i.e., it no longer appears in any further triangles. So, simply maintain the frequency of all the vertices (the no. of triangles it appears in) and also the triangles that contain the $$$i$$$-th vertex. At every step, choose a vertex that has a frequency of $$$1$$$, and cut its corresponding triangle.
  • To find p, consider every triangle. It has $$$3$$$ edges. Since only a single edge corresponds to the vertex of the polygon, and it appears only once in the input, we construct a graph on n vertices. We compute the count/frequency of all the edges in the input and for all edges $$$(u - v)$$$ that have a frequency of $$$1$$$, we add an edge $$$(u - v)$$$ in the graph. Now, the graph will be in the form of a simple cycle corresponding to the order of the vertices in the polygon. So, simply perform a dfs to find $$$p$$$.

Here, we have found $$$p$$$ and $$$q$$$ independently.

Code: 67604806

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

    can you explain the steps to implement first part(to find q) of your exaplaination .I got what you are saying but i am not able to understand how to implement it efficiently.

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

Can anyone explain the problem A please? I am really confused on that.

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

I dont get why the answer to test case 8 of problem c is 1 and not 0. In that test case the problem with lowest mandatory time is the third one, so if we want to solve one or more problems we must solve this one, but because the time it takes to solve this problem is 6 seconds, and there is a problem which its mandatory time is 6, we can not solve the third problem without solving this one or getting a zero score.So why is the answer to this test case 1? I am probably missing something here but i cant figure it out. Can someone please help me? edit* I found out how it can be 1.

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

queryforces

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

Please someone could explain to me the intuition behind the problem D.

I am not able to understand how the query is coming and how we to find the spell(string) using t(string) and query of edit distance.

In fact, I am not clear with input.

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

My soln. is similar to one which is mentioned in editorial and it is passing for problem B1 but failing for problem B2. I am not able to find out the mistake. Please help.

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

please, can anyone tell me that why in b2 editorial solution first loop run upto only k ? why ? please, anyone reply guys.

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

    Because if you buy greater than $$$k$$$ items without using the offer, you would spend more money, rather buy $$$k$$$ items using the offer and buy others individually.

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

For me personally, finding permutation of vertices was far easier than finding an order of cuts.

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

Do I have correct idea for problem E?

https://codeforces.com/contest/1282/submission/67669011

Idea:

Store vertices like graph. 1 piece = 6 new edges. Sort vertices by number of neighbors. On each step poll vertex V with smallest number of neighbors. V must have only two neighbors. Delete V from its neighbors. Add these two neighbors back to priority queue. Repeat while there wont be only two vertices.

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

Why does the link to the editorial of this round appear twice? https://codeforces.com/contest/1282

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

Can someone figure out what's wrong with this solution for D? 67670033

It has a similar idea as given in the tutorial.

unreal.eugene

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

Nice testcase 67 in D.

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

why is my answer for problem E got wrong answer

Input
3
6
3 6 5
5 2 4
5 4 6
6 3 1
6
2 5 6
2 5 1
4 1 2
1 3 5
3
1 2 3
Participant's output
1 3 5 2 4 6
3 1 4 2
1 4 2 6 5 3
1 4 2 3
1 2 3
1
Jury's answer
1 6 4 2 5 3 
4 2 3 1 
1 4 2 6 5 3 
3 4 2 1 
1 3 2 
1 

I think it said clockwise or counter clockwise

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

-3 1 2 0 how is the answer to this query for problem A 4?shouldn't it be 5? while travelling : -3 -2 -1 0 1 ,nowhere is tower signal available.

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

    same Confusion!! Did you find the answer?

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

      I got the idea. We need to count distance and not number of points. So, -3 to -2 -> 1 -2 to -1 -> 1 -1 to 0 -> 1 0 to 1 -> 1. So, answer is 4.

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

        Well if that so in this test case answer should have been 6 : 1 10 7 1 : as, 1->2,2->3,3->4,4->5,(available for 6,7 and 8)8->9,9->10.

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

anyone please explain B2 in Recursion DP <3

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

Could anyone help me to see why I got RE? TIA! 68362298

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

I doubt that the checker of Problem D calculates incorrect Edit Distance when $$$|t|>|s|$$$ because 68363205 got WA on test 1. Can anyone help me about this? Thanks.

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

In problem b2 for test case : 5 2 3
10 1 3 9 2

should the answer not be equal to 2 as by buying the element with cost 2 we could also buy the element with cost 1 i.e buying element of cost 2 and getting the element with cost 1 as free.

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

    Note that the announcement says: You must buy exactly k gifts to use the offer. So the answer is 1.