Vladosiya's blog

By Vladosiya, history, 8 days ago, In English

1714A - Everyone Loves to Sleep

Idea: Vladosiya

Tutorial
Solution

1714B - Remove Prefix

Idea: MikeMirzayanov

Tutorial
Solution

1714C - Minimum Varied Number

Idea: MikeMirzayanov

Tutorial
Solution

1714D - Color with Occurrences

Idea: MikeMirzayanov

Tutorial
Solution

1714E - Add Modulo 10

Idea: SixtyWithoutExam

Tutorial
Solution

1714F - Build a Tree and That Is It

Idea: MikeMirzayanov

Tutorial
Solution

1714G - Path Prefixes

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good editorial!

»
8 days ago, # |
  Vote: I like it +23 Vote: I do not like it

Code for D is messed up a bit.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is a better intuitive solution.

    Solution

    166883799

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I implemented it in an easier way.

    My Submission
    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please share your idea?

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

      hey man i sort of did the same implementation as yours, but I'm getting MLE, can you please tell me why ? D

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Mike Mirzayanov thanks for awesome editorial

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Idk, awesome editorial in my understanding contains much more detailed and intuitive solutions with hints, this one is just ok.

»
8 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Question D is a great problem,but why is the code for D so messy?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, can anyone tell me why did I get a MLE on D with submission 166572453? I precomputed every segment that can be painted in one step, however there can at most be 100*10 such segments for every test case. If every segment is 3 integers (12 bytes) then they use at most 12000 bytes of memory. Lets say that I copy all segments once into final, then I use at most 2*12000=24000 bytes per test case. This is way below the 256 MB memory limit, so why did my solution get MLE? Thanks.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve question D with DP? Can you tell me about it and share your code? If you can help me, I will thank you very much.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is my solution: 166798483

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What does your dp[i] mean?

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        dp[i] is the minimum number of steps needed to color prefix(length is i) of text t in red.

        use[i]: If an operation was done at a certain location, I recorded the selected subscript.

        from[i]: Otherwise I recorded which operation the location was affected by.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

        dp is an array and i is the element position in the array

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Indented solution of problem D from editorial:

Solution
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

"When you color a letter in red again, it stays red."

Missed this line during contest does this make the question similar to Jump game? ->where we can jump from index to any index in range (i,i+a[i])

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me out with my wa for E? https://codeforces.com/problemset/submission/1714/166799175

Approach:

  • I move the highest number to a remainder of 8
  • Everything else can either reach the number or not, and I set conditions for it.
For i in (0, n - 1)
Let k = a[i] / 10, l = a[max] / 10
    if remainder = 1, 2, 4, 8 then (l - k) % 2 = 0
    if remainder = 3, 6, 7, 9 then (l - k) % 2 = 1 
    if remainder = 5, a[i] + 5 == a[max]
    if remainder = 0, a[i] == a[max]
    else return NO
»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

The code for F: Build a Tree and That is it does not really clarify things mentioned in tutorial rather it has checks and implementations that makes it seem like the code to be working on a different idea. Can anyone either explain the tutorial or the code ? Thanks.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you help me with G.I checked ur code, but can't understand, Can u explain ur idea ? Thanks.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      So, let's first make a DFS call and make array Asum[N], where Asum[u] stores the sum of all the A-values along the edges from root to node u.

      Now notice that B values of all edges are positive. Let's pick any node u. And let's say, Path[u] = [B1, B2, B3, B4, B5,.....Bx] where the Bi indicates the B-values of all edges from root to node u.

      Since Bi s are positive the prefix sum on Path[u] will only increase. Let's call the prefix sum on Path[u] as PrefixPath[u].

      Since we want to know maximum prefix path that doesnt go beyond all A values sum in the path from root to u, the final answer for node u will be

      Answer[u] = Largest index k in PrefixPath[u] such that PrefixPath[k] > Asum[u].

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I can explain my idea of solution if it can help you.

    Let's place $$$1,2$$$ and $$$3$$$ nodes. There is $$$4$$$ possible ways to do it: link to image

    1. The first case: $$$d_{23} = d_{31} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

    2. The second case: $$$d_{31} = d_{23} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

    3. The third case: $$$d_{12} = d_{23} + d_{31}$$$. Let's check it, if it is right, then let's build our tree like in image.

    4. The last case: let's see that $$$d_{12} + d_{23} + d_{31} \le n$$$, let's get loop for $$$d_{14} = [1..n]$$$ (sum of $$$n$$$ for all cases is $$$\le 10^5$$$ so we can do it), now we know $$$d_{34} = d_{31} - d_{14}$$$ etc. If all this right, then let's build our tree like in image.

    If all cases are wrong, answer is NO.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Woah...Thank you so much. The image actually made your idea very clear. upvote_plus_plus

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My Editorial for the problems I solved

