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

Автор AdvancerMan, 3 года назад, перевод, По-английски

1263A - Sweet Problem

Idea: MikeMirzayanov

Tutorial
Solution (MikeMirzayanov)

1263B - PIN Codes

Idea: Stepavly

Tutorial
Solution (Stepavly)

1263C - Everyone is a Winner!

Idea: unreal.eugene

Tutorial
Solution (unreal.eugene)

1263D - Secret Passwords

Idea: Stepavly

Tutorial
Solution (Stepavly)

1263E - Editor

Idea: Supermagzzz

Tutorial
Solution (Supermagzzz)

1263F - Economic Difficulties

Idea: AdvancerMan

Tutorial
Solution (Rox)
 
 
 
 
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

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

Problem C can be done in O(√n) , I think. I just have a for loop 1->sqrt(n) and add 2 numbers to the list and got accepted :D

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

For Problem B a similar solution would be to consider a map for storing all the found pins while iterating through the list. Once it finds a pin that already exists in the map, randomly choose any position in the pin to replace it randomly with another digit. This repeats until we get a new 4 digit number. And this counts as a step.

Finally, print the step count and the new pins.

https://codeforces.com/contest/1263/submission/66044121

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

C can also be solved using the fact that $$$j = \left\lfloor \dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor }\right\rfloor$$$ is the largest $$$j$$$ such that $$$\left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor$$$.
65967376

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

Can anybody explain me logic of problem E. How it is done using segment tree?

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

    Suppose that '(' is 1 and ')' is -1, and others are 0. If the string is a correct text, these conditions will be satisfied:
    - The sum of any prefix should not less than 0 because that means the number of ')' is greater than '(' in this prefix.
    - The sum of the whole string should be 0 because the number of '(' and ')' should be equal.
    If the two conditions are not satisfied, the answer is -1.
    Otherwise, the answer is equal to the maximum depth of these brackets. It is equal to the maximum sum prefix because the sum of a prefix means how much '(' do not match with a ')' in the prefix.
    So we can use a segment tree to keep the sum of all prefixes and get the maximum and minimum sum prefix.
    My code: 66065668

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

      Thanks got it.

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

      Can you explain your solution a little bit. What is the use of tag.

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

        I use a segment tree to keep prefix sum array, so when I modify the $$$i$$$-th element in the original array, I need to update sums of prefixes that contain the $$$i$$$-th element. They are a continuous range $$$[i, n-1]$$$ in the prefix sum array, so we need to use lazy tag to do range updates. If the tag of a node is $$$t$$$, that means every element in the range should plus $$$t$$$, and the maximum and minimum value of the node should plus $$$t$$$, too.

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

      What's the time complexity? Is it n^2*log(n) ?

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

        No, the time complexity is $$$O(n \log n)$$$.
        The time complexity of doing a range update or range minimum/maximum query is $$$O(\log n)$$$. In my code, when I process a command, I do range update at most twice and range minimum/maximum query at most 3 times, so the time complexity of processing a command is $$$O(\log n)$$$. There is $$$n$$$ commands, so the time complexity is $$$O(n \log n)$$$.

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

How to solve problem E using lazy segment tree? :)

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

Stepavly How can I solve D using std::set ?

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

A different O(n) approach for E:

Maintain a prefix sum and store maximum and minimun in it.

Be lazy when the operation is L\R or when #( != #) (number of brackets).

when #( = #), update the prefix sum just in the range the cursor touched, amortize time is O(1) since L,R operations paid for each update in this range.

To maintain maximum and minimum store an histogram of prefixes.

solution: 66080615

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

    i was thinking in this way, but then i've remembered that i'm dummy and came with obvious segment tree solution

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

Sweet candies problem If we are given 8 2 8 candies, there is no possible way that we can eat it for 9 days. Can you tell me what is wrong in my approach?

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

    It is possible that we can eat candies for 9 days. One scenario for example would be that we eat 7 candies from biggest and medium piles i.e. 8 and 8 here. This can be done for 7 days. Then we are left (1 2 1) candies. Then eat such that the pile is (0 1 1) on the 8th day and on 9th day, it would be (0 0 0).

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

    IF U TAKE 1 CANDY FROM RED AND ONE CANDY FROM GREEN THEN IT REMAINS 7 1 8 AGAIN IF U TAKE GREEN AND BLUE THEN 7 0 7 ,,,2 DAYS GONE,,,HOW MANY DAYS U CAN TAKE TWO DIFF CANDY? YES 7 DAYS,,, SO 7+2=9!

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

