CodeFoces.com is the place where I go when I do not know what to blog about. 🙂
Anyhow, as a developer who is with some experience there, I always expect that the first problems of Division 2 would be quite easy. And by quite easy, I mean that I would be able to solve them in less than 10 minutes, including the writing of the code and the reading of the problem.
However, this is not always the case. Today’s problem (A from contest 814) is looking like this:
A few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.
To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi’s sequence has been broken for a long time, but now Kaiki provides an opportunity.
Hitagi’s sequence a has a length of n. Lost elements in it are denoted by zeros. Kaiki provides another sequence b, whose length k equals the number of lost elements in a (i.e. the number of zeros). Hitagi is to replace each zero in a with an element from b so that each element in b should be used exactly once. Hitagi knows, however, that, apart from 0, no integer occurs in a and b more than once in total.
If the resulting sequence is not an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki’s sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in a with an integer from b so that each integer from b is used exactly once, and the resulting sequence is not increasing.
The first line of input contains two space-separated positive integers n (2 ≤ n ≤ 100) and k (1 ≤ k ≤ n) — the lengths of sequence a and brespectively.
The second line contains n space-separated integers a1, a2, …, an (0 ≤ ai ≤ 200) — Hitagi’s broken sequence with exactly k zero elements.
The third line contains k space-separated integers b1, b2, …, bk (1 ≤ bi ≤ 200) — the elements to fill into Hitagi’s sequence.
Input guarantees that apart from 0, no integer occurs in a and b more than once in total.
Output “Yes” if it’s possible to replace zeros in a with elements in b and make the resulting sequence not increasing, and “No” otherwise.
What is the idea? With other words, we have quite a few cases and they are somehow “reverted” – whenever we are able to make an increasing sequence only, we should be print No. In my head, success is always associated with Yes, but that was the smallest problem of all.
Let’s start with the cases:
- If we have more than 1 value in the 2. list (the elements to fill into Hitagi’s sequence) we should always be able to make a non-increasing sequence;
- If we have the 0 as a first element, we should only check the next one;
- If we have the 0 as a last element, we should only check the previous one;
- If we have the 0 as middle element, we should check two;
- Before even starting to check – its a good idea to check the non-changeable elements, whether they are in an increasing sequence;
- We should also check whether we are given at all any elements in the 2. list.
Having written this, after about 20 minutes of writing IF-ELSE-ELSEIF I have been able to pass the tests. Anyhow, do not do this at home (or at work):
Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class cf814a { static void Main() { string strInputA = Console.ReadLine(); int intLen1 = int.Parse(strInputA.Split()[0]); int intLen2 = int.Parse(strInputA.Split()[1]); List liIntA = new List(); List liIntB = new List(); liIntA = Console.ReadLine().Split().Select(int.Parse).ToList(); liIntB = Console.ReadLine().Split().Select(int.Parse).ToList(); bool bFake = false; bool bFakeBroken = false; if (intLen2 > 1) { bFakeBroken = true; } for (int i = 1; i < liIntA.Count; i++) { if (liIntA[i]!=0 && liIntA[i-1]!=0 && liIntA[i]<liinta[i-1]) {="" bfakebroken="true;" break;="" }="" int="" intposition="liIntA.IndexOf(0);" if="" (liintb.count="">0) { liIntA[intPosition] = liIntB[0]; } if (liIntA.Count>1) { if (intPosition == 0) { if (liIntA[0] < liIntA[1]) { bFake = true; } } else if (intPosition == liIntA.Count-1) { if (liIntA[intPosition-1]< liIntA[intPosition] ) { bFake = true; } } else { if (liIntA[intPosition-1]<liinta[intposition] &&="" liinta[intposition]<liinta[intposition+1])="" {="" bfake="true;" }="" if="" (bfakebroken="" intlen2="">0) { Console.WriteLine("Yes"); } else if (intLen2 == 0) { Console.WriteLine("No"); } else { if (bFake) { Console.WriteLine("No"); } else { Console.WriteLine("Yes"); } } } } |
Yup. That’s all. As dirty & ugly as it can be! 🙂 But it works, because it has tests! 😀