A
B
C
D
E
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a very good contest D was interesting but i think you should reorder the problem like this B C A E D G F

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I read the solution "Thus, we will apply the operation to each element of the array until its remainder modulo 10 becomes, for example, 2, and then check that the array does not contain both remainders 2 and 12 modulo 20." I don't know why do we need to check that "the aray does not contain both remainders 2 and 12 modulo 20". Why do we have to do that. Can you explain for me. Thanks

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are only 2 possible cycles when considered modulo 20 (2 -> 4 -> 8 -> 16 -> 2) and (12 -> 14 -> 18 -> 6 -> 12). If members of both cycles are present, you can never make all the numbers the same.

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

    we also can apply operation until we get either 2 or 4 or 6 or 8 as remainder of 10 from each (as all element eventually add-up and give even output) and then we can do same process ( which is checking whether array contain all same element)

    if we choose 2 all element will be 12 or 2 // while propagating (3,6,7,9) we can get 12 after some operation while changing element to module 20

    for 3's propagation ->3 6 12 14 18 26 32 34 38 46 ->>(%20)->> 3 6 12 14 18 6 12 14 18 6

    for 6's propagation ->6 12 14 18 26 3 34 328 46->>(%20)->> 6 12 14 18 6 12 14 18 6

    for 7's propagation ->7 14 18 26 32 34 38 46 ->>(%20)->> 7 14 18 6 12 14 18 6

    for 9's propagation ->9 18 26 32 34 38 46 52 ->>(%20)->> 9 18 6 12 14 18 6 12

    for other numbers (1,2,4,8) we can get 2 after some operation while changing element to module 20

    for 1's propagation ->1 2 4 8 16 22 24 28 36 42->>(%20)->> 1 2 4 8 16 2 4 8 16 2

    for 2's propagation ->2 4 8 16 22 24 28 36 42->>(%20)->> 2 4 8 16 2 4 8 16 2

    for 4's propagation ->4 8 16 22 24 28 36 42->>(%20)->> 4 8 16 2 4 8 16 2

    for 8's propagation ->8 16 22 24 28 36 42->>(%20)->> 8 16 2 4 8 16 2

    mark we can get 2 for (1,2,4,8) but we can't get 12 and similarly we can get 12 for (3,6,7,9) but we can't get 2;

    mark in similar way we can get 4 for (1,2,4,8) not 14 and we can get 14 for(3,6,7,9) not 4

    so change all element to either 2 or 4 or 6 or 8 you will end up having either (2,12) or (4,14) or (6,16) or (8,18) respectively and then check whether all same or not answer accordingly

    if 5 and 0 as (%10) present we need to check them separately either all same who having 0 as (%10) and if 5 present all should be 5 less from all element who are having 0 as (%10);

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using dp ??

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D and E were very nice But I think problem E is much easier than D.

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem F is also very nice and I think problem F is easier than D and E because I successfully passed F in the contest but failed to pass D and E.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Code for $$$Problem D$$$ should be posted like this :

Solution

I think Vladosiya has forgotten to write </spoiler> at the end.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anybody have E wa3 ,only one line of code was different between the two submissions Submissions id(wa3) : 166896597 Submissions id(ac) : 166900206 I'd like to know what the problem is. Could you please take a look at it for me,thanks!!!!!

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

G is not that hard compared to F, D

agree?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D can be also done with DP approach: 166555787

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

It took some time for me but I solved it finally :)

I started by stating out the different series that are being made and what commonalities they have. I deduced that there are two disjoint sets (if you exclude the multiples of 5 of which there are several disjoint sets.) that you get.

I called the set {1,2,4,8,16,22,24,...,96} for evenSet. And the set {3, 6, 12, 14, 18, 26, ..., 98} for oddSet.