In Problem A, how is the answer if r < g +b is (r + b +g)/2, what is the maths behind? Or is it purely observational?

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

    When the maximum number is less than the sum of the other two numbers, you can try to simulate this process. Use a priority queue to select the maximum two numbers from each time and subtract one. When this operation is completed, the maximum number is always less than the sum of the other two numbers until it becomes 0.00 or 0.01. The answer (B + G + R) / 2 mathematical induction can prove that my English expression is not very good I hope my answer will help you When the maximum number is larger than the sum of the other two numbers, answer is obviously the sum of two less numbers.

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

      Would please show the proof for the mathematical induction of (r+b+g)/2

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

        Suppose B>=G>=R, and B is less than or equal to G + R, When (B + G + R) <= 2, (when B G R is 1 1 0 or 0 0 0 respectively), the answer is (B + G + R) / 2 When (B + G + R) > 2, when we reduce B G by one, the maximum number of the answer plus one or three numbers is still less than or equal to the sum of the other two numbers, so we prove that. Above all.

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

Can anybody explain the Segment tree solution of E problem a little elaborately, I have read solutions of many people but couldn't decipher the logic of what they are trying to do. I know these things that the minimum sum prefix has to be greater than -1, total sum has to be 0 and maximum sum prefix would the answer, but how exactly are we computing this using a segment tree?

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

    Suppose you know that the total length of everything is n. Let each '(' to be a +1, each ')' to be a -1, and each regular character to be a 0.

    So for example if I have string (((a))), we get [1, 2, 3, 3, 2, 1, 0]. Notice that if we drop below 0 then we have an invalid string since there are too many ')'. The maximum amount of nesting is what we want to query, and that's just the maximum value on the segment.

    When we make changes we can just perform updates on segment. For example if I change from 'a' -> '(' at index i, then I just add 1 for all elements from [i...n], if I change from ')' to '(', then I have to add 2 for all elements [i...n]. Really we have range sum updates and range max/min queries which a straightforward use of segment tree

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

      Thank you so much, this explanation is crystal clear. But I wanted to ask you this that changing a a to ( is a point update so can't we do that point update and calculate the max prefix and min prefix sum using some other way? I thought of a way that we store totalSum, MaxPrefixSum and MinPrefixSum for each node, now for every parent thw updation would be something like parent.MaxPrefixSum = max(Left.MaxPrefixSum, Left.TotalSum+Right.MaxPrefixSum) And similarly for MinPrefixSum TotalSum would be updated directly.

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

Can someone explain Problem C, I am not able to understand the math

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

    The idea is that, given n, you need to iterate through all numbers i where (0<=i<=n) and see the result of dividing n/i and store it in a set.

    The optimization trick is to only iterate through i where (0<=i<=√n) and store both i and n/i in the set. So the time complexity is O(t√n). Here is my code: 65966154

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

Challenge Problem F completed:

The complexity of my code is linear. I only use algorithms like dfs, counting sort, monotonic stack.

My solution

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

please explain about B problem. I not getting What is logic.thanks.

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

(In the editorial of problem A)is the line correct? "Then we make equal the piles g, b by eating g−b from the piles r and b".

I think it would be-"Then we make equal the piles g, b by eating g−b from the piles r and g".

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

(In the editorial of problem A)Is the line correct? "Then we make equal the piles g, b by eating g−b from the piles r and b".

I think it would be-"Then we make equal the piles g, b by eating g−b from the piles r and g".

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

How to solve problem E with segment tree??? plz explain for me. thanks..

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

    Lets assume '(' = 1 and ')' = -1 and any other character is equal to 0. For each segment store the following things:-
    1. Number of opening brackets.
    2. Number of closing brackets.
    3. Maximum prefix sum and minimum prefix sum.

    For each iteration update the tree. The string is balanced if minimum prefix sum is positive or zero and number of opening brackets == number of closing brackets. Number of different colors (final answer) is maximum prefix sum. You can have a look on my submission.66222540

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

Tutorial for problem has a typo I guess: Then we make equal the piles g, b by eating g−b from the piles r and b.

Here it should be piles r and g I think. Correct me if I am wrong.

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

Can someone explain how to solve Div2-F. I am not able to understand the editorial. P.S- What is " the segment [l,r]", I am not able to understand it. Thanks in advance.

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

How to solve F by lowest common ancestor approach?

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

Can anyone please tell me where my approach of Problem B is wrong .

https://codeforces.com/contest/1263/submission/66242150

It's even showing the wrong answer on test case 1, which i can't seems to understand.

EDIT: Found my mistake !!

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

Can you tell me why for the input 8 9 10

output is 13, it should be 16.

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

    Tanya can't eat for $$$16$$$ days straight because the sum of piles' sizes is reducing by $$$2$$$ every day so she can't eat for more than $$$\left\lfloor \frac{8 + 9 + 10}{2} \right\rfloor = 13$$$ days.

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

For problem A, how can I prove this that if g+b>r, then the best possible approach would be to make the stacks equal?

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

"Очевидно, costl,l — максимальная длина «бамбука» l." cost l,l — это разве не максимальное количество, которое можно удалить? Тогда максимальная длинна бамбука — минимальное количество, которое можно оставить. Или я не понимаю чего-то?

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

    Поясню другими словами построение $$$cost_{l, r}$$$. Возьмем верхнее дерево. Пусть на отрезке $$$[l, r]$$$ все приборы должны иметь путь до корня нижнего дерева, а про остальные приборы мы ничего не знаем. То есть для всех приборов не из отрезка $$$[l, r]$$$ мы не можем сказать, должны они иметь путь до нижнего корня, или не должны. Тогда $$$upperCost_{l, r}$$$ — это максимальное количество ребер, которые мы можем отрезать в верхнем дереве так, чтобы для всех приборов не из отрезка $$$[l, r]$$$ был путь до верхнего корня. Аналогично для $$$lowerCost_{l, r}$$$. Тогда $$$upperCost_{l, l}$$$ — количество ориентированных вниз ребер, которые ведут в поддерево только с прибором $$$l$$$, а это как раз бамбук из листа $$$l$$$.

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

66304111 I am unable to see due to which part my code is exceeding the time limit for Question D, used simple DFS in my approach. Above is the submission link. Thanks in Advance :)

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

    It is because of the maps that you used to store the adjacency list and used vector. Instead of storing the strings in the adjacency list, you can assign an index for each string (most simply -> its index in the input string) and work with integers, rather than strings. This way, you get rid of an extra log factor and get accepted. If you need further help, you can check my submissions for the problem. This also happened to me.

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

