awoo's blog

By awoo, history, 2 years ago, translation, In English

1749A - Cowardly Rooks

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1749B - Death's Blessing

Idea: BledDest

Tutorial
Solution (adedalic)

1749C - Number Game

Idea: BledDest

Tutorial
Solution (Neon)

1749D - Counting Arrays

Idea: BledDest

Tutorial
Solution (BledDest)

1749E - Cactus Wall

Idea: BledDest

Tutorial
Solution (Neon)

1749F - Distance to the Path

Idea: BledDest и adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +51
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Top 3 reason for depression

1)breakup

2)Substance Abuse

2)WA in div2 C

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you somehow solve F using centroid decomposition?

»
2 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

My Solution for the problem 1749D — Counting Arrays. (Python)

Simple

Commented One

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was trying to solve problem E using BFS + backpointer table for tracing steps. I have been debugging for an hour, but can't figure out why my solution is not optimal — is there a bug somewhere? Can someone pls help?

https://codeforces.me/contest/1749/submission/177375163

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problems !

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In D, I understand that if the i-th element is not "bad"(it can be removed only if it is at position 1), it's factors must contain all primes from 1 to i.

My question is: Why the number of good(not bad) elements is $$$\dfrac{m}{p_1p_2...p_k}$$$, where $$$p_k$$$ is mentioned in the editorial. Could somebody enlighten me why it is obvious :(

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For position i if you call an element not bad if it can only be removed at the first position, then the element must be divisible by all the prime numbers present in [1,i]. Let's say there are k prime numbers in [1,i] : p1, p2, p3...pk.

    Now, what is the smallest valid not bad element for the position i could be?

    It would be: L.C.M(p1,p2,...pk) = p1.p2.p3....pk

    What are the other valid not bad elements possible for the position i?

    It would the Multiples of L.C.M(p1,p2,...pk) = p1.p2.p3....pk

    How many valid not bad elements possible for the position i in [1,m]

    m/L.C.M(p1,p2...pk)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You mentioned multiples, now I can see why. Thanks very much!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this code for problem E is always wrong?

I have debuged it for 3 hours TAT

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone explain why the problem 1749E — Cactus Wall the path carved out by 0-1 DFS would always satisfy cacti cannot grow on cells adjacent to each other by side as we are not storing the cacti in the current path(only checking the initial cacti)?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Note that we do BFS traversal in an order that satisfy the initial constraints as well as we maintain the constraints by traversing diagonally. It suffices to check this, since only one of the path will be our answer (which will obviously satisfy the constraints as it has been constructed that way).

    TLDR : Since we only traverse diagonally to construct the path, the constraint is maintained for all paths (individually). This is necessary and sufficient.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The key observation of problem E is very interesting. I'm wondering if we can generalize this problem.

Say you're given a map consisting of '.', '#', 'A' and 'B'. You need to grow cactus so that one cannot go from an 'A' cell to a 'B' cell. In this case how can we find the starting and the ending point of the shortest path?

For example for the following map:

.#.#.
..#..
.AAA.
..A..
...BB
.BBB.

one must grow cactus like this:

.#.#.
..#..
#AAA#
.#A#.
..#BB
.BBB.

We can't just start from an arbitrary cell in the first column and ends at another arbitrary cell in the last column. There seems to be more restrictions.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, Obviously, it is more profitable for Bob to "prohibit" the smallest element of the array

Not to me. What about the case when Bob, using this tactics, takes the same integer multiple times? What if during her turn, Alice couldn't have taken all of them anyways? So that Bob wasted some moves and could rather take some other elements that Alice already took?

Could you show the proof that such situation never happens? It really puzzled me during the contest and still does. Any help is appreciated.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Not sure of your example. But i can try to explain the first line.

    Let's suppose there are some elements and each time Alice can remove element <= k-i+1 and bob can add the same amount to any element after Alice's turn. So if you see k-i+1 is decreasing and after Alice chance, if bob is going to add any k-i+1 to any element it will surely go beyond the scope of Alice next chance no matter how small or big number bob added it on(take any example and verify it). So bob will always try to take the smallest number as it will decrease Alice's chance to select element with k-i+1 condition in next turn. whereas if bob had selected any other number there is possibility Alice might use smallest in next turn.

    You can think of this problem as Alice remove one element and then Bob is also removing one element by increasing it byeond the Alice's scope.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      whereas if bob had selected any other number there is possibility Alice might use smallest in next turn.

      This is what I was looking for! Mystery solved, thanks!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't prove the following lemma used in Problem E

There exists no path from top row to bottom row only if there is a zigzag path consisting of $$$#$$$ from a cell in the leftmost column to a cell in the rightmost column.

It is very intuitive to see it by drawing some pictures, but I just can't get around proving it formally. I tried induction on $$$n•m$$$, greedy proof strategies etc. But nothing seems to work. Any help? BledDest

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For C: Number game, I had a solution that is O(nlogn), although I understand the constraints didn't require it. the idea was binary search for k.

I devised a function "doesKWork" that takes inputs as the k to check and also an array where a[i] stores the number of elements lesser than or equal to i present in the original array.

bool doesKWork(vector<int> &lEq,int k)
{
    int j = 0;
    for (int i = 1; i <= k; i++)
    {
        if(lEq[i] >= k+i-1)
        {
            continue;
        }
        else
        {
            return false;
        }
    }

    return true;
}

for k to be a valid number such that Alice wins in optimal play by bob, this must be the condition satisfied. each lEq[i] >= k+i-1. then its just simple binary search for k.

//binary search on k
//lesserThanOrEqualTo is a vector calculated before, check submission for details
        int l = 1, r = n;
        int ans = 1;
        bool setAns = false;
        while(l <= r)
        {
            int mid = (l+r)/2;

            if(doesKWork(lesserThanOrEqualTo,mid))
            {
                //then we check the ahead segment
                l = mid+1; continue;
            }
            else
            {
                //then we check the segment before mid
                r = mid-1; continue;
            }
        }
        cout << l-1 << endl;

You can check my submission for reference 177187641

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why isn't the total number of arrays just $$$m^n$$$ ? Why should we take $$$m^1 + m^2 + ...+m^n$$$ ?

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    "You have to calculate the number of ambiguous arrays $$$a$$$ such that the length of $$$a$$$ is from $$$1$$$ to $$$n$$$"

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem C, what i am thinking is that we will first vector in which values are stored then take values one by one from left but i dont understand what does stages mean here

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really sorry for necroposting. Can anyone please help me why my code is giving WA in D.

269406458

My solution is exactly like Author's solution. But I can't figure out what is wrong with my code. I have thought it for hours and still can't figure out the problem with my code.

Sieve is for calculating prime numbers(though it is unnecessary). dq stores prime numbers upto 100. total = m^1+m^2+⋯+m^n. res stores the number of unambiguous arrays.

Sorry for my bad English.