The trick is to know that it's only the last two digits in every number which denotes which set it belongs to. For example 111 is equivalent to 11 in the series since they can converge.

What about prime numbers like 17? For them, we can see that 17 + 17 % 10 = 24 is a member of the evenSet. This is true for all such numbers, we can just check if either the number or the next number of the series of the current number is in the set we're interested to check.

What about multiples of 5? For them, we know that {5, 10} is one set, {15,20} another. The set cannot increase and thus we only need to worry about checking if all numbers are equal to the latter in the set. i.e. if a % 10 == 5, then we should look for a + 5. But note that we will check for all other numbers b, if b == a or b+5==a.

Once we have this, the solution should be quite straightforward:

  1. Generate the evenSet and the oddSet.

  2. Check if there are any multiples of 5, if so then we know that all of them should be in the same multiples set.

  3. If there were not any multiples of 5, then check if a or a + a%10 is in the evenSet or the oddSet. (Only take the last two digits of the number!). If there are already any in the oddSet, then since the sets are disjoint, then we know there are no way to make them equal. Similarly, we check in the oddSet and if there are any in the evenSet.

Took a bit of time but well worth it, learned a lot. Can probably be cleaned up a lot:

import java.util.HashSet;
import java.util.Scanner;

public class E {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int t = input.nextInt();

        while (t > 0) {
            solution(input);
            t--;
        }
    }
    public static void solution(Scanner input) {
        int n = input.nextInt();
        int[] a = new int[n];
        String result = "Yes";
        boolean odds = false;
        boolean evens = false;
        boolean fives = false;

        HashSet<Integer> evenSet = new HashSet<>();
        HashSet<Integer> oddSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            a[i] = input.nextInt();
        }

        // 1. Generate even sets: {1,2,4,8} etc. A member or the member + member % 10 counts.
        int firstEven = 1;
        while (firstEven < 100) {
            evenSet.add(firstEven);
            firstEven += firstEven % 10;
        }

        int firstOdd = 3;
        while (firstOdd < 100) {
            oddSet.add(firstOdd);
            firstOdd += firstOdd % 10;
        }

        // 2. Check if multiple of 5.
        int target = 0;
        for (int e : a) {
            if (e % 10 == 5) {
                if (fives && (e + 5) != target) {
                    result = "No";
                    break;
                }

                if (target == 0) {
                    target = e + 5;
                }
                fives = true;
            }

            if (e % 10 == 0) {
                if (fives && e != target) {
                    result = "No";
                    break;
                }

                if (target == 0) {
                    target = e;
                }
                fives = true;
            }
        }

        // 3. Check in odd and even sets if there are no fives.
        if (!fives) {
            for (int e : a) {
                String numStr = String.valueOf(e);
                int num;

                if (numStr.length() > 2) {
                    num = Integer.parseInt(numStr.substring(numStr.length() - 2));
                } else {
                    num = Integer.parseInt(numStr);
                }

                String nextNumStr = String.valueOf(num + num % 10);
                int nextNum;

                if (nextNumStr.length() > 2) {
                    nextNum = Integer.parseInt(nextNumStr.substring(nextNumStr.length() - 2));
                } else {
                    nextNum = Integer.parseInt(nextNumStr);
                }

                if (evenSet.contains(num) || evenSet.contains(nextNum)) {
                    if (odds) {
                        result = "No";
                        break;
                    }
                    evens = true;
                }

                if (oddSet.contains(num) || oddSet.contains(nextNum)) {
                    if (evens) {
                        result = "No";
                        break;
                    }
                    odds = true;
                }

            }
        }

        System.out.println(result);

    }
}

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, why flag12 and flag2 should not be true for the answer to be YES?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Remainders 2, 4, 6, 8 cycles and in that cycle number increases by 20. So difference between every two elements must divide by 20 (and these elements must have the same remainder modulo 20).

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If I understood it right, like if number 12 and 22 both exist in array we wont be able to make these numbers equal, since they will be be converted to 32 and 42 respectively, and this goes on, there wouldn't be a point where they will become equal.

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

i coded D iteratively, but its giving me MLE, can someone please tell me why ?

iterative D soln

»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I got TLE ? What's wrong with my code[submission:166546367]

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve G using binary lifting