How to solve D?

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

My submission is 66433037 and it's completely linear but it's giving me TLE for problem E?? Can anyone help me fix this? I've used a Stack of an object which is 4 generics, and all of my actions are push and pop and writing to an array; not really sure where I could clean this up; is there some Java structure I'm using which is particularly slow?

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

For D, 4 l k al ak Answer is 1. Can someone tell me how l and k are equivalent?

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

"for (string &pin : a)" what does this mean?

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

AdvancerMan isn't the recurrence given in F incorrect?

If you're using 0-based indexing it should be: $$$dp_i = \max\limits_{0 \le j < i}(dp_{j}+ max(upperCost_{j, i-1}, lowerCost_{j, i-1}))$$$, where $$$dp_0 = 0$$$.

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

I implemented it in the same way but get WA verdict. Someone please help 67183675

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

Can anyone provide me the code for the Binary Search version of the 1263C — Everyone is a Winner! problem ???

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

Can someone explain using binary search to find k in problem C ?

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

Hello AdvancerMan. I found that maybe the test cases for problem D are still not strong enough. For example:

3
cd
bc
ad

This case will output 1 for my submission 73597744, output 2 for my submission 73603502 , but both of the two submissions are accepted now.

I think the right answer should be 1. Do I have any misunderstanding?

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

    Hello! I've checked your solutions and you don't have any misunderstanding. Indeed answer for the given test case is 1.

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

i tried solving problem D with dsu but it is showing memory limit exceeded in test 6.I tried optimizing it but it is still showing the same problem.Please tell me how i can i optimize it to get it accepted. here is my code:

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

Hi, AdvancerMan

I get denial of judgement when upsolving problem F.

I even tried other's accepted code and it still crashes, please look into it.

https://codeforces.com/contest/1263/submission/84879747

The error message goes like this:

Test: #5, time: 0 ms., memory: 0 KB, exit code: 0, checker exit code: 0, verdict: CRASHED Checker Log

Generator is not determinate [the verification run produces different output, cmd =gen 1000 3 1000 2 1000 1 0 200 3 1000 2 1000 1 0 150], [16990 bytes, '1000

1244

1 970 1 1239 533 226 912 1 824 1 576 9... 1009 75 419 864 541 906 735 335 380 496 1097

', sha1=1ba04e177afba056927a2855f07e8327356b8113] vs. [16999 bytes, '1000

1244

1 970 1 1239 533 226 912 1 824 1 576 9...332 1164 609 569 742 895 1049 123 974 690 852

', sha1=40211f2f08ea2d3d7248b9d2960c5dd4cbd04154].

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

how to solve D with DSU I have solved it but getting wa

Spoiler

include

include

include

include

include

include

include

include

include

include

using namespace std;

define Fio \

ios_base::sync_with_stdio(false); \
cin.tie(nullptr);                 \
cout.tie(nullptr)

define f(i, n) for (long long int i = 0; i < n; i++)

define ll long long int

define fo(i, a, b) for (long long int i = a; i <= b; i++)

define w(t) \

int t;    \
cin >> t; \
while (t--)

define vi vector

define vl vector

define vvi vector<vector>

define vvl vector<vector>

define mii map<int, int>

define mll map<ll,ll>

define umii unordered_map<int, int>

define newl cout<<"\n"

define pb push_back

define mp make_pair

define fi first

define se second

const ll inf = 1e9 + 7; const ll modc = 998244353;

define MAX 500005

ll findparent(char a,ll parent[]){ if(parent[parent[a-'a']]!=parent[a-'a'])parent[a-'a']=findparent(parent[a-'a'],parent); return parent[a-'a']; }

void unionfind(char a,char b,ll parent[],ll size[]){ ll parent_a = findparent(a,parent); ll parent_b = findparent(b,parent); if(parent_a==parent_b)return; if(size[parent_a]>=size[parent_b]){ size[parent_a]+=size[parent_b]; parent[parent_b]=parent_a; }else { size[parent_b]+=size[parent_a]; parent[parent_a]=parent_b; } return; }

int main(){ Fio; ll n; cin>>n; ll parent[1001]; ll size[1001]; fo(i,1,1000)parent[i]=i,size[i]=1; fo(i,0,n-1){ string s; cin>>s; if(s.length()==1)continue; fo(j,1,s.length()-1)unionfind(s[0],s[i],parent,size); } ll num_of_con = 0; string al = "abcdefghijklmnopqrstuvwxyz"; fo(i,0,25){ if(findparent(al[i],parent)==al[i]-'a')num_of_con++; } cout<<num_of_con; return 0; }

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

Problem C is tagged as meet-in-the-middle. I'm unsure whether the mathematical solution is only the meet-in-the-middle or it's completely different approach so, could anyone please explain the meet-in-the-middle approach for Problem C. Apologies for necro-bumping.

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

In problem D, why do we use n + c — '0' for storing edges instead of simply c — '0'. It fails on test 4 but not sure why.

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

    alt_ may be to avoid self loop. i am not sure though.

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

    I also have same doubt??

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

      I think that to maintains uniqness of vertices because vertices are identified by id assigning to vertices.If there n=4 , "a","ab","abc","abcd". By bipartiteness , In first set there are 4 vertices and in second set 10 vertices. So itdentify uniqness of each